[PYTHON] Codeforces Runde # 600 (Div. 2) Bacha Review (10/21)

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Bachas Kritik hat nicht aufgeholt, weil ich mich kurz zuvor auf die heutige Abschlussankündigung vorbereitet habe. Ich möchte eine Person sein, die Abschlussforschung und Wettbewerbsprofis in Einklang bringen kann.

Ich werde mich auch nicht auflösen, weil die Bewertung nicht aufholt. Ich werde ab morgen mein Bestes geben.

Problem A

Ich werde nicht auf die Details des Problems eingehen, sondern erwägen, $ a $ und $ b $ in einer einzigen Operation auszugleichen.

Wenn ** das Problem umschreibt ** und die ungleichen fortlaufenden Teile von $ a $ und $ b $ genommen werden, ist die Anzahl der Teile eins, wenn die Anzahl der Teile zwei oder mehr beträgt NEIN sollte ausgegeben werden, wenn (die Unterschiede innerhalb des Teils sind nicht gleich oder die Differenz innerhalb des Teils ist $ b \ _i-a \ _i \ <0 $), und JA sollte zu anderen Zeiten ausgegeben werden.

Die ungleichen zusammenhängenden Teile von $ a $ und $ b $ können leicht extrahiert werden, indem die Funktion ** groupby verwendet wird, um zu bestimmen, ob $ b \ _i-a \ _i = 0 $ ** ist. Es ist auch nicht schwierig, ① und ② zu beurteilen, solange dieser kontinuierliche Teil extrahiert werden kann.

A.py

from itertools import groupby
for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    b=list(map(int,input().split()))
    c=[a[i]-b[i] for i in range(n)]
    d=[[i,list(j)] for i,j in groupby(c,key=lambda x:x==0) if i==False]
    if len(d)>=2:
        print("NO")
    elif len(d)==0:
        print("YES")
    else:
        l=len(d[0][1])
        for i in range(l):
            if d[0][1][i]!=d[0][1][0]:
                print("NO")
                break
        else:
            if d[0][1][i]>0:
                print("NO")
            else:
                print("YES")

B-Problem

Wenn Sie das Problem nicht lösen, ist es fast $ O (n ^ 2) $. Implementieren Sie es daher sorgfältig. Auch dieses Mal müssen wir nicht über die maximale oder minimale Anzahl von Tagen nachdenken, also machen wir einfach eine einfache Simulation **.

Es gibt auch einige Bedingungen, also stellen Sie sicher, dass Sie sie ausschreiben. Bitte verzeihen Sie mir, obwohl sich der Ausdruck geringfügig von der Problemstellung unterscheidet. Wenn das Folgende nicht für jede Eingabe- / Ausgabeinformation gilt, gilt es als Tag.

① Wenn nur eines von + und - (+) angezeigt wird ② Wenn +, - (+) mehr als einmal erscheint ③ Wann-erscheint vor +

Zu diesem Zeitpunkt wird sofort entschieden, dass der Tag gilt, um zu vermeiden, dass die Bedingung (2) mehr als einmal auftritt, wenn sie als ** Tag gilt. Diese Erklärung ist nicht leicht zu verstehen, daher wird die Implementierung unten erläutert.

$ s: $ Eine Gruppe von Leuten, die bereits gekommen sind $ b: $ Eine Gruppe von Menschen, die noch nicht zurückgekehrt sind $ now: $ Index der angegebenen Eingabe- / Ausgabeinformationen, die Sie anzeigen (weniger als $ n $) $ ans: $ Letzter Index der Eingabe- / Ausgabeinformationen für einen Tag

Wenn Sie die obigen vier vorbereiten, können Sie einfach die folgenden ** Fälle ** machen.

(1) Wenn $ a [jetzt] > 0 $ [1] Wenn $ a [jetzt] $ in $ s $ enthalten ist Da + zweimal erscheint, ist ② nicht erfüllt. Ausgänge -1. [2] Wenn nicht enthalten Fügen Sie $ a [jetzt] $ zu $ s $ und $ b $ hinzu.

