[PYTHON] Codeforces Runde # 676 (Div. 2) Bacha Review (10/31)
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Dieses Mal konnte ich das C-Problem aufgeben und am D-Problem arbeiten, sodass ich mich erholen konnte. Ich denke, die Einstellung, nicht aufzugeben, war gut.
Dieses Problem war ein schwieriges Ergebnis, da es viele Knebelprobleme gab, aber da es sich eindeutig um ein Knebelproblem handelt, würde ich gerne ** gut damit umgehen **.
Problem A
(Im Folgenden ist das $ i $ -Bit $ a \ _i, b \ _i, x \ _i $)
Dies ist ein kleines Problem, das wir oft in Codeforces sehen. In einem solchen Problem kann ** jedes Bit unabhängig berechnet werden **. Überlegen Sie also, was mit dem $ i $ -Bit passiert.
(1) Wenn $ a \ _i = 1 ist, ist b \ _i = 1 $ Wenn $ x \ _i = 1 $ ist, steht das $ i $ -Bit von $ (a \ oplus x) + (b \ oplus x) $ nicht, sodass das $ i $ -Bit 0 ist, was das Minimum ist.
(2) Wenn $ a \ _i = 1, b \ _i = 0 $ oder $ a \ _ i = 0, ist b \ _i = 1 $ Da das $ i $ -Bit von $ (a \ oplus x) + (b \ oplus x) $ in einem der $ x \ _i = 0,1 $ auffällt, ist das $ i $ -Bit mit 1 das kleinste.
(3) Wenn $ a \ _i = 0 ist, ist b \ _i = 0 $ Wenn $ x \ _i = 0 $ ist, steht das $ i $ -Bit von $ (a \ oplus x) + (b \ oplus x) $ nicht, sodass das $ i $ -Bit bei 0 das kleinste ist.
Aus dem Obigen kann die Antwort erhalten werden, indem 1 Bit zu $ a \ _i und b \ _i $ addiert wird.
A.py
for _ in range(int(input())):
a,b=map(int,input().split())
x=0
for i in range(32):
if ((a>>i)&1):
if ((b>>i)&1):
pass
else:
x+=(1<<i)
else:
if ((b>>i)&1):
x+=(1<<i)
else:
pass
print(x)
B-Problem
Es dauerte lange, bis ich auf die Idee kam, und ich teilte sie in Fälle von Dunkelheit ein.
Was Sie tun, ist ziemlich typisch. In jedem Fall ist es möglich, Sie daran zu hindern, vom Start zum Ziel zu gelangen. Ich denke, es ist möglich, Sie daran zu hindern, sich dem Ziel und dem Start zu nähern.
Von hier aus ist es ein Ideenspiel, aber wenn Sie denken, dass Sie nur die beiden Quadrate neben dem Startpunkt und die beiden Quadrate neben dem Zielpunkt ändern müssen, ist die Überlegung gut. Mit anderen Worten ist es ausreichend, wenn die zwei Quadrate neben dem Startpunkt 0 (oder 1) und die zwei Quadrate neben dem Zielpunkt 1 (oder 0) sind. Dies kann auch erreicht werden, indem nur bis zu zwei Quadrate mit guter Einstellung eingestellt werden.
Ich denke, dass es ohne Schwierigkeiten implementiert werden kann, wenn Sie nur auf den Fall achten, wenn zwei benachbarte Quadrate 0,0 oder 1,1 sind. Wie ich beim Schreiben dieses Kommentars bemerkt habe, habe ich sowohl (0,0), (1,1) als auch (1,1), (0,0) ausprobiert und die mit der geringeren Anzahl von Zellen zum Ändern ausgewählt. In diesem Fall ist die Implementierung einfacher.
B.py
for _ in range(int(input())):
n=int(input())
s=[input() for i in range(n)]
f1=[int(s[0][1]),int(s[1][0])]
f2=[int(s[-1][-2]),int(s[-2][-1])]
ans=[]
if f1==[0,0]:
if f2[0]==0:
ans.append([n,n-1])
if f2[1]==0:
ans.append([n-1,n])
elif f1==[1,1]:
if f2[0]==1:
ans.append([n,n-1])
if f2[1]==1:
ans.append([n-1,n])
elif f2==[0,0]:
if f1[0]==0:
ans.append([1,2])
if f1[1]==0:
ans.append([2,1])
elif f2==[1,1]:
if f1[0]==1:
ans.append([1,2])
if f1[1]==1:
ans.append([2,1])
elif f1==[0,1] or f1==[1,0]:
if f1==[0,1]:
ans.append([2,1])
else:
ans.append([1,2])
if f2[0]==0:
ans.append([n,n-1])
if f2[1]==0:
ans.append([n-1,n])
print(len(ans))
for i in range(len(ans)):
print(ans[i][0],ans[i][1])
C-Problem
Ich fand es sehr schwierig. Da es schwierig ist, eine Lösung für das Knebelproblem zu formulieren, stützt es sich in der Regel auf Ideen und ist nicht stabil.
Ich habe versucht, es zu einer guten Rezitation zu machen, aber ** ich konnte mich am Anfang nicht von der Lösung von $ i = n-1 $ lösen **. Bei solchen Problemen empfiehlt es sich, sich beim Erstellen auf die minimalen und maximalen Werte zu konzentrieren. Mit anderen Worten, wenn Sie auf $ i = 2 $ achten, können Sie es mit der folgenden Methode erstellen.
Wenn Sie am Anfang $ n = 2 $ setzen, können Sie $ S \ _1 $ vom Ende ** trennen. Ich denke, es ist möglich zu glauben, dass es durch Inversion gut konstruiert werden kann.
C.py
s=input()
n=len(s)
print(3)
print("L 2")
print("R 2")
print(f"R {2*n-1}")
D Problem
Dieses Problem war auch ein Knebel. Es ist alles Knebel ... Und da ich nicht gut darin bin, es umzusetzen, habe ich die Fälle im Dunkeln wie im B-Problem aufgeteilt. Ich bin froh, dass ich gewonnen habe.
Erstens ** ist die Operation schwer zu verstehen, also organisieren Sie sie **. In Anbetracht der Art und Weise, wie die Koordinaten in jeder Operation verschoben werden, gibt es die folgenden 6 Möglichkeiten.
Und wenn jede Bewegung ** $ c \ _i $ zu $ x \ _i $ ** wird, bewegt sie sich zu $ (0,0) \ rightarrow (x, y) $, sodass die folgenden Bedingungen erforderlich sind. ..
Zu diesem Zeitpunkt ist ** $ x \ _1-x \ _4 $ unter den obigen Bedingungen festgelegt **, und die Werte von $ x \ _6-x \ _3 bzw. x \ _2-x \ _5 $ werden bestimmt. Wenn außerdem der Wert von $ x \ _6-x \ _3, x \ _2-x \ _5 $ bestimmt wird, wird der Wert von $ x \ _6, x \ _3, x \ _2, x \ _5 $ eindeutig bestimmt. Wenn Sie sich überlegen, welcher Term von ** $ x \ _1-x \ _4, x \ _6-x \ _3, x \ _2-x \ _5 $ auf 0 ** gesetzt werden soll, wird die Überlegung von hier aus fortgesetzt. ..
Wenn Sie $ x \ _1-x \ _4 $ nicht verwenden möchten, setzen Sie zunächst $ x \ _1-x \ _4 = 0 $ (1). Wenn Sie $ x \ _6-x \ _2 $ nicht verwenden möchten, können Sie $ x \ _6-x \ _3 = 0 $ (2) verwenden. Wenn Sie $ x \ _2-x \ _5 $ nicht verwenden möchten, können Sie $ verwenden. Sie können x \ _2-x \ _5 = 0 $ (3) setzen.
Zusätzlich können die Fälle (1) bis (3) wie folgt klassifiziert werden.
(1) Wenn $ x \ _1-x \ _4 = 0 $
[1] Über $ x \ _1, x \ _4 $
[2] Über $ x \ _6, x \ _3 $ Wenn $ x \ geqq 0 $, $ x \ _6 = x, x \ _3 = 0 $ Wenn $ x \ leqq 0 $, $ x \ _6 = 0, x \ _3 = -x $
[3] Über $ x \ _2, x \ _5 $ Wenn $ y \ geqq 0 $, $ x \ _2 = y, x \ _5 = 0 $ Wenn $ y \ leqq 0 $, $ x \ _2 = 0, x \ _5 = -y $
(2) Wenn $ x \ _6-x \ _3 = 0 $
[1] Über $ x \ _6, x \ _3 $
[2] Über $ x \ _1, x \ _4 $ Wenn $ x \ geqq 0 $, $ x \ _1 = x, x \ _4 = 0 $ Wenn $ x \ leqq 0 $, $ x \ _1 = 0, x \ _4 = -x $
[3] Über $ x \ _2, x \ _5 $ Wenn $ y-x \ geqq 0 $, $ x \ _2 = y-x, x \ _5 = 0 $ Wenn $ y-x \ leqq 0 $, $ x \ _2 = 0, x \ _5 = x-y $
(3) Wenn $ x \ _2-x \ _5 = 0 $
[1] Über $ x \ _2, x \ _5 $
[2] Über $ x \ _1, x \ _4 $ Wenn $ y \ geqq 0 $, $ x \ _1 = y, x \ _4 = 0 $ Wenn $ y \ leqq 0 $, $ x \ _1 = 0, x \ _4 = -y $
[2] Über $ x \ _6, x \ _3 $ Wenn $ x-y \ geqq 0 $, $ x \ _6 = x-y, x \ _3 = 0 $ Wenn $ x-y \ leqq 0 $, $ x \ _6 = 0, x \ _3 = y-x $
Geben Sie schließlich die Mindestkosten für $ x \ _1, x \ _2, x \ _3, x \ _4, x \ _5, x \ _6 $ aus, die in jedem der oben genannten Fälle erhalten wurden. TU es einfach.
D.py
def calc():
global c1,c2,c3,c4,c5,c6,x1,x2,x3,x4,x5,x6
return x1*c1+x2*c2+x3*c3+x4*c4+x5*c5+x6*c6
for _ in range(int(input())):
x,y=map(int,input().split())
c1,c2,c3,c4,c5,c6=map(int,input().split())
ans=[]
if x>0 and y>0:
x1,x2,x3,x4,x5,x6=0,y,0,0,0,x
elif x>0:
x1,x2,x3,x4,x5,x6=0,0,0,0,-y,x
elif y>0:
x1,x2,x3,x4,x5,x6=0,y,-x,0,0,0
else:
x1,x2,x3,x4,x5,x6=0,0,-x,0,-y,0
ans.append(calc())
if x>0 and y-x>0:
x1,x2,x3,x4,x5,x6=x,y-x,0,0,0,0
elif y-x>0:
x1,x2,x3,x4,x5,x6=0,y-x,0,-x,0,0
elif x>0:
x1,x2,x3,x4,x5,x6=x,0,0,0,x-y,0
else:
x1,x2,x3,x4,x5,x6=0,0,0,-x,x-y,0
ans.append(calc())
if y>0 and x-y>0:
x1,x2,x3,x4,x5,x6=y,0,0,0,0,x-y
elif x-y>0:
x1,x2,x3,x4,x5,x6=0,0,0,-y,0,x-y
elif y>0:
x1,x2,x3,x4,x5,x6=y,0,y-x,0,0,0
else:
x1,x2,x3,x4,x5,x6=0,0,y-x,-y,0,0
ans.append(calc())
print(min(ans))
Nach dem E-Problem
Ich werde diesmal nicht lösen.
Recommended Posts