[PYTHON] AtCoder Beginner Contest 121 Rückblick auf frühere Fragen

Benötigte Zeit

Impressionen

Da das D-Problem XOR war, hielt ich es für unmöglich, aber es war nicht so schwierig und ich fühlte mich nicht begeistert. (Vertrautheit nicht begeistert)

Problem A

Achten Sie nur darauf, die Stellen zu zählen, die Sie tragen.

answerA.py

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

B-Problem

Jede Bewertungsformel sollte auf alle Probleme angewendet werden.

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)

C-Problem

Nehmen Sie so viel wie möglich mit aufsteigender Sortierung. Es ist notwendig, genau zu beurteilen, wie viel genommen werden kann.

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

D Problem

Nachtrag (29.1.2020)

** Der von der Writer-Lösungsmethode implementierte Code wurde hinzugefügt. Es ist gegen Ende des Artikels geschrieben. Die Writer-Lösung ist vielseitiger. ** ** **

Bei der Berechnung von XOR ** kann jedes Bit unabhängig berechnet werden **. Wenn Sie das XOR der ganzen Zahlen $ c_1 $ ~ $ c_n $ berücksichtigen, konvertieren Sie es in eine Binärzahl und zählen Sie die Anzahl von 1s für jedes Bit. Daher kann es als 1 berechnet werden, wenn die Anzahl der Einsen ungerade ist, und als 0, wenn die Anzahl der Einsen gerade ist. Mit anderen Worten, selbst bei diesem Problem ist es ausreichend, auf jedes Bit von A bis B zu achten und die Berechnung unabhängig durchzuführen. Betrachten wir zunächst den Fall, in dem A bis B alle in Binärzahlen umgewandelt und in aufsteigender Reihenfolge angeordnet werden. Zu diesem Zeitpunkt können Sie sehen, dass es wie in der Abbildung unten aussieht.

Wenn Sie sich ansehen, wie viele Nullen und Einsen sich in jedem Bit befinden, können Sie sehen, dass ** jedes Bit periodisch Nullen und Einsen wiederholt **. Es ist klar (ohne nachzudenken?), Dass die Länge dieses Zyklus $ 2 ^ {k} $ für das k-te Bit (0-indiziert) beträgt. Wenn k> = 1 ist, ist die Länge eines Zyklus gerade. Wenn Sie also XOR berechnen, ist ein Zyklus 0, sodass Sie ihn ignorieren können. ** Wie viele Einsen sind an beiden Enden von A und B aufeinanderfolgend? Es ist gut zu zählen ** (das Bild des Zählens des Teils, der im ungeraden Teil verbleibt, wenn k = 1 ist, werden nur 0 und 1 wiederholt, so dass die Zahl 1 leicht erhalten werden kann). Wenn einige Bits von A und B unterschiedlich sind, können Sie einfach berechnen, wie viele 1s bis 1s auf einer Seite vorhanden sind. Wenn jedoch sowohl A als auch B 1s in diesem Bit sind, sind alle 1s in A bis B. Bitte beachten Sie, dass es doppelt gezählt wird (im selben Zyklus enthalten), wenn es wird. Wenn Sie überlegen, wie lange Einsen vom Ende an andauern, können Sie leicht darüber nachdenken, wie viele Einsen es gibt, indem Sie den Unterschied berücksichtigen, wie in der folgenden Abbildung gezeigt (unter Berücksichtigung der Grenze).

Wenn das Obige implementiert ist, wird es wie folgt.

Da es ein wenig unorganisiert ist, ist der Gedankenfluss unten organisiert.

** (1) Da es sich um XOR handelt, müssen Sie nur zählen, wie viele Einsen sich in jedem Bit befinden. ↓ (2) Es gibt (kontinuierliche) 0- und 1-Zyklen ↓ (3) Zählen Sie, wie viele Einsen es vom Ende gibt (weil die Zykluslänge gerade ist) ↓ (4) Sie können (3) verstehen, indem Sie die Anzahl der Grenzen berücksichtigen, an denen die Periode wechselt **

Beachten Sie außerdem, dass bei b = 0 das Argument von log2 zu 0 und zu RE wird. Ich wurde erwischt.

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)

Writer-Lösung

Wenn Sie XORs mit mehreren Zahlen berechnen, konvertieren Sie diese in Binärzahlen und zählen Sie, wie viele Einsen für jedes Bit vorhanden sind. Wenn die Anzahl der Einsen ungerade ist, ist sie 1 und wenn sie gerade ist, ist sie 0. Sie kann in Bits berechnet werden. Daraus können Sie ersehen, dass wenn Sie XOR für ** aufeinanderfolgende zwei ganze Zahlen k und k + 1 nehmen (k ist gerade), diese bis auf das 0. Bit gleich sind, sodass das Ergebnis von XOR 1 ** ist. Daher ist es nicht notwendig, alle XORs von A nach B der Reihe nach zu betrachten, sondern die Paare (k, k + 1) (k ist eine gerade Zahl) von A nach B zu zählen und die Gesamtgleichmäßigkeit und Seltsamkeit der Paare zu berücksichtigen. Sie können das XOR leicht von A nach B finden. Zu diesem Zeitpunkt wurden die Fälle jedoch aufgeteilt, indem darauf geachtet wurde, ob A und B in der Menge enthalten waren. Der Code sieht folgendermaßen aus:

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