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

Temps requis

スクリーンショット 2020-01-20 14.39.41.png

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.

IMG_0096.JPG

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).

IMG_0095.JPG

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))

Recommended Posts

AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 127 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 112 Revue des questions précédentes
AtCoder Beginner Contest 076 Revue des questions précédentes
AtCoder Beginner Contest 089 Revue des questions précédentes
AtCoder Beginner Contest 069 Revue des questions précédentes
AtCoder Beginner Contest 079 Revue des questions précédentes
AtCoder Beginner Contest 067 Revue des questions précédentes
AtCoder Beginner Contest 093 Revue des questions précédentes
AtCoder Beginner Contest 046 Revue des questions précédentes
AtCoder Beginner Contest 123 Revue des questions précédentes
AtCoder Beginner Contest 049 Revue des questions précédentes
AtCoder Beginner Contest 078 Revue des questions précédentes
AtCoder Beginner Contest 081 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 060 Revue des questions précédentes
AtCoder Beginner Contest 104 Revue des questions précédentes
AtCoder Beginner Contest 057 Revue des questions précédentes
AtCoder Beginner Contest 121 Revue des questions précédentes
AtCoder Beginner Contest 126 Revue des questions précédentes
AtCoder Beginner Contest 090 Revue des questions précédentes
AtCoder Beginner Contest 103 Revue des questions précédentes
AtCoder Beginner Contest 061 Revue des questions précédentes
AtCoder Beginner Contest 059 Revue des questions précédentes
AtCoder Beginner Contest 044 Revue des questions précédentes
AtCoder Beginner Contest 083 Revue des questions précédentes
AtCoder Beginner Contest 048 Revue des questions précédentes
AtCoder Beginner Contest 124 Revue des questions précédentes
AtCoder Beginner Contest 116 Revue des questions précédentes
AtCoder Beginner Contest 097 Revue des questions précédentes
AtCoder Beginner Contest 088 Revue des questions précédentes
AtCoder Beginner Contest 092 Revue des questions précédentes
AtCoder Beginner Contest 099 Revue des questions précédentes
AtCoder Beginner Contest 065 Revue des questions précédentes
AtCoder Beginner Contest 053 Revue des questions précédentes
AtCoder Beginner Contest 094 Revue des questions précédentes
AtCoder Beginner Contest 063 Revue des questions précédentes
AtCoder Beginner Contest 107 Revue des questions précédentes
AtCoder Beginner Contest 071 Revue des questions précédentes
AtCoder Beginner Contest 064 Revue des questions précédentes
AtCoder Beginner Contest 082 Revue des questions précédentes
AtCoder Beginner Contest 084 Revue des questions précédentes
AtCoder Beginner Contest 068 Revue des questions précédentes
AtCoder Beginner Contest 058 Revue des questions précédentes
AtCoder Beginner Contest 043 Revue des questions précédentes
AtCoder Beginner Contest 098 Revue des questions précédentes
AtCoder Beginner Contest 114 Revue des questions précédentes
AtCoder Beginner Contest 045 Revue des questions précédentes