(2) Wenn $ a [jetzt] \ <0 $ [1] Wenn $ -a [jetzt] $ nicht in $ b $ enthalten ist Da-zuerst erscheint oder +, - bereits erscheint, ist weder ② noch ③ erfüllt. Ausgänge -1. [2] Wenn enthalten Schließen Sie $ -a [jetzt] $ von $ b $ aus.

Wenn ** $ b $ leer ist, gilt es als Tag **. Löschen Sie also den gesamten Inhalt von $ s $ und fügen Sie $ now $ zu $ ans $ hinzu.

Wenn $ b $ nach Durchführung der obigen Fallklassifizierung in der Reihenfolge mit beliebigen Eingabe- / Ausgabeinformationen nicht leer ist, ist ① nicht erfüllt. In diesem Fall wird -1 ausgegeben.

Da die Ausgabe ** die Länge ist, in der die Eingabe- / Ausgabeinformationen geteilt werden **, sollten $ ans [i] -ans [i-1] $ in aufsteigender Reihenfolge von $ i $ ausgegeben werden.

(Es ist eine lange Erklärung, aber ich denke nur an die Bedingungen ** ① bis ③ und was als Variable benötigt wird **.)

B.py

n=int(input())
a=list(map(int,input().split()))
#Leute, die schon gekommen sind
s=set()
#Diejenigen, die jetzt loswerden müssen
b=set()
#Bis zu welchem Tag
now=0
#Reihe von Antworten
ans=[]
while now<n:
    if a[now]>0:
        if a[now] in s:
            print(-1)
            exit()
        else:
            s.add(a[now])
            b.add(a[now])
    else:
        if -a[now] not in b:
            print(-1)
            exit()
        else:
            b.remove(-a[now])
    if len(b)==0:
        ans.append(now+1)
        s=set()
    now+=1
if len(b)!=0:
    print(-1)
    exit()
for i in range(len(ans)-1,0,-1):
    ans[i]-=ans[i-1]
print(len(ans))
print(" ".join(map(str,ans)))

C-Problem

** Ich war durch die Problemstellung verwirrt **, aber wenn Sie ruhig denken, ist es ein Problem mit vielen offensichtlichen Teilen.

Erwägen Sie die Auswahl eines $ k $ Stücks. Zu diesem Zeitpunkt ist es am besten, ** $ k $ Stücke ** aus den kleinsten auszuwählen. Wenn Sie $ k $ Stücke auswählen, ist es außerdem am besten, an jedem Tag ** $ m $ Stücke in absteigender Reihenfolge der Süße ** auszuwählen. Wenn Sie also an $ m = 2 $ denken, ist dies wie in der folgenden Abbildung dargestellt. (Der Doppelpfeil steht für $ m $ Stücke, der eingekreiste Teil ist der Tag, an dem jede Süßware ausgewählt wird, und der rot dargestellte Teil ist der Änderungsbetrag.)

In Anbetracht der Bewegung des Abschnitts der Länge ** $ m $ ** in der obigen Abbildung wird durch Erhöhen von $ k $ das Inkrement der Gesamtsüße der Index ** mit dem Rest von ** $ m $ sein. (** Paraphrase mit einem hohen Abstraktionsgrad! **). Mit anderen Worten, der Rest der Division des Index (0-indiziert) durch $ m $ ist in $ k $ der Indizes enthalten, die $ (k-1) \% \ m $ sind. Dies kann auch leicht berechnet werden, indem die kumulative Summe der Reste für jeden Index genommen wird. Da die kumulative Summe das Inkrement ist, können Sie die Antwort für jedes $ k $ finden, indem Sie die kumulative Summe am Ende nehmen.

