Codeforces Round # 618 (Div.2) Examen Bacha (9/26)
Les résultats de cette fois
Impressions de cette époque
(Depuis que je l'ai écrit le 10/4, ma mémoire est un peu vague.)
Cette fois, tout s'est bien passé sans WA. Cependant, j'ai passé trop de temps sur l'apparence et la lisibilité du problème D. L'autre jour, l'ARC s'est également senti dépassé par le problème, alors je veux m'habituer au problème de haute difficulté et gagner en confiance afin de pouvoir penser avec précision et sans égal quel que soit le score.
Problème A
Assurez-vous que ni la somme ni le produit ne sont nuls. Tout d'abord, ** il est plus facile de penser au produit **, et ajoutez +1 à tout élément 0 inclus pour éviter que 0 ne soit inclus. Sur cette base, si le total est 0, vous pouvez ajouter +1 à un élément approprié (autre que -1), et vous pouvez trouver le nombre de +1 jusqu'à présent.
A.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(n):
if a[i]==0:
a[i]=1
ans+=1
if sum(a)!=0:
print(ans)
else:
print(ans+1)
Problème B
Trouvez la valeur lorsque la différence entre les valeurs médianes divisées en deux nombres impairs est minimisée. Je n'ai pas pu trouver une solution tout de suite, mais comme il y avait pas mal de gens qui passaient par là, je pensais que ce serait de toute façon un bâillon. Donc, j'ai pris la différence entre les deux valeurs au milieu, en comptant à partir de la plus petite, et j'ai essayé l'échantillon, et il correspondait, alors je l'ai soumis.
Je voudrais le soumettre avec un certain degré de certitude, mais j'étais impatient et j'ai soumis ce numéro sans preuve. Je ne le prouverai pas parce que je ne suis pas motivé, mais j'ai juste besoin de montrer qu'une médiane est en dessous de l'élément $ n $ th et l'autre est en dessous de l'élément $ n + 1 $ th. Par exemple, si vous supposez que les valeurs médianes sont toutes de $ n $ ou moins, vous pouvez l'afficher par la méthode absurde **.
B.py
for _ in range(int(input())):
n=int(input())
a=sorted(list(map(int,input().split())))
print(a[n]-a[n-1])
Problème C
Tout d'abord, j'ai fait une expérience et y ai réfléchi. De plus, comme il est au niveau du bit ou **, considérez l'opération pour chaque bit **. Maintenant, considérant ce qui arrive au calcul de $ f (x, y) = (x | y) -y $ à chaque bit, c'est comme suit.
| x | y | f(x,y) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Par conséquent, la condition selon laquelle l'opération binaire $ f (x, y) $ est effectuée dans l'ordre à partir du front et que le bit $ i $ est enfin perceptible est ** le bit du premier élément est 1 et seulement 0 est sorti après cela. Si ça ne vient pas **. Tout d'abord, considérez ** comme une condition ** qu'il n'y a qu'un seul ** $ i $ bit qui vaut 1. En traitant cette condition, vous pouvez préparer un bit de masque qui se détache dans le bit $ i $ lorsqu'il n'y a qu'un seul bit $ i
C.py
n=int(input())
a=list(map(int,input().split()))
mask=0
for i in range(31):
if [(j>>i)&1 for j in a].count(1)==1:
mask+=(1<<i)
#Trouvez le maximum
ans=[-1,-1]
for i in range(n):
if ans[0]<(a[i]&mask):
ans[0]=a[i]&mask
ans[1]=i
realans=[]
realans.append(a[ans[1]])
for i in range(n):
if i!=ans[1]:
realans.append(a[i])
print(" ".join(map(str,realans)))
Problème D
Si vous pouvez le voir, c'est simple. J'ai personnellement trouvé l'énoncé du problème très difficile à lire.
Tout d'abord, pour résumer l'énoncé du problème, déterminez si le cadre extérieur créé lorsque la figure donnée est déplacée en parallèle tout en incluant l'origine est similaire à la figure d'origine. À ce moment-là, j'ai pensé que ce serait bien s'il y avait des côtés parallèles et de même longueur ** (par exemple, le diamant). Cette preuve intuitive peut être vue en illustrant le mouvement en se déplaçant en parallèle aussi loin que possible de l'origine, y compris l'origine **. J'avais une bonne idée de cela dans mon esprit, alors j'ai illustré l'exemple 2. Ensuite, c'est devenu intuitif, donc je vais l'implémenter.
Quant à l'implémentation, puisque les points sont donnés dans le sens antihoraire, nous profitons du fait que la connexion des points adjacents devient un côté, et stockons les côtés (en tant que vecteur) dans l'ordre donné à $ bords $. De plus, si ** $ n $ est un nombre impair, il ne sera pas apparié **, donc NO sera affiché à l'avance. De plus, il y a $ n $ côtés, mais dans $ bords $, les côtés séparés par $ \ frac {n} {2} $ sont appariés de sorte que les paires soient parallèles et de longueur égale. Juge. Puisque ce jugement stocke les côtés comme vecteur, il suffit de juger si ** l'addition devient un vecteur 0 **.
D.py
n=int(input())
points=[]
for i in range(n):
points.append(list(map(int,input().split())))
if n%2==1:
print("No")
exit()
edges=[]
for i in range(n-1):
edges.append([points[i+1][0]-points[i][0],points[i+1][1]-points[i][1]])
edges.append([points[0][0]-points[n-1][0],points[0][1]-points[n-1][1]])
#print(edges)
for i in range(n//2):
if edges[i][0]+edges[i+n//2][0]!=0 or edges[i][1]+edges[i+n//2][1]!=0:
#print(i)
#print(points[i][0]+points[i+n//2][0])
#print(points[i][1]+points[i+n//2][1])
print("No")
exit()
print("Yes")
E problème
Après réflexion, il semblait possible de l'implémenter s'il y avait un arbre de segment qui pourrait ajouter des intervalles et prendre la valeur maximale, mais c'était impossible car ce n'était pas un simple entier que je voulais mettre sur l'arbre de segmentation.
Je voulais comprendre l'arbre des segments à cause d'ACLBC, mais je n'avais pas assez de motivation et je ne l'ai pas encore pris (je comprends RMQ). J'ai aussi acheté un livre sur les fourmis, donc je prévois de le prendre bientôt, et je le conserverai comme exercice à ce moment-là.
Problème F
Je vais sauter cette fois
Recommended Posts