Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Ich denke, diesmal ist es gut gelaufen. Ich bin jedoch enttäuscht, weil ich das D-Problem nicht lösen konnte, das aufgrund der Überschneidung mit dem Mittagessen rechtzeitig gelöst zu sein schien. Es schien jedoch, dass ich das Problem auf dieser Ebene lösen konnte, also dachte ich, ich wäre ein wenig gewachsen. Dieses Mal konnte ich das Problem ruhig angehen, daher denke ich, dass dies der Grund für den Sieg ist.

Problem A

Basierend auf den gegebenen Werten von $ r, g, b, w $ wird beurteilt, ob jedes Zeichen in einem Kreis angeordnet ist oder nicht. Sie können auch $ r, g, b $ nacheinander auswählen und so weit wie möglich in $ w $ ändern, aber ** diese Operation ändert nicht die Gewinnchancen und Gewinnchancen von jedem **, also dies Sie müssen nur über zwei Möglichkeiten nachdenken, um dies einmal zu tun oder nicht.

Wenn darunter die Summe der Werte von $ r, g, b, w $ (die Länge der Transkription) gerade ist, ist jeder Wert von ** $ r, g, b, w $ gerade **. Wenn Sie eine haben, können Sie es schaffen. Durch einmaliges Ändern von $ r, g, b $ in $ w $ wird die Gerade und Seltsamkeit von ** $ r, g, b, w $ umgekehrt **, also $ r, g, b, w $ Sie können eine Auflage machen, wenn ein Wert ungerade ist.

Wenn andererseits die Länge der Zirkulation ungerade ist, muss nur eines von ** $ r, g, b, w $ ungerade sein **. In Anbetracht der Inversion von gerade und ungerade ist es auch möglich, eine Rezitation durchzuführen, selbst wenn nur eines von $ r, g, b, w $ gerade ist.

`A.py`


for _ in range(int(input())):
    r,g,b,w=map(int,input().split())
    if (r+g+b+w)%2==0:
        if r%2==0 and g%2==0 and b%2==0 and w%2==0:
            print("Yes")
        elif r%2==1 and g%2==1 and b%2==1 and w%2==1:
            print("Yes")
        else:
            print("No")
    else:
        x=[r%2,g%2,b%2,w%2]
        if x.count(1)==1:
            print("Yes")
        elif x.count(0)==1 and r>0 and g>0 and b>0:
            print("Yes")
        else:
            print("No")

B-Problem

Erwägen Sie, Schach wie Luke voranzutreiben und den Feldern auf einem beliebigen Gitter zu folgen. Selbst wenn Sie den dunklen Wolken folgen, öffnet sich das 埒 nicht. Denken Sie also daran, ** in einer bestimmten Reihenfolge zu folgen **.

Zuerst dachte ich, ich würde es in einem Whirlpool verfolgen, aber ich fand es umständlich zu implementieren, also dachte ich, ich würde es Zeile für Zeile folgen **. Mit anderen Worten, betrachten Sie Folgendes wie in der folgenden Abbildung gezeigt.

Hier müssen Sie nur (1) nach dem Verfolgen aller oberen Reihen ** weiter zur unteren Reihe zurückverfolgen ** und (2) ** beim Bewegen zwischen den Reihen ** in den Kontaktquadraten bewegen **. Seien Sie vorsichtig, die Implementierung sieht folgendermaßen aus:

① kann durch Verbinden mit list (Bereich (x, -1, -1)) + list (Bereich (x + 1, n)) implementiert werden, und ② gibt an, ob die Kontaktquadrate die Spalte ganz links oder die Spalte ganz rechts sind. Es kann implementiert werden, indem der Fall mit geteilt wird.

`B.py`


n,m,x,y=map(int,input().split())
x-=1;y-=1
ans=[]
ans.append([x,y])

now=0
for i in list(range(x,-1,-1))+list(range(x+1,n)):
    now=1-now
    if i==x:
        ans+=[[i,j] for j in range(m) if j!=y]
    else:
        if now:
            ans+=[[i,j] for j in range(m)]
        else:
            ans+=[[i,j] for j in range(m)][::-1]
for i in ans:
    print(i[0]+1,i[1]+1)

C-Problem

Zuerst dachte ich darüber nach, mich so zu entscheiden, dass die Bits nicht in der Reihenfolge von der oberen Ziffer stehen, aber ich hatte das Gefühl, dass es schwierig sein würde, sich gierig für die mittlere Ziffer zu entscheiden **.

Wenn Sie etwas (Nummer) wie dieses Problem auswählen, verbessern sich die Aussichten häufig, wenn Sie DP ** in Betracht ziehen. Darüber hinaus ist es auch ein entscheidender Faktor, dass die Bitberechnung, die das Speichern des Zustands erleichtert, und dass oder für jedes Bit von $ 0 \ leqq a_i, b_i <2 ^ 9 $ nur diesen Bereich einnimmt (** Begrenzung der Anzahl der Zustände **). Betrachten Sie daher den folgenden DP.

$ dp [i] [j]: = $ (Gibt es einen Fall, in dem es $ j $ ist, wenn oder für jedes Bit bis zu $ a_i $ genommen wird)

