[PYTHON] Codeforces Runde # 652 (Div. 2) Bacha Review (8/24)

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Dieses Mal habe ich das Gefühl, dass ich es lösen konnte, wie ich wollte. Die Geschwindigkeit ist jedoch immer noch unzureichend, daher möchte ich den Lösungssinn verbessern.

Problem A

Rückblickend auf das Problem, da es gut wäre, wenn es parallele Seiten gäbe, wurde gesagt, dass es mindestens eine Seite parallel zur $ X $ -Achse und parallel zur $ Y $ -Achse geben sollte, sodass die Anzahl der Seiten vier beträgt. "JA" wurde nur ausgegeben, wenn es ein Vielfaches von war. Ich habe es mit einer grafischen Idee durch den Wettbewerb geführt, aber es ist leicht zu beweisen, wenn man auf den zentralen Winkel achtet.

A.py

for i in range(int(input())):
    n=int(input())
    print("YES"if n%4==0 else "NO")

B-Problem

Es scheint, dass es mit einer erheblich schnelleren Geschwindigkeit als die Umgebung gelöst wurde. Es tut mir jedoch leid, weil ich mich in der Implementierung etwas verlaufen habe. Für (binäre) ** Strings ist es besonders wichtig, mit Samples zu experimentieren, um ein Gefühl für sie zu bekommen **.

Da eines der beiden benachbarten Zeichen "10" gelöscht wird, kann ** die 0, die am linken Ende fortlaufend ist, und die 1, die am rechten Ende fortlaufend ist, nicht gelöscht werden ** (ich denke, es ist leicht zu verstehen, wenn Sie sich das erste Beispiel ansehen). Ich werde.). Daher habe ich versucht, die Anzahl solcher Elemente in $ l und r $ zu speichern. Wenn ** alle Elemente in einem zusammenhängenden Teil (✳︎) ** enthalten sind, kann dies nicht gekürzt werden, sodass die angegebene Zeichenfolge so ausgegeben wird, wie sie ist.

Wenn Sie den fortlaufenden Teil am linken und rechten Ende ignorieren, wird die folgende Zeichenfolge angezeigt. (Da das Muster von (✳︎) ausgeschlossen ist, erscheinen immer eine oder mehrere Einsen am linken Ende und eine oder mehrere Nullen am rechten Ende.)

11…00

Eine solche Zeichenkette kann schließlich im Zustand "10" belassen werden, indem die Reihenfolge der zu löschenden Zeichen angepasst wird. Hier **, wenn die Längen gleich sind, sind sie in lexikalischer Reihenfolge kleiner **, daher ist es am besten, 1 zu löschen und 0 zu belassen, und die auszugebende Zeichenfolge ist (fortlaufende 0 am linken Ende) +0. + (Fortlaufend 1) am rechten Ende.

B.py

for i in range(int(input())):
    n=int(input())
    s=input()
    if all([i=="1" for i in s]) or all([i=="0" for i in s]):
        print(s)
        continue
    #l,r muss sein
    l,r=-1,n
    for i in range(n):
        if s[i]=="1":
            l=i
            break
    for i in range(n-1,-1,-1):
        if s[i]=="0":
            r=i
            break
    if l>r:
        print(s)
        continue
    print(s[:l]+"0"+s[r+1:])

C-Problem

Erwägen Sie, das Glück aller zu maximieren. Zu diesem Zeitpunkt dachte ich über die ** Giermethode ** nach, während ich darüber nachdachte, Elemente zu verwenden, die sowohl für max als auch für min so groß wie möglich sind. Das heißt, bedenken Sie, dass ** kleine Elemente so viel wie möglich verbraucht werden **, um "min" zu erhöhen, und ** große Elemente so wenig wie möglich verbraucht werden **, um "max" zu erhöhen. Das heißt, Sie können wie folgt denken.

Ordnen Sie $ a \ _i $ und $ w \ _i $ in absteigender Reihenfolge an. Wählen Sie für jedes $ w \ _i $ max das größte verbleibende Element aus und entfernen Sie es. Wählen Sie dann $ w \ _i-1 $ Teile aus und entfernen Sie sie in aufsteigender Reihenfolge aus den verbleibenden Elementen. Zu diesem Zeitpunkt ist "min" das kleinste Element. Auf diese Weise kann max die größten $ k $ Stücke ** in ** $ a \ _i $ auswählen und ** zuerst die kleinsten Elemente so viel wie möglich ** verbrauchen. Mit können Sie eine Maximierung anstreben.

Was Sie hier jedoch beachten sollten, ist, wenn ** $ w \ _i = 1 $ **. Zu diesem Zeitpunkt stimmen ** max und min überein **. Wenn Sie also ein großes Element auswählen, können Sie das doppelte Glück dieses Elements auswählen. Wenn daher $ w \ _i = 1 $ ist, wählen Sie im Voraus ein großes Element aus.

C.py

from collections import deque
for _ in range(int(input())):
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort(reverse=True)
    a=deque(a)
    w=list(map(int,input().split()))
    w.sort(reverse=True)
    #Prozess 1 zuerst
    ans=0
    for i in range(w.count(1)):
        ans+=2*a.popleft()
    for i in range(k-w.count(1)):
        p=a.popleft()
        ans+=p
        #print(p)
        for j in range(w[i]-1):
            p=a.pop()
            if j==0:
                ans+=p
                #print(p)
    print(ans)

D Problem

Vorläufig dachte ich, indem ich ein Diagramm zeichnete, um zu wissen, um welche Art von Baum es sich handelt. Zu diesem Zeitpunkt nahmen die Eckpunkte in der Reihenfolge Rot → Gelb → Blau → Grün → Rot zu, und ich verstand, dass es sich um einen ** Baum handelt, der rekursiv aus der Wurzel ** bestimmt wird (er kann auch als fraktale Figur bezeichnet werden).

