[PYTHON] AtCoder Beginner Contest 121 Revue des questions précédentes

Temps requis

Impressions

Puisque le problème D était XOR, je pensais que c'était impossible, mais ce n'était pas si difficile et je sentais que je n'étais pas enthousiaste. (Familiarité pas enthousiaste)

Problème A

Faites juste attention à ne pas compter les endroits que vous portez.

answerA.py

H,W=map(int,input().split())
h,w=map(int,input().split())
print(H*W-h*W-w*H+h*w)

Problème B

Chaque formule d'évaluation doit être appliquée à tous les problèmes.

answerB.py

n,m,c=map(int,input().split())
b=list(map(int,input().split()))
ans=0
for i in range(n):
    a=list(map(int,input().split()))
    k=0
    for i in range(m):
        k+=a[i]*b[i]
    ans+=(k+c>0)
print(ans)

Problème C

Prenez autant que vous le pouvez avec le tri croissant. Il est nécessaire de juger avec précision de la quantité qui peut être prise.

answerC.py

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
ab.sort()
ans=0
for i in range(n):
    if m>ab[i][1]:
        ans+=ab[i][0]*ab[i][1]
        m-=ab[i][1]
    else:
        ans+=ab[i][0]*m
        print(ans)
        break

Problème D

Post-scriptum (2020/1/29)

** Ajout du code implémenté par la méthode de solution Writer. Il est écrit vers la fin de l'article. La solution d'écriture est plus polyvalente. ** **

Dans le calcul de XOR **, chaque bit peut être calculé indépendamment **, et lorsque l'on considère le XOR des entiers $ c_1 $ ~ $ c_n $, convertissez-le en un nombre binaire et comptez le nombre de 1 pour chaque bit. Par conséquent, il peut être calculé comme 1 lorsque le nombre de 1 est impair et 0 lorsque le nombre est pair. En d'autres termes, même dans ce problème, il suffit de prêter attention à chaque bit de A à B et d'effectuer le calcul indépendamment. Tout d'abord, pensons au cas où A en B sont tous convertis en nombres binaires et classés par ordre croissant. À ce stade, vous pouvez voir que cela ressemble à la figure ci-dessous.

Si vous regardez combien de 0 et de 1 sont dans chaque bit, vous pouvez voir que ** chaque bit répète périodiquement des 0 et des 1 **. Il est clair (sans réfléchir?) Que la longueur de ce cycle sera de 2 $ ^ {k} $ pour le kème bit (indexé à 0). De plus, lorsque k> = 1, la longueur d'un cycle est paire, donc si vous calculez XOR, un cycle sera égal à 0, vous pouvez donc l'ignorer. ** Combien de 1 sont consécutifs aux deux extrémités de A et B? Il est bon de compter ** (l'image de compter la partie qui reste dans la partie impaire, lorsque k = 1, seuls 0 et 1 sont répétés, de sorte que le nombre de 1 peut être facilement obtenu). De plus, lorsque certains bits de A et B sont différents, vous pouvez simplement calculer combien de 1 à 1 il y a d'un côté, mais si A et B sont tous les deux des 1 dans ce bit, tous les 1 de A à B Veuillez noter qu'il sera compté deux fois (inclus dans le même cycle) lorsqu'il le deviendra. En outre, lorsque vous considérez combien de temps les 1 continuent à partir de la fin, vous pouvez facilement penser au nombre de 1 en considérant la différence comme indiqué dans la figure ci-dessous (en tenant compte de la limite).

Lorsque ce qui précède est mis en œuvre, cela devient comme suit.

Aussi, comme il est un peu désorganisé, le flux de pensée est organisé en dessous.

** (1) Puisqu'il s'agit de XOR, vous n'avez qu'à compter le nombre de 1 dans chaque bit. ↓ (2) Il y a (continu) 0 et 1 cycles ↓ (3) Comptez le nombre de 1 à partir de la fin (car la durée du cycle est paire) ↓ (4) Vous pouvez comprendre (3) en considérant le nombre de frontières où la période change **

Notez également que lorsque b = 0, l'argument de log2 devient 0 et devient RE. Je me suis fait prendre.

answerD.py

import math
import sys
a,b=map(int,input().split())
if b==0:
    print(0)
    sys.exit()
n=math.floor(math.log2(b))+1
ans=[0]*n
form="0"+str(n)+"b"
sa=format(a,form)
sb=format(b,form)
for i in range(n):
    if i==n-1:
        if (b-a+1)%2==0:
            ans[i]=((b-a+1)//2)%2
        else:
            if sa[i]=="1":
                ans[i]=((b-a+1)//2+1)%2
            else:
                ans[i]=((b-a+1)//2)%2
        break
    if sa[i]=="1" and sb[i]=="0":
        s_compa=sa[:i]+"1"*(n-i)
        cmpa=int(s_compa,2)
        ans[i]=(cmpa-a+1)%2
    elif sa[i]=="0" and sb[i]=="1":
        s_compb=sb[:i]+"1"+"0"*(n-i)
        cmpb=int(s_compb,2)
        ans[i]=(b-cmpb+1)%2
    elif sa[i]=="1" and sb[i]=="1":
        s_compa=sa[:i]+"1"*(n-i)
        cmpa=int(s_compa,2)
        s_compb=sb[:i]+"1"+"0"*(n-i)
        cmpb=int(s_compb,2)
        if cmpa>a:#cmpb<b
            ans[i]=((b-cmpb+1)+(cmpa-a+1))%2
        else:
            ans[i]=(b-a+1)%2
cnt=0
for i in range(n):
    cnt+=(ans[i]*2**(n-i-1))
print(cnt)

Solution écrivain

Lors du calcul des XOR de plusieurs nombres, convertissez-les en nombres binaires et comptez le nombre de 1 pour chaque bit. Lorsque le nombre de 1 est impair, il est de 1 et lorsqu'il est pair, il est de 0. Il peut être calculé en bits. À partir de là, vous pouvez voir que si vous prenez XOR pour ** deux entiers consécutifs k et k + 1 (k est pair), ils seront les mêmes sauf pour le 0ème bit, donc le résultat de XOR sera 1 **. Par conséquent, il n'est pas nécessaire de considérer tous les XOR de A à B dans l'ordre, mais en comptant les paires de (k, k + 1) (k est un nombre pair) de A à B et en considérant la planéité et l'étrangeté totales des paires. Vous pouvez facilement trouver le XOR de A à B. Cependant, à ce moment, les cas ont été divisés en faisant attention à savoir si A et B étaient inclus dans l'ensemble. Le code ressemble à ceci:

answerE_better.py

a,b=map(int,input().split())
if a%2==0 and b%2==0:
    k=(b-a)//2
    print(b^(k%2))
elif a%2==0 and b%2==1:
    k=(b-a+1)//2
    print(k%2)
elif a%2==1 and b%2==0:
    k=(b-a-1)//2
    print(a^b^k%2)
else:
    k=(b-a)//2
    print(a^(k%2))