[PYTHON] Codeforces Runde # 603 (Div. 2) Bacha Review (10/15)

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Ich konnte bis zu D lösen, aber E fühlte, dass er immer noch außer Reichweite war. Die Idee war, dass das E-Problem herauskam, aber die Implementierung explodierte. Ich finde es gut, dass ich D in dieser Zeit lösen konnte (obwohl C lange Zeit gebraucht hat, um ein Rätsel zu lösen). Außerdem war dieses Problem sehr schwer zu lesen, daher lehne ich Writer ab.

Problem A

Es schien intuitiv und schwer zu lösen zu sein. Im Folgenden werden wir mit der Diskussion als $ r \ <g \ <b $ fortfahren.

Zuerst habe ich die Politik verfolgt, eine Menge von $ g und b $ auszuwählen und den Rest mit $ r $ zu kombinieren, aber es war eine wunderbare Lügenlösung, ohne die Stichprobe zu bestehen. Aus der Idee, ** von den meisten zu kombinieren ** (TLE, wenn es dumm ist), kam ich auf die folgende Lösung (unbewiesen, aber wahrscheinlich richtig).

① Kombiniere $ g und b $ bis $ g = r $ Zu diesem Zeitpunkt kann nur $ m = g-r $ gepaart werden. Die für das Paar verwendeten $ g und b $ werden aktualisiert.

② Betrachten Sie eine Kombination unter $ r = g \ <b $

(1) Wenn $ r + g \ leqq b $ Zu diesem Zeitpunkt können sowohl $ r als auch g $ mit $ b $ kombiniert werden, sodass $ m + r + g $ ausgegeben wird.

(2) Wenn $ r + g> b $ $ r, g $ sind mit $ b $ versetzt. Das heißt, sowohl $ r als auch g $ können mit $ b $ durch $ [\ frac {b} {2}] $ kombiniert werden. Da die verbleibenden $ r und g $ dieselbe Zahl sind, können Sie auch $ r und g $ miteinander kombinieren. Daher können Sie $ m + [\ frac {b} {2}] \ mal 2 + r (= m + [\ frac {b} {2}] \ mal 2 + g) $ ($ in dieser Formel) ausgeben. r, g $ ist der Rest).

A.py