Wenn Sie sich die Klaue ansehen (ein Teilbaum, dessen drei Seiten von einer Wurzel ausgehen), sind auch ** Klauenwurzeln in der Klaue enthalten **. Daher ist es möglich, nur die Klaue zu malen, die zum Zeitpunkt $ n $ erstellt wurde, und (die Anzahl der Wurzeln der Klaue, die zum Zeitpunkt $ n $ erstellt wurde) $ \ times $ 4 ist die Anzahl der Scheitelpunkte, die gelb gestrichen werden können. Es war (✳︎).

Hier kann ** es rekursiv aus der Wurzel bestimmt werden und ** es gibt drei Zustände der Spitze ** (ob es keine Blätter, ein Blatt oder drei Blätter hat). Wenn Sie sich darauf konzentrieren, ist es einfach zu implementieren, wenn Sie es als dp betrachten. Definieren Sie DP daher wie folgt:

$ dp [i] [j]: = $ (Wie viele Scheitelpunkte befinden sich vom ersten Versuch $ i $ im Zustand $ j $)

Es hat jedoch kein Blatt, wenn $ j = 0 $ ist, hat ein Blatt, wenn $ j = 1 $ ist, und hat drei Blätter, wenn $ j = 2 $.

Zu diesem Zeitpunkt ist die Änderung der DP wie folgt. (Wenn der Übergang von DP wie dieses Problem schwer zu verstehen ist, ist er durch Tabellieren des Übergangs ** leicht zu verstehen.)

Wenn dies in Code transkribiert wird, sieht es so aus:

dp[i][0]+=dp[i-1][0]
dp[i][1]+=dp[i-1][0]
dp[i][0]+=dp[i-1][1]*2
dp[i][2]+=dp[i-1][1]
dp[i][2]+=dp[i-1][2]

Wenn Sie (✳︎) verwenden, ist $ (dp [i] [2] -dp [i-1] [2]) \ times 4 $ die Antwort, aber ** $ n $ die dritte Klaue Ansonsten kann gemalt werden **, so dass einige der Proben nicht bestanden haben. In Anbetracht der folgenden Abbildung können Sie, wenn Sie die zum $ n $ -ten Zeitpunkt erstellte Klaue anwenden, die zum ** $ n-3 $ -ten Zeitpunkt erstellte Klaue auf die höheren Klauen ** anwenden.

Daher ist die Klaue, die im Rooted Dead Bush angewendet werden kann, dessen Level $ n $ ist, "($ n $ claw) + ($ n-3 $ claw) + ($ n-6 $) Es wird die zweite Klaue sein) +… ”.

Auch in Bezug auf den Rechenaufwand ** reicht es nicht aus, den DP jedes Mal zu berechnen **, so dass das ** DP-Array bis zu $ 2 \ mal 10 ^ 6 $ vorberechnet wird ** und der (Index) des DP-Arrays berechnet wird. Die ** kumulative Summe (für jeden Wert von $ mod \ 3 $) muss ebenfalls in der Vorberechnung ** vorbereitet werden.

Außerdem schien die Vorberechnung von DP in meiner Implementierung zu viel Speicher zu beanspruchen und wurde zu MLE. Deshalb schrieb ich sie in ** C ++ um und nahm MLE **.

D.cc

//Debug-Optionen:-fsanitize=undefined,address

//Compileroptimierung
#pragma GCC optimize("Ofast")

//Einschließen usw.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//Makro
//für Schleife
//Das Argument ist(Variablen in der Schleife,Bewegungsumfang)Oder(Variablen in der Schleife,Erste Nummer,Anzahl der Enden)、のどちらOder
//Schleifenvariablen ohne D werden um 1 erhöht, und Schleifenvariablen mit D werden um 1 dekrementiert.
//FORA ist ein Bereich für Aussagen(Wenn es schwer zu bedienen ist, löschen Sie es)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//x ist ein Container wie ein Vektor
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//Konstante
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Gemeinsames Recht
#define MAXR 100000 //10^5:Maximale Reichweite des Arrays
//Abkürzung
#define PB push_back //Einfügen
#define MP make_pair //Paarkonstruktor
#define F first //Das erste Element des Paares
#define S second //Das zweite Element des Paares

signed main(){
    //Code zur Beschleunigung der Eingabe
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n=2000000;
    vector<vector<ll>> dp(n,vector<ll>(3,0));
    dp[0][0]=1;
    FOR(i,1,n-1){
        dp[i][0]+=dp[i-1][0];
        dp[i][1]+=dp[i-1][0];
        dp[i][0]+=dp[i-1][1]*2;
        dp[i][2]+=dp[i-1][1];
        dp[i][2]+=dp[i-1][2];
        dp[i][0]%=MOD;
        dp[i][1]%=MOD;
        dp[i][2]%=MOD;
    }
    vector<ll> ans(n,0);
    REP(i,3){
        if(i!=0){
            ans[i]+=(MOD+dp[i][2]-dp[i-1][2])*4;
            ans[i]%=MOD;
        }
        for(ll j=i;j<n-3;j+=3){
            ans[j+3]+=ans[j];
            ans[j+3]+=(MOD+dp[j+3][2]-dp[j+2][2])*4;
            ans[j+3]%=MOD;
        }
    }
    ll t;cin>>t;
    REP(i,t){
        cin>>n;
        cout<<ans[n-1]<<endl;
    }
}

Nach dem E-Problem

Ich werde diesmal überspringen