Code de l'éducation forces Round 86 Bacha Review (9/17)
Les résultats de cette fois
Impressions de cette époque
J'étais impatient comme d'habitude cette fois, mais j'ai pu switcher et passer D à la dernière minute, c'est donc un bon point. Après tout, lorsque le problème est impatient, le problème n'est pas organisé et ** les notes ont tendance à être encombrées **, alors ** prenez des notes aussi proprement que possible ** et ** si vous ne comprenez vraiment pas Je voudrais faire une copie propre **.
Problème A
Je pense qu'il y avait un problème similaire dans ABC auparavant.
Les signes de $ x et y $ sont les mêmes, et $ x <y $. À ce stade, il est préférable de les réduire tous de manière monotone, et comme l'opération de ** ② se déplacera en même temps **, réduisez $ y $ à $ x $ par l'opération de ①. De plus, puisque $ y = x $, vous pouvez sélectionner l'opération la plus appropriée pour les opérations ① et ②, et la valeur minimale à obtenir est $ (yx) \ fois a + min (x \ fois b, 2 \ fois x \ fois a) $. Ce sera.
A.py
for _ in range(int(input())):
x,y=map(int,input().split())
a,b=map(int,input().split())
if x>y:
x,y=y,x
print((y-x)*a+min(x*b,2*x*a))
Problème B
Récemment, j'ai le sentiment qu'il est devenu possible de passer à travers les problèmes liés à la construction de Kodofo à grande vitesse. Je serais heureux si vous pouviez sortir avec ABC (je suis très déçu car c'était le cas avec ABC-F la dernière fois ...).
Tout d'abord, j'ai pensé que ** le cycle pourrait être assez petit **. En effet, si vous pouvez créer une chaîne qui sera $ 0101… $ ou $ 1010… $, la période sera 2. La considération basée sur cette politique est la suivante.
Premier,
B.py
for _ in range(int(input())):
t=input()
if all(i=="0" for i in t) or all(i=="1" for i in t):
print(t)
else:
print(len(t)*"01")
Problème C
Quand j'ai fait la politique initiale, j'étais impatient parce que j'ai fait une erreur dans ** $ i, j $ que j'ai écrit **, et je n'ai pas pu trouver la bonne réponse. De plus, après cela, malgré le problème typique **, j'ai essayé de le résoudre analytiquement **.
Tout d'abord, il est évident que le calcul dans la requête ne sera pas à temps, donc ** pré-calculer **. À ce stade, si vous écrivez tous les nombres possibles, ce sera 10 $ ^ 9 $ **, donc ce n'est évidemment pas à temps.
Donc, en faisant attention à $ (x \ mod \ a) \ mod \ b \ neq (x \ mod \ b) \ mod \ a $, $ i = x \ mod \ a, j = x \ mod \ b $ Si vous connaissez la formule ci-dessus, vous pouvez penser à la formule ci-dessus, alors j'ai pensé à $ ab $ combinaison de $ i, j $, mais ** Si vous avez une image du théorème du reste chinois, il vous suffit de connaître le reste de $ ab $ ** compris. Cela peut être $ (x \ mod \ a) \ mod \ b \ neq (x \ mod \ b) \ mod \ a \ leftrightarrow (x \ mod \ a) \ mod \ b \ neq (x \ mod \ b) \ mod \ a \ leftrightarrow Cela peut être dit du fait qu'il devient k \ mod \ a) \ mod \ b \ neq (k \ mod \ b) \ mod \ a $.
Par conséquent, en pré-calcul, $ pre [i]: = $ ($ (i \ mod \ a) \ mod \ b \ neq (i \ mod ) lorsque le reste divisé par $ ab $ est $ 0 $ ~ $ i $ b) Trouvez le nombre de \ mod \ a $) (la somme cumulée est utilisée car elle sera nécessaire plus tard).
De plus, dans la requête, $ i \ in [l, r] $ est utilisé pour trouver le nombre de $ (i \ mod \ a) \ mod \ b \ neq (i \ mod \ b) \ mod \ a $. Est calculé en soustrayant le nombre à $ i \ dans [0, l-1] $ du nombre à ** $ i \ dans [0, r] $ **. De plus, si le nombre dans $ i \ in [0, x] $ est $ f (x) $, il peut être calculé par $ f (r) -f (l-1) $.
Sur cette base, envisagez de trouver $ f (x) $ en utilisant le pré-calcul, mais le reste divisé par ** $ ab $ est $ 0 $ ~ $ ab-1 $, et les nombres sont bouclés dans l'ordre à partir de 0. Considérons ** et le nombre de boucles, $ f (x) = [\ frac {x} {a \ times b}] \ times pre [ab-1] + pre [x \ mod \ ( Il peut être calculé comme a \ times b)] $.
Par conséquent, chaque requête est calculée par $ O (1) $, vous pouvez donc ouvrir un programme suffisant pour $ O (t \ times (a \ times b + q)) $ dans son ensemble.
C.py
from itertools import accumulate
def f(i):
global a,b,pre
x=i//(a*b)
y=i%(a*b)
return x*pre[-1]+pre[y]
for _ in range(int(input())):
a,b,q=map(int,input().split())
pre=[int((i%a)%b!=(i%b)%a) for i in range(a*b)]
pre=list(accumulate(pre))
ans=[]
for i in range(q):
l,r=map(int,input().split())
ans.append(str(f(r)-f(l-1)))
#print(f(r),f(l-1))
print(" ".join(map(str,ans)))
Problème D
Personnellement, c'était un problème plus intuitif et plus facile à résoudre que le problème C. Il peut être assez efficace de modifier le problème à résoudre après qu'il soit bloqué pendant environ 30 minutes. Cependant, l'énoncé du problème était un peu difficile à lire.
(Ci-après, supposons que les séquences données pour la distribution aux cas de test soient $ m $. Elles sont ** triées par ordre décroissant **.)
Chaque cas de test est une collection de plusieurs séquences d'une certaine longueur (← Je ne suis intéressé que par la longueur, alors ** l'interprétez comme une collection de plusieurs nombres ** et résolvez le problème ci-dessous). De plus, des cas de test dans lesquels le nombre de cas de test est distribué de sorte que le nombre de cas de test est réduit tout en satisfaisant la condition que $ i $ est contenu dans moins de $ c \ _i $ dans chaque cas de test **. Considérez le nombre de. Il remplit également $ n \ geqq c \ _1 \ geqq c \ _2 \ geqq… \ geqq c \ _k \ geqq 1 $, en s'assurant que le nombre minimum de cas de test existe.
Ici, j'ai décidé de décider avec gourmandise quel cas de test inclure dans l'ordre à partir du nombre avec la plus grande contrainte **. On peut aussi dire que ** lorsqu'un certain nombre est décidé, les restrictions après cela sont toujours satisfaites **.
Tout d'abord, préparez un tableau $ ans $ qui gère l'ensemble du scénario de test (chaque scénario de test contient plusieurs éléments). De plus, laissez la longueur de $ ans $ être $ l $ et l'indice que vous regardez dans le cas de test $ ans $ soit $ now $. Puis ajoutez $ [m [0]] $ à $ ans $ comme premier cas de test et initialisez $ now $ avec 0 et $ l $ avec 1.
Sur cette base, ajoutez $ m [1],…, m [n-1] $ au scénario de test dans cet ordre. Quand vous regardez $ m [i] $, quand $ m [i-1]> m [i] $, $ c [m [i] -1]> c [m [i-1] - Cela peut être 1] $. Dans ce cas, vous pouvez mettre à jour ** $ now $ à 0 ** et remplacer $ m [i] $ par $ ans [now] $. En outre, ce jugement est $ len (ans [0]) \ <c [m [i] -1] $ ou $ c [m [i-1] -1] \ <c [m [i] -1] $ Peut être fait par
Ensuite, quand $ c [m [i] -1] = c [m [i-1] -1] $, il est possible qu'il puisse être ajouté après l'élément vu dans ** $ now $ **, donc $ now + = 1 $ jusqu'à ce qu'un élément qui devient $ len (ans [now]) \ <c [m [i] -1] $ soit trouvé, et s'il est trouvé, ajoutez-le à $ ans [now] $. De plus, s'il n'est pas trouvé, il n'y a pas assez de cas de test, alors ajoutez $ [m [i]] $ à $ ans $.
En répétant cela, vous pouvez décider avidement de réduire au maximum le nombre de cas de test. Après cela, vous pouvez générer le scénario de test final selon les instructions du problème.
Il est difficile d'expliquer ce qui précède avec des mots, mais je pense que la mise en œuvre peut se faire sans heurts tant que la légitimité de la méthode de la cupidité est comprise.
D.py
n,k=map(int,input().split())
m=sorted(list(map(int,input().split())),reverse=True)
c=list(map(int,input().split()))
ans=[[m[0]]]
#ans longueur
l=1
#Quelle séquence et quelle séquence mettre(Attention aux mises à jour)(Comme si vacant)
now=0
for i in range(1,n):
if len(ans[0])<c[m[i]-1]:
now=0
ans[now].append(m[i])
else:
while now!=l:
if len(ans[now])<c[m[i]-1]:
break
now+=1
if now==l:
ans.append([m[i]])
l+=1
else:
ans[now].append(m[i])
print(len(ans))
for i in range(len(ans)):
print(len(ans[i]),end=" ")
print(" ".join(map(str,ans[i])))
Après le problème E
Je vais sauter cette fois
Recommended Posts