for _ in range(int(input())):
    r,g,b=sorted(list(map(int,input().split())))
    m=g-r
    g-=m
    b-=m
    #print(r,g,b)
    if r+g<=b:
        print(m+r+g)
    else:
        n=b
        r-=n//2
        g-=n//2
        print(m+n//2*2+r)

B-Problem

Da ** $ n $ höchstens 10 ** beträgt, können Sie alles anders machen, indem Sie nur eine Ziffer ändern. Daher beträgt die Mindestanzahl der Änderungen (die Anzahl derselben PIN) -1, und Sie können sie im Wörterbuch als (PIN, Nummer) speichern und zählen. ** Generieren Sie außerdem eine PIN, damit die neue nicht mit der ursprünglichen übereinstimmt. Sie können jedoch das obige Wörterbuch verwenden und es mindestens so oft ändern, dass nur die erste Ziffer nicht abgedeckt wird. .. Die Idee selbst ist einfach, also werde ich mein Bestes geben, indem ich ** die Implementierung entwerfe **.

B.py

for _ in range(int(input())):
    n=int(input())
    d=dict()
    c=[]
    for i in range(n):
        x=input()
        if x in d:
            d[x]+=1
        else:
            d[x]=1
        c.append(x)
    ans=0
    for i in d:
        ans+=(d[i]-1)
    ansa=[]
    for i in range(n):
        if d[c[i]]==1:
            ansa.append(c[i])
            continue
        for j in range(10):
            x=f"{j}"+c[i][1:]
            if x not in d:
                d[c[i]]-=1
                d[x]=1
                ansa.append(x)
                break
    print(ans)
    for i in range(n):
        print(ansa[i])

C-Problem

Ich bin aus irgendeinem Grund süchtig danach. Diese Art von Problem sollte Ihnen gefallen ...

Da $ n $ auf $ [\ frac {n} {k}] $ festgelegt ist, werden wir experimentieren, um das Verhalten durch Verschieben von ** $ k $ ** zu sehen. Hier ist $ n $ in der Stichprobe klein und das Verhalten kann nicht erfasst werden. Wenn Sie also an $ n = 100 $ denken, ist dies wie folgt. Auch [] wird weggelassen.

Dann können Sie sehen, dass die Antworten bei $ k \ geqq 8 $ fortlaufend sind. Daher wird ** angenommen, dass alle Zahlen nach der fortlaufenden Zahl bis 0 fortlaufend sind **, alle aufgelistet werden, bis die fortlaufenden erscheinen, und danach werden sie in der Reihenfolge bis 0 aufgelistet und die aufsteigende Sortierung wird ausgegeben. Ich habe mich dazu entschlossen. Auch wenn ich es nicht bewiesen habe, betrachte den Graphen von ** $ f (k) = \ frac {n} {k} $ ** und die Steigung wird kleiner, wenn $ k $ zunimmt und $ k $ wird Es ist selbstverständlich, dass es sich allmählich 0 nähert, wenn es größer wird.

C.py

for _ in range(int(input())):
    n=int(input())
    ans=[]
    i=1
    while i<n:
        if len(ans)!=0:
            if ans[-1]==n//i:
                break
        ans.append(n//i)
        i+=1
    if len(ans)==0:
        print(2)
        print("0 1")
        continue
    for i in range(ans[-1]-1,-1,-1):
        ans.append(i)
    print(len(ans))
    print(" ".join(map(str,ans[::-1])))

D Problem

Ich dachte, D sei einfacher als C. Einfach umsetzen. Es hat lange gedauert, weil $ a, b, c $ in der Problemstellung auftauchten und ich mit dem Alphabet verwechselt wurde.

Um die Problemstellung kurz zusammenzufassen: Zusätzlich zu der Tatsache, dass diejenigen, die dasselbe Alphabet enthalten, als dasselbe Passwort angesehen werden können, enthalten die Passwörter von ○, △, □ dasselbe Alphabet zwischen ○, △ und zwischen △, □. Wenn dasselbe Alphabet in ○, △, □ enthalten ist, kann dies als dasselbe Passwort angesehen werden.

Wenn Sie also an ** denselben Satz mit denselben Passwörtern ** denken, können Sie die Anzahl der Sätze ** im Elementarsatzsystem zählen, sodass Sie an Union Find denken können.

Wir müssen nur dasselbe Alphabet einfügen, also schauen wir für jedes Passwort, ob es die Alphabete $ a $ ~ $ z $ enthält. Speichern Sie es dann als $ ca [i]: = $ (ein Array, das den Index der Passwörter enthält, die das Alphabet $ i $ enthalten). Dann müssen Sie nur alle Elemente in jedem Array vereinen, damit Sie die Elemente (Indizes) vor und nach ** in diesem Array ** vereinen können. Wenn Sie dies in einem beliebigen Alphabet tun und dann die Gruppenfunktion aufrufen, ist die Größe der Gruppe die Antwort. Wenn Sie die im Array gespeicherte Schleife von der zu vereinigenden Schleife trennen, können Sie außerdem Verwirrung bei der Implementierung vermeiden.

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

//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,vector<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
    }

    //Stellen Sie fest, 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]].PB(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(){
    //Code zur Beschleunigung der Eingabe
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n;cin>>n;
    UnionFind uf(n);
    vector<vector<ll>> alp(26);
    REP(i,n){
        string s;cin>>s;
        vector<bool> ca(26);
        FORA(i,s){
            ca[ll(i-'a')]=true;
        }
        REP(j,26){
            if(ca[j])alp[j].PB(i);
        }
    }
    REP(i,26){
        ll l=SIZE(alp[i]);
        if(l==0 or l==1)continue;
        REP(j,l-1){
            uf.unite(alp[i][j],alp[i][j+1]);
        }
    }
    uf.grouping();
    cout<<SIZE(uf.group)<<endl;
}

E Problem

Ich werde diesmal nicht auflösen, weil ich die Implementierung fehlerhaft und verwelkt gemacht habe. Die Lösung wird unten beschrieben.

** Da es sich um eine Klammer handelt, ist es eine Bedingung, dass sie immer 0 oder mehr ist und das letzte Element 0 ist, wenn die kumulative Summe mit (+1,) als -1 genommen wird **. Durch Umschreiben der Klammern an der Position des Cursors ** ändert sich außerdem die kumulative Summe nach dieser Position gleichmäßig im Bereich von -2 bis 2 **. Sie müssen auch die maximale Verschachtelungstiefe ermitteln, wenn die Klammern gelten. Dies ist ** das Maximum der kumulierten Summen **.

Daher kann es gelöst werden, indem die Position des Cursors, die aktuelle Zeichenfolge und die beiden Segmentbäume RMQ (min) und RMQ (max) zum Aktualisieren des Intervalls verwendet werden. Ich hatte jedoch keinen Seg-Baum, also habe ich ihn fehlerhaft gemacht. Ich denke darüber nach, eine verbesserte Version des Seg-Baums zu verwenden, die von ACL oder dem Seg-Baum einer anderen Person bereitgestellt wird, aber die Implementierung ist nicht einfach. Vielleicht werde ich es beibehalten, wenn ich Lust dazu habe.

Nach F Problem

Ich werde diesmal überspringen.