(✳︎)… Da das Inkrement die kumulative Summe jedes Restes während des Bachacons ist, dachte ich, dass ich die Indizes hier bekommen könnte.

C.py

n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
tod=[[] for i in range(k)]
for i in range(n):
    tod[i%k].append(a[i])
from itertools import accumulate
for i in range(k):
    tod[i]=list(accumulate(tod[i]))
ans=[]
now=0
for i in range(n):
    now+=tod[i%k][i//k]
    ans.append(now)
print(" ".join(map(str,ans)))

D Problem

Es könnte mein Lieblingsproblem mit UnionFind sein.

Es ist leicht zu erkennen, was zu tun ist, daher werde ich mein Bestes geben, um es gut umzusetzen.

Wenn $ (l, r) $ verbunden ist, sind auch $ (l, l + 1) $, $ (l, l + 2) $… $ (l, r-1) $ verbunden, dh * * Alle Knoten mit Zahlen in $ [l, r] $ müssen sich in derselben verketteten Komponente befinden **. Da Beispiel 1 in diesem Fall leicht zu verstehen ist, sieht es wie folgt aus.

1-2-5-7
3-4-6-8
9
10
11-12

Zu diesem Zeitpunkt ist $ (1,7) $ verbunden, daher müssen die Knoten mit den in $ [1,7] $ enthaltenen Nummern dieselbe Verbindungskomponente haben. Das heißt, die erste und die zweite Verknüpfungskomponente müssen dieselbe Verknüpfungskomponente sein, und die Antwort lautet 1.

1-2-3-4-5-6-7-8
9
10
11-12

Führen Sie daher zuerst Union Find aus, um die verknüpften Komponenten zu trennen. Nach dem Ausführen von Union Find müssen die verbundenen Komponenten mindestens so oft miteinander verbunden werden, dass das Thema erfüllt wird. Wenn hier $ l $ und $ r $ verbunden sind, sind alle in $ [l, r] $ enthaltenen Knoten verbunden, sodass nur der Knoten mit der kleinsten und größten ** Nummer der verketteten Komponente gespeichert wird. Du kannst es schaffen **.

Wenn also laut UnionFind $ l \ _i $ der minimale Wert und $ r \ _i $ der maximale Wert für die $ i $ -te verkettete Komponente ist, dann ist $ [l \ _1, r \ _1], [l \ _2, Sie können das Intervall r \ _2], ... [L \ _ k, r_k] $ erhalten.

Wenn Sie diese Abschnitte in aufsteigender Reihenfolge von ** $ l $ ** (✳︎) anordnen, gilt ** $ hashi > l \ _i $, indem Sie das rechte Ende des Abschnitts festlegen, das dieselbe Verbindungskomponente wie $ hashi $ haben soll $ [l \ _i, r \ _i] $ muss ebenfalls dieselbe verkettete Komponente ** sein. Zu diesem Zeitpunkt wird sie als $ hash = max (hashi, r \ _i) $ aktualisiert.

Im Gegensatz dazu ist im Fall von $ hashi \ <l \ _i $ ** keine Aktualisierung erforderlich und der Betreff ist erfüllt **. Wenn Sie also die Anzahl der in dieser verknüpften Komponente enthaltenen ursprünglichen verknüpften Komponenten in $ now $ speichern , $ Now-1 $ ist die Mindestanzahl von Seiten, die zum Erstellen dieser Verbindungskomponente erforderlich sind. (Aktualisieren Sie gleichzeitig die Werte von $ hashi $ und $ now $ für die nächste verkettete Komponente, die Sie überprüfen möchten.)

Wenn die Mindestanzahl zusätzlicher Seiten, die Sie als Antwort finden möchten, $ ans $ ist, können Sie die Antwort finden, indem Sie in einem beliebigen Abschnitt nachsehen und $ now-1 $ zu $ ans $ hinzufügen und dann $ ans $ hinzufügen. Sie müssen es nur ausgeben.

(✳︎)… Wenn Sie über das Zusammenführen von Abschnitten nachdenken, ist es üblich, nach dem linken oder rechten Rand zu sortieren **

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 Endungen)、のどちらOder
//Wenn es kein D gibt, wird die Schleifenvariable um 1 erhöht, und wenn es ein D gibt, wird die Schleifenvariable 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

