Codeforces Round # 609 (Div.2) Examen Bacha (10/6)
Les résultats de cette fois
Impressions de cette époque
J'ai essayé de corriger l'erreur de lecture d'hier, mais je l'ai mal lu en raison d'un problème C. C'est trop serré ... ** Si vous ne pouvez pas le résoudre en 30 minutes, vous devrez peut-être le courage de le couper rapidement **.
Problème A
Je vais le faire commodément. Puisqu'il s'agit d'une soustraction de nombres, ** faites attention à la régularité **.
Quand $ n $ est pair, $ a et b $ sont pairs, donc par exemple, si $ b = 4 $, $ a $ est encore plus grand que $ 4 $, donc le sujet est satisfait.
Lorsque $ n $ est impair, l'un de $ a et b $ est pair et l'autre est impair. Par exemple, si $ b = 9 $, $ a $ est encore plus grand que $ 9 $, le sujet est donc satisfait.
A.py
n=int(input())
if n%2==0:
print(n+4,4)
else:
print(n+9,9)
Problème B
Vous pouvez les trier, ainsi vous pouvez penser au nombre de restes qu'il y a dans ** $ a $ et $ b $ **, et résoudre le problème en supposant que la réponse est toujours valide sous les contraintes. Notez également que $ m $ peut représenter jusqu'à 10 ^ 9 façons, donc l'ajout de 1 à la fois nécessite des calculs de 10 ^ 9 $ dans le temps.
Dans l'état initial, l'élément est enregistré dans le dictionnaire sous la forme qu'il y a $ y $ dans le reste de $ x
À ce moment, ajoutez $ x $ à chaque élément et divisez par $ m $ pour trouver le minimum $ x $ requis pour l'ensemble des restes $ a $ et $ b $ à correspondre. Ici, concentrez-vous sur le dernier élément de ** $ a $ (reste maximum) **, et lors de l'ajout de plusieurs nombres, le prochain ensemble qui peut correspondre est le début de ** $ b $. Quand il correspond à l'élément de (le reste est le plus petit) **. Par conséquent, supprimez le dernier élément de $ a $ et ajoutez-le à nouveau comme premier élément de $ a $ pour trouver la ** différence ** nécessaire pour ce faire. De plus, avec la valeur initiale définie sur $ x = 0 $, la différence est ajoutée à $ x $ dans l'ordre et à $ x $ lorsque $ a et b $ sont ajoutés jusqu'à ce qu'ils correspondent.
B.py
from collections import Counter
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
#0,1,Trier par le reste de ...
#déplacez simplement un pour correspondre à cela
#Au plus n fois
c=sorted([list(i) for i in list(Counter(a).items())],key=lambda x:x[0])
d=sorted([list(i) for i in list(Counter(b).items())],key=lambda x:x[0])
n=len(c)
#Supprimez le dos et collez-le à l'avant(Gestion des différences)
x=0
for i in range(n):
p=c.pop(-1)
#Il n'est peut-être pas nécessaire de faire le tour
dp=(d[0][0]+m-p[0])%m
x+=dp
c.insert(0,p)
#print(c,d)
for j in range(n):
c[j][0]+=dp
c[j][0]%=m
if c==d:
print(x%m)
break
Problème C
Je l'ai mal lu et inondé ...
(Le chiffre $ i $ (indexé à 0) du haut du nombre donné est $ a \ _i $, et le chiffre $ i $ du haut du nombre final est $ b \ _i $. .)
$ a \ _i = a \ _ {i + k} $ fait une ** mystérieuse erreur de lecture ** qu'il ne tient qu'à une distance de $ k $, et $ a \ _i = a \ _ {i + 2k} $ Je pensais que ce n'était pas nécessaire. Pourquoi….
En d'autres termes, lorsque $ a \ _i = a \ _ {i + k} $ tient, tous les chiffres avec le même reste divisé par ** $ k $ ont la même valeur **. Par conséquent, si vous décidez $ b \ _i = a \ _i $ dans $ 0 \ leqq i \ <k $, $ b \ _i $ sera déterminé uniquement pour $ i \ geqq k $.
Maintenant, lorsque vous regardez $ i \ geqq k $ à partir du plus petit de $ i $, faites attention au chiffre qui devient $ b \ _i \ \ neq a \ _i $. Autrement dit, si ** $ b \ _i > a \ _i $ apparaît en premier, alors $ b> a $ tient **. De plus, il n'y a pas de $ b $ plus petit que cela, donc affichez-le comme réponse. Inversement, si ** $ b \ _i \ <a \ _i $ apparaît en premier, ** doit augmenter l'un des chiffres de +1. De plus, si +1 est ajouté, tous les chiffres avec le même reste divisé par $ k $ seront incrémentés de +1. ** Peu importe le chiffre restant ajouté par +1 dans $ b \ _i (i \ <k) $, $ b \ _i> a \ _i $ détient **. Par conséquent, il est préférable d'ajouter +1 au chiffre $ i $ où $ i \% \ k = k-1 $ tient, et $ b> a $ tient. De plus, s'il n'y a pas de chiffre qui devient $ b \ _i \ \ neq a \ _i $, alors $ b = a $, donc le sujet est satisfait.
C.py
#Je vais regarder le reste
#J'ai mal compris tous les sujets
#Je pensais que c'était une seule fois
n,k=map(int,input().split())
a=list(map(int,input()))
ans=[-1]*n
upper=False
lower=False
#Les mises à jour se produisent en bas et en haut
#La mise à jour n'est-elle pas acceptable?
for i in range(k):
ans[i]=a[i]
for i in range(k,n):
ans[i]=ans[i-k]
if ans[i]==a[i]:
pass
elif ans[i]>a[i]:
#Quand il devient supérieur en premier
#Tu n'as pas à changer
if lower==False and upper==False:
upper=True
else:
#Lorsque vous devenez plus bas en premier
#Changez simplement la partie inférieure
#Sera-t-il supérieur s'il est modifié?
if lower==False and upper==False:
lower=True
#Changer celui qui a fait le mieux
#9 n'est pas bon
#En dessous se trouve 0
for j in range(k-1,-1,-1):
if ans[j]!=9:
break
for l in range(i+1):
if l%k==j:
ans[l]+=1
elif l%k>j:
ans[l]=0
print(n)
print("".join(map(str,ans)))
D problem
J'ai pensé à DP et à une bonne méthode de configuration, mais il semble que c'était un problème de connaissance. Je pense que cela ne peut pas être aidé si cela est abandonné.
** Il semble qu'il soit préférable de répartir les dominos en damier ** (Référence).
Lorsque vous créez un motif en damier peint en noir et blanc, vous pouvez voir qu'il est inférieur ou égal à min (le nombre de carrés blancs, le nombre de carrés noirs) (✳︎). En outre, la réponse est de trouver la valeur maximale, qui peut être indiquée comme étant min (nombre de cellules blanches, nombre de cellules noires). Voir ici pour la preuve. Je pense que c'est montré de manière intuitive.
D.py
n=int(input())
a=list(map(int,input().split()))
#Je ne sais pas
#Un système qui répand les dominos → peignez en damier(Quoi?)
w,b=0,0
for i in range(n):
if i%2==0:
w+=a[i]//2
b+=a[i]-a[i]//2
else:
b+=a[i]//2
w+=a[i]-a[i]//2
print(min(b,w))
Après le problème E
Je vais sauter cette fois.
Recommended Posts