Wenn unter Berücksichtigung eines solchen DP $ dp [i-1] [j] = 1 $ und $ b_k (1 \ leqq k \ leqq m) $ für $ a_i $ ausgewählt ist, ist dies wie folgt. Wird sein.

dp[i][j\|(a\_i \\& b\_k)]=1

Daher kann dieser DP in ungefähr $ n \ mal m \ mal 2 ^ 9 $ mal berechnet werden, so dass Sie ein Programm schreiben können, das schnell genug ist.

`C.py`


n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
change=[[a[i]&b[j] for j in range(m)]for i in range(n)]
dp=[[0]*(2**9) for i in range(n)]

for i in range(n):
    if i==0:
        for k in range(m):
            dp[0][change[i][k]]=1
        continue
    for j in range(2**9):
        if dp[i-1][j]==1:
            for k in range(m):
                dp[i][j|change[i][k]]=1

for j in range(2**9):
    if dp[-1][j]==1:
        print(j)
        break

D Problem

Zuerst habe ich das Problem falsch verstanden und dachte, dass das Array $ a $ so verarbeitet wird, wie es ist. ** Wenn Sie sich das Beispiel ansehen, sollten Sie keinen Fehler gemacht haben **. Denken Sie also darüber nach und verwenden Sie es als nächstes (in diesem Fall können Sie es mit DP lösen).

Zunächst ist es offensichtlich, dass Sie aus dem größten auswählen möchten. Wenn zu diesem Zeitpunkt $ a \ _i> m $ ist, kann es am folgenden $ d $ -Tag nicht ausgewählt werden. Teilen Sie es daher zuerst in das Element ** $ a \ _i> m $ und das Element $ a \ _i \ leqq m $ auf. ** Speichern Sie im Array "e", "f". Es wird auch angenommen, dass "e" und "f" in absteigender Reihenfolge angeordnet sind.

Wenn Sie die Anzahl der Elemente kennen, die ** $ a \ _i> m $ sind, können Sie hier die Anzahl der Elemente kennen, die aus den Elementen ausgewählt werden können, die ** $ a \ _i \ leqq m $ sind, also ** $ a \ _i Nehmen wir an, dass es $ k $ Elemente gibt, die> m $ ** sind. Wie Sie leicht sehen können, ist $ k $ kleiner oder gleich "len (f)". In Anbetracht dessen, dass $ k $ $ a \ _i (> m) $ so angeordnet werden sollte, dass $ a \ _i (\ leqq m) $ so weit wie möglich ausgewählt werden kann, ist die folgende Anordnung optimal.

Daher kann zu diesem Zeitpunkt $ a \ _i (\ leqq m) $ aus $ n- $ {$ (k-1) \ times (d + 1) + 1 $} ausgewählt werden. Beachten Sie auch, dass $ (k-1) \ times (d + 1) + 1 \ leqq n $ erfüllt sein muss (das Maximum $ k $, das dies erfüllt, ist $ K '$). .. Selbst wenn ** $ n- $ {$ (k-1) \ times (d + 1) + 1 $} "len (e)" überschreitet, können nur die in "e" enthaltenen ausgewählt werden (✳︎). ) ** Bitte beachten Sie.

Wenn Sie ** $ k $ um 1 erhöhen, verringert sich die Zahl, die aus "e" ausgewählt werden kann, um $ d + 1 $ **, also ** $ k $ auf $ 0 $ ~ $ K '$, während Sie die Differenz verwalten ** Suchen Sie nach der größten Anzahl von ihnen. Außerdem erhöht sich $ k = 0 \ rightarrow 1 $ um $ 1 $ anstelle von $ d + 1 $. Betrachten Sie also $ k = 0 $ separat. Zu diesem Zeitpunkt sollten Sie die Summe von "e" berücksichtigen.

Auf diese Weise sollte der für jedes $ k $ erhaltene Maximalwert als Antwort ausgegeben werden.

(Ich habe es später bemerkt, aber ich denke, dass die Implementierung von (✳︎) klarer war, wenn ich versuchte, ** $ k $ zu reduzieren.)

`D.py`


n,d,m=map(int,input().split())
a=list(map(int,input().split()))
e,f=[i for i in a if i<=m],[i for i in a if i>m]
e.sort(reverse=True)
f.sort(reverse=True)
c=len(e)
if c==n:
    print(sum(a))
    exit()
#a[i]>m kann entsprechend bis max
l=1
r=min((n-1)//(d+1)+1,len(f))
#k's range 
#e,f 's sum
ans=sum(e)
nowe,nowf=0,0
for i in range(l,r+1):
    if i==l:
        nowe=sum(e[:n-(1+(l-1)*(d+1))])
        nowf=sum(f[:l])
        ans=max(nowe+nowf,ans)
        continue
    nowe-=sum(e[n-(1+(i-1)*(d+1)):n-(1+(i-1-1)*(d+1))])
    nowf+=f[i-1]
    ans=max(nowe+nowf,ans)
print(ans)

Nach dem E-Problem

Ich werde diesmal überspringen

[PYTHON] Codeforces Runde # 664 (Div. 2) Bacha Review (8/13)