//Unten repräsentieren die Primzahl und der Baum dasselbe.
class UnionFind{
public:
    vector<ll> parent; //parent[i]Ist der Elternteil von i
    vector<ll> siz; //Ein Array, das die Größe der Primmenge darstellt(Initialisieren Sie mit 1)
    map<ll,set<ll>> group; //Nach Set verwalten(key:Repräsentant der Menge, Wert:Ein Array von Elementen der Menge)
    ll n; //Elementanzahl

    //Konstrukteur
    UnionFind(ll n_):n(n_),parent(n_),siz(n_,1){ 
        //Initialisieren, da die Wurzel aller Elemente selbst ist
        for(ll i=0;i<n;i++){parent[i]=i;}
    }

    //Holen Sie sich die Wurzel des Baums, zu dem Daten x gehören(Führen Sie auch eine Routenkomprimierung durch)
    ll root(ll x){
        if(parent[x]==x) return x;
        return parent[x]=root(parent[x]);//Da der Wert des Zuweisungsausdrucks der Wert der zugewiesenen Variablen ist, kann die Route komprimiert werden.
    }

    //X- und y-Bäume zusammenführen
    void unite(ll x,ll y){
        ll rx=root(x);//x root
        ll ry=root(y);//Wurzel von y
        if(rx==ry) return;//Wenn im selben Baum
        //Kleine Menge zu großer Menge zusammenführen(Zusammengeführt von ry zu rx)
        if(siz[rx]<siz[ry]) swap(rx,ry);
        siz[rx]+=siz[ry];
        parent[ry]=rx;//Wenn sich x und y nicht im selben Baum befinden, hängen Sie y root ry an x root rx an
    }

    //Bestimmen Sie, ob der Baum, zu dem x und y gehören, identisch ist
    bool same(ll x,ll y){
        ll rx=root(x);
        ll ry=root(y);
        return rx==ry;
    }

    //Ermitteln Sie die Größe der Primzahl von x
    ll size(ll x){
        return siz[root(x)];
    }

    //Gruppieren Sie jeden Primsatz
    void grouping(){
        //Führen Sie zuerst die Routenkomprimierung durch
        REP(i,n)root(i);
        //Mit Karte verwalten(Standard-Build verwenden)
        REP(i,n)group[parent[i]].insert(i);
    }

    //Löschen Sie das Prim-Set-System und initialisieren Sie es
    void clear(){
        REP(i,n){parent[i]=i;}
        siz=vector<ll>(n,1);
        group.clear();
    }
};

signed main(){
    //Ausgabespezifikation der Anzahl der Bruchstellen
    //cout<<fixed<<setprecision(10);
    //Code zur Beschleunigung der Eingabe
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n,m;cin>>n>>m;
    UnionFind uf(n);
    REP(i,m){
        ll u,v;cin>>u>>v;
        uf.unite(u-1,v-1);
    }
    uf.grouping();
    vector<pair<ll,ll>> segments;
    FORA(i,uf.group){
        segments.PB(MP(*i.S.begin(),*--i.S.end()));
    }
    sort(ALL(segments));
    ll hashi=segments[0].S;
    ll now=1;
    ll ans=0;
    FOR(i,1,SIZE(segments)-1){
        if(hashi<segments[i].F){
            ans+=(now-1);
            now=1;
            hashi=segments[i].S;
        }else{
            hashi=max(hashi,segments[i].S);
            now++;
        }
    }
    ans+=(now-1);
    cout<<ans<<endl;
}

Nach dem E-Problem

Ich werde diesmal überspringen.