[PYTHON] Codeforces Round # 676 (Div.2) Examen Bacha (10/31)
Les résultats de cette fois
Impressions de cette époque
Cette fois, j'ai pu abandonner le problème C et travailler sur le problème D, donc j'ai réussi à récupérer. Je pense que l'attitude de ne pas abandonner était bonne.
Ce problème était un résultat difficile car il y avait beaucoup de problèmes de bâillon, mais comme il s'agit clairement d'un problème de bâillon, je voudrais ** bien le gérer **.
Problème A
(Ci-après, le bit $ i $ est $ a \ _i, b \ _i, x \ _i $)
C'est un petit problème que nous voyons souvent dans Codeforces. Dans un tel problème, ** chaque bit peut être calculé indépendamment **, alors considérez ce qui arrive au bit $ i $.
(1) Lorsque $ a \ _i = 1, b \ _i = 1 $ Si $ x \ _i = 1 $, le bit $ i $ de $ (a \ oplus x) + (b \ oplus x) $ ne tiendra pas, donc le bit $ i $ est 0, ce qui est le minimum.
(2) Lorsque $ a \ _i = 1, b \ _i = 0 $ ou $ a \ _ i = 0, b \ _i = 1 $ Puisque le bit $ i $ de $ (a \ oplus x) + (b \ oplus x) $ se distingue dans n'importe lequel de $ x \ _i = 0,1 $, le bit $ i $ est le plus petit à 1.
(3) Lorsque $ a \ _i = 0, b \ _i = 0 $ Si $ x \ _i = 0 $, le bit $ i $ de $ (a \ oplus x) + (b \ oplus x) $ ne restera pas, donc le bit $ i $ est le plus petit à 0.
De ce qui précède, la réponse peut être obtenue en ajoutant 1 bit à $ a \ _i et b \ _i $.
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)
Problème B
Il a fallu beaucoup de temps pour arriver à l'idée, et je l'ai divisée en cas d'obscurité.
Ce que vous faites est assez typique. Dans tous les cas, il est possible de vous empêcher d'aller de début en but, donc je pense qu'il est peut-être possible de vous empêcher de passer près du but et près du départ.
À partir de là, c'est un jeu d'idées, mais si vous pensez qu'il vous suffit de changer ** les deux cases adjacentes au point de départ et les deux cases adjacentes au point de but **, la considération se passe bien. En d'autres termes, il suffit que les deux cellules adjacentes au point de départ soient à 0 (ou 1) et les deux cellules adjacentes au point de but à 1 (ou 0). En outre, cela peut être réalisé en ajustant jusqu'à deux carrés avec un bon ajustement.
Je pense que cela peut être mis en œuvre sans difficulté si vous ne faites attention qu'au cas où deux carrés adjacents sont 0,0 ou 1,1. Comme je l'ai remarqué en écrivant ce commentaire, j'ai essayé à la fois (0,0), (1,1) et (1,1), (0,0) et j'ai choisi celui avec le plus petit nombre de cellules à changer. Si c'est le cas, ce sera plus facile à mettre en œuvre.
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])
Problème C
J'ai trouvé cela très difficile. Comme il est difficile de formuler une solution au problème du bâillon, il a tendance à reposer sur des idées et n'est pas stable.
J'ai essayé d'en faire une bonne récitation, mais ** je n'ai pas pu m'éloigner de la solution de $ i = n-1 $ au début **. Pour de tels problèmes, il est bon de ** faire attention aux valeurs minimales et maximales lors de la construction. En d'autres termes, si vous faites attention à $ i = 2 $, vous pouvez le construire par la méthode suivante.
En mettant $ n = 2 $ au début, vous pouvez séparer $ S \ _1 $ de la fin **, donc je pense qu'il est possible de penser qu'il peut être bien construit par inversion.
C.py
s=input()
n=len(s)
print(3)
print("L 2")
print("R 2")
print(f"R {2*n-1}")
Problème D
Ce problème était aussi un bâillon. Tout est bâillon ... Et comme je ne suis pas doué pour l'implémenter, j'ai divisé les cas dans le noir comme dans le cas du problème B. Je suis content d'avoir gagné.
Tout d'abord, ** l'opération est difficile à comprendre, alors organisez-la **. En considérant comment déplacer les coordonnées dans chaque opération, il existe 6 manières suivantes.
Et quand chaque mouvement ** $ c \ _i $ est tourné $ x \ _i $ **, il se déplace vers $ (0,0) \ rightarrow (x, y) $, donc les conditions suivantes sont requises. ..
À ce stade, ** $ x \ _1-x \ _4 $ est fixé dans les conditions ci-dessus **, et les valeurs de $ x \ _6-x \ _3 et x \ _2-x \ _5 $ sont déterminées respectivement. De plus, lorsque la valeur de $ x \ _6-x \ _3, x \ _2-x \ _5 $ est déterminée, la valeur de $ x \ _6, x \ _3, x \ _2, x \ _5 $ est déterminée de manière unique. Par conséquent, si vous pensez à quel terme de ** $ x \ _1-x \ _4, x \ _6-x \ _3, x \ _2-x \ _5 $ doit être mis à 0 **, la considération à partir d'ici continuera. ..
Tout d'abord, si vous ne souhaitez pas utiliser $ x \ _1-x \ _4 $, définissez $ x \ _1-x \ _4 = 0 $ (1). De même, si vous ne voulez pas utiliser $ x \ _6-x \ _2 $, vous pouvez utiliser $ x \ _6-x \ _3 = 0 $ (2), si vous ne voulez pas utiliser $ x \ _2-x \ _5 $, vous pouvez utiliser $. Vous pouvez définir x \ _2-x \ _5 = 0 $ (3).
De plus, les cas (1) à (3) peuvent être classés comme suit.
(1) Lorsque $ x \ _1-x \ _4 = 0 $
[1] Environ $ x \ _1, x \ _4 $
[2] Environ $ x \ _6, x \ _3 $ Lorsque $ x \ geqq 0 $, $ x \ _6 = x, x \ _3 = 0 $ Lorsque $ x \ leqq 0 $, $ x \ _6 = 0, x \ _3 = -x $
[3] Environ $ x \ _2, x \ _5 $ Lorsque $ y \ geqq 0 $, $ x \ _2 = y, x \ _5 = 0 $ Lorsque $ y \ leqq 0 $, $ x \ _2 = 0, x \ _5 = -y $
(2) Lorsque $ x \ _6-x \ _3 = 0 $
[1] Environ $ x \ _6, x \ _3 $
[2] Environ $ x \ _1, x \ _4 $ Lorsque $ x \ geqq 0 $, $ x \ _1 = x, x \ _4 = 0 $ Lorsque $ x \ leqq 0 $, $ x \ _1 = 0, x \ _4 = -x $
[3] Environ $ x \ _2, x \ _5 $ Lorsque $ y-x \ geqq 0 $, $ x \ _2 = y-x, x \ _5 = 0 $ Lorsque $ y-x \ leqq 0 $, $ x \ _2 = 0, x \ _5 = x-y $
(3) Lorsque $ x \ _2-x \ _5 = 0 $
[1] Environ $ x \ _2, x \ _5 $
[2] Environ $ x \ _1, x \ _4 $ Lorsque $ y \ geqq 0 $, $ x \ _1 = y, x \ _4 = 0 $ Lorsque $ y \ leqq 0 $, $ x \ _1 = 0, x \ _4 = -y $
[2] Environ $ x \ _6, x \ _3 $ Lorsque $ x-y \ geqq 0 $, $ x \ _6 = x-y, x \ _3 = 0 $ Lorsque $ x-y \ leqq 0 $, $ x \ _6 = 0, x \ _3 = y-x $
Enfin, indiquez le coût minimum pour $ x \ _1, x \ _2, x \ _3, x \ _4, x \ _5, x \ _6 $ obtenu dans chacun des cas ci-dessus. Simplement fais-le.
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))
Après le problème E
Je ne résoudrai pas cette fois.
Recommended Posts