[PYTHON] Codeforces Runde # 663 (Div. 2) Bacha Review (8/13)
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Ich habe das C-Problem 10 Minuten lang nicht verstanden. Als ich zum D-Problem sprang, machte ich immer wieder Fehler in der Implementierung **. Als ich das C-Problem nach Beendigung gelöst habe, konnte ich es in weniger als 10 Minuten lösen, also habe ich einen Fehler bei der Lösung des Problems gemacht ... Später war ich ungeduldig, als ich die Rangliste meines Freundes sah, deshalb möchte ich versuchen, diese Ungeduld zu beseitigen.
Problem A
Es war ein Knebelproblem ...
Erstens liegt $ p $ in der Größenordnung von $ 1 $ ~ $ n $, und der in $ p \ _i, p \ _ {i + 1},… p \ _ {j-1}, p \ _j $ enthaltene Maximalwert ist mindestens Es wird $ j-i + 1 $ sein. Auch für jede nicht negative ganze Zahl $ A, B $ aus $ A \ oder \ B \ geqq A, B $, $ p \ _i \ oder \ p \ _ {i + 1} \ oder \… \ oder \ p \ _ {j-1} \ oder \ p \ _ j \ geqq j-i + 1 $ gilt. Da die Bedingung für eine beliebige Zahlenfolge erfüllt ist, ist es daher ausreichend, eine geeignete Folge auszugeben.
A.py
for _ in range(int(input())):
n=int(input())
print(" ".join(map(str,range(1,n+1))))
B-Problem
Ich habe mich gefragt, ob es mit BFS usw. gemacht werden würde, weil es das Raster ändert, aber es war ein Gag-Problem nach dem A-Problem.
Bewegen Sie sich nur nach rechts oder unten und erreichen Sie (n, m) von einem beliebigen Quadrat aus. Hier sind ** Muster, die nicht erreicht werden können ** Muster, die nach unten oder rechts eindringen. Um ein solches Muster zu vermeiden, sind daher alle Zellen ganz rechts D und alle Zellen unten R. Wenn Sie diese Quadrate ändern können, können Sie auch immer (n, m) erreichen, auch wenn andere Quadrate der Ausgangspunkt sind.
Aus dem Obigen lautet die Antwort (die Zelle ganz rechts ist die Anzahl von R) + (die unterste Zelle ist die Anzahl von D).
B.py
for _ in range(int(input())):
n,m=map(int,input().split())
a=[input() for i in range(n)]
ans=0
for i in range(m-1):
ans+=(a[n-1][i]=="D")
for i in range(n-1):
ans+=(a[i][m-1]=="R")
print(ans)
C-Problem
Ich hatte während des Wettbewerbs eine Richtlinie, aber als ich sie wegwarf und das D-Problem löste, lief mir die Zeit davon. ** Ich werde versuchen, Probleme zu lösen, die lösbar zu sein scheinen **.
Zunächst wird angenommen, dass zwei ungerichtete Seiten des Subjekts für ein bestimmtes $ i $ ($ (i, j_1), (i, j_2) $) ** usw. gezeichnet werden können.
Aus der obigen Abbildung (die Anzahl der Teile ①), (die Anzahl der Teile ②) gilt $ i <j \ _1, j \ _2 $. Da entweder $ j \ _1 <j \ _2, j_2 <j_1 $ gilt, können Sie auch eine ungerichtete Seite mit $ (j_1, j_2) $ und $ i, j \ _1, j \ _2 $ zeichnen Sie können zwischen wechseln.
Betrachten wir daher eine Zahlenfolge (** zusätzliche Ereignisse **), die keinen Zyklus hat. Da das obige Ergebnis für jedes $ i $ gilt, gibt es hier keinen Zyklus in der Sequenz **, in dem es kein $ i $ gibt, das der Mindestwert ist. Eine solche Sequenz ist nicht nur eine monotone Sequenz wie $ 1,2,3,4 $, sondern auch eine Sequenz wie $ 1,4,3,2 $, die nur einen Maximalwert hat. Wenn es einen Maximalwert gibt, ist die Zahl $ N $. Wenn der Maximalwert die $ i $ -te Position erreicht, ist dies wie in der folgenden Abbildung dargestellt.
Hier wird die Reihenfolge der Zahlen, die zu $ 1 $ ~ $ i-1 $, $ i + 1 $ ~ $ N $ th kommen, durch Auswahl der Zahlen eindeutig bestimmt, sodass der Maximalwert $ N $ der $ i $ th ist. Die Nummer wird nach $ \ _ {N-1} C \ _ {i-1} $ angeordnet, wenn es darum geht. Wenn Sie die Summe von $ i = 1 $ ~ $ N $ finden, dann ist $ \ _ {N-1} C \ _ {i-1}, \ _ {N-1} C \ _ {i-1}, …, \ _ {N-1} C \ _ {i-1} = 2 ^ {N-1} $.
Aus dem Obigen ergibt sich, dass die Anzahl der Spalten ohne Zyklen $ 2 ^ {N-1} $ und die Gesamtzahl der Vorwärtsspalten $ N! $ Ist. $ N! -2 ^ {N-1} $ ist also die Antwort.
C.py
n=int(input())
def modpow():
ret=1
for i in range(n-1):
ret*=2
ret%=(10**9+7)
return ret
def perm():
ret=1
for i in range(n):
ret*=(i+1)
ret%=(10**9+7)
return ret
print((perm()-modpow())%(10**9+7))
D Problem
Das Problem besteht darin, die Mindestanzahl von Malen zu finden, um die Zahl so zu ändern, dass alle Zahlen von 1s in einer quadratischen Submatrix beliebiger Länge ungerade sind.
Hier ** kann eine quadratische Matrix mit einer Länge von 4 erzeugt werden, indem vier quadratische Matrizen mit einer Länge von 2 kombiniert werden. Wenn jedoch die Anzahl von 1s in einer quadratischen Matrix mit einer Länge von 2 ungerade ist, ist die Länge gleich Die Anzahl der Einsen in einer quadratischen Matrix mit einer 4 ist gerade. Wenn es also $ n, m \ geqq 4 $ ist, muss -1 ausgegeben werden. Betrachten Sie im Folgenden den Fall von $ n <4 $ oder $ m <4 $. Beachten Sie auch, dass es $ n \ leqq m $ ist (ich habe es während des Wettbewerbs nicht bemerkt).
(1) Wenn $ n = 1 $
Da es keine quadratische Submatrix gleicher Länge gibt, muss sie nicht geändert werden, sondern nur 0 ausgegeben werden.
(2) Wenn $ n = 2,3 $
In diesen Fällen gibt es immer eine Mindestanzahl von Malen (der Beweis wird weggelassen). Zuerst dachte ich, ich würde die gierige Methode verwenden, um die Spalten in der Reihenfolge ** zu bestimmen, aber ich gab die gierige Methode auf, weil die Fallklassifizierung kompliziert ist und die ** gierige Methode nicht gerechtfertigt werden kann **. Ich tat.
Hier ** DP **, wenn man bedenkt, dass ** Spalten in der Reihenfolge ** entschieden werden und dass jede Spalte nur $ 2 ^ n $ von $ n = 2,3 $ ** ist Ich denke, Sie können auf die Idee kommen. DP kann wie folgt definiert werden.
$ dp [i] [j]: = $ (Mindestanzahl von Änderungen, wenn die Spalte $ i $ festgelegt ist, und wird zu $ j $, wenn die Spalte $ i $ als Binärzahl betrachtet wird)
Betrachten Sie hier den Übergang von DP von $ dp [i-1] [j] $ zu $ dp [i] [k] $. Da $ 1 \ leqq j, k \ leqq 2 ^ n $ ist, wird der Übergang durch eine Doppelschleife dargestellt (** es gibt mehrere Zustände! **). Wenn $ j und k $ bestimmt werden, wird im Voraus berechnet, ob die Anzahl der Einsen in den Spalten $ i-1 $ und $ i $ in der quadratischen Matrix mit einer Länge von 2 ungerade ist. Kann durchgeführt werden (bitcheck [j] [k]). Zusätzlich kann die Anzahl der Versuche, die erforderlich sind, um von $ a [i] $ zu $ k $ zu wechseln, vorberechnet werden (bitcalc [a [i]] [k] als Binärzahl angesehen). Basierend darauf ist der Übergang von DP wie folgt.
Wenn $ bitcheck [j] [k] = True $ ist, ist $ dp [i] [k] = dp [i-1] [j] + bitcalc [eine [i] $ Bit-Notation $] [k] $
Da TL sehr streng ist und ** viele Eingaben enthält **, müssen Sie "input = sys.stdin.readline" verwenden, um die Eingabe zu beschleunigen (dies ist möglicherweise nicht erforderlich, wenn die Implementierung gut ist). Hmm.).
D.py
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
a=[[int(j) for j in input()[:-1]] for i in range(n)]
if n>=4 and m>=4:
print(-1)
exit()
if n==1 or m==1:
print(0)
exit()
inf=10000000000000
if n==2 or m==2:
bitcheck=[[0]*4 for i in range(4)]
for j in range(4):
for k in range(4):
for i in range(1):
if (((j>>i)&1)+((k>>i)&1)+((j>>(i+1))&1)+((k>>(i+1))&1))%2==0:
bitcheck[j][k]=False
break
else:
bitcheck[j][k]=True
bitcalc=[[0]*4 for i in range(4)]
for j in range(4):
for k in range(4):
for i in range(2):
if ((j>>i)&1)^((k>>i)&1):
bitcalc[j][k]+=1
if n==2:
n,m=m,n
b=[list(x) for x in zip(*a)]
else:
b=[i for i in a]
dp=[[inf]*4 for i in range(n)]
for i in range(n):
if i!=0:
for j in range(4):
for k in range(4):
if bitcheck[j][k]:
dp[i][k]=min(dp[i][k],dp[i-1][j]+bitcalc[b[i][0]+b[i][1]*2][k])
else:
for k in range(4):
dp[i][k]=bitcalc[b[i][0]+b[i][1]*2][k]
print(min(dp[n-1]))
exit()
if n==3 or m==3:
bitcheck=[[0]*8 for i in range(8)]
for j in range(8):
for k in range(8):
for i in range(2):
if (((j>>i)&1)+((k>>i)&1)+((j>>(i+1))&1)+((k>>(i+1))&1))%2==0:
bitcheck[j][k]=False
break
else:
bitcheck[j][k]=True
bitcalc=[[0]*8 for i in range(8)]
for j in range(8):
for k in range(8):
for i in range(3):
if ((j>>i)&1)^((k>>i)&1):
bitcalc[j][k]+=1
if n==3:
n,m=m,n
b=[list(x) for x in zip(*a)]
else:
b=[i for i in a]
dp=[[inf]*8 for i in range(n)]
for i in range(n):
if i!=0:
for j in range(8):
for k in range(8):
if bitcheck[j][k]:
dp[i][k]=min(dp[i][k],dp[i-1][j]+bitcalc[b[i][0]+b[i][1]*2+b[i][2]*4][k])
else:
for k in range(8):
dp[i][k]=bitcalc[b[i][0]+b[i][1]*2+b[i][2]*4][k]
print(min(dp[n-1]))
exit()
Nach dem E-Problem
Ich werde diesmal überspringen
Recommended Posts