[PYTHON] Codeforces Runde # 479 (Div. 3) Bacha Review (9/25)

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Das E-Problem war ein Implementierungsspiel, aber ich bedauere es, weil ich weiterhin Fehler gemacht habe, als ich es gewaltsam implementiert habe, ohne mir die endgültige Form der Implementierung vorzustellen. Es war gut, unterwegs zum F-Problem zu wechseln, aber es ist keine gute Idee, die Implementierung fallen zu lassen, obwohl die Richtlinie vollkommen korrekt ist. Deshalb werde ich wiederholt mit Kodofos Bacha trainieren.

Problem A

Es geht nur darum, die Zahl als Zeichenfolge zu betrachten und sie ehrlich zu simulieren. Ich war ein wenig verloren, weil es nicht viele solche Probleme gibt.

A.py

n,k=input().split()
n=[int(i) for i in n]
k=int(k)
for i in range(k):
    if n[-1]==0:
        n=n[:-1]
    else:
        n[-1]-=1
print("".join(map(str,n)))

B-Problem

Ich hatte ein wenig Probleme, die Bedeutung der Problemstellung zu verstehen, aber ich muss nur zählen, wie viele der beiden aufeinander folgenden Zeichen (im Folgenden einfach als Zeichenfolge bezeichnet) sind. Mit anderen Worten, wenn das Wörterbuch $ check [i]: = $ (es gibt mehrere Indexkombinationen, deren Zeichenketten $ i $ sind), gibt es $ n-1 $ Indexkombinationen, daher sollten alle $ check $ sein. Sie können es aufnehmen. Nach dem Speichern im Wörterbuch sollte das mit der größten Kombination von Indizes ausgegeben werden, und die Elemente im Wörterbuch werden in umgekehrter Reihenfolge sortiert, und das erste wird als Lösung verwendet.

B.py

n=int(input())
s=input()
check=dict()
for i in range(n-1):
    t=s[i:i+2]
    if t in check:
        check[t]+=1
    else:
        check[t]=1
c=list(check.items())
c.sort(key=lambda x:x[1],reverse=True)
print(c[0][0])

C-Problem

Es ist $ x \ in [1,10 ^ 9] $, also sollten Sie ** vorsichtig mit dem Eckfall sein ** (Ich habe bemerkt, dass ich 1WA ausgegeben habe, seien Sie vorsichtig ...).

Wenn $ x $ eine beliebige Ganzzahl annehmen kann, $ a \ _0, a \ _1, a \ _2, ..., a \ _ {k-1} \ leqq x, wenn die Sequenz $ a $ in aufsteigender Reihenfolge angeordnet wird Nehmen Sie einfach $ x $, also $ und $ x <a \ _k $. Da sie in aufsteigender Reihenfolge angeordnet sind, können Sie auch $ x $ nehmen, dh $ a \ _ {k-1} \ leqq x <a \ k $. Außerdem sollte ** $ x = a \ _ {k-1} $ gesetzt werden **, aber wenn $ a {k-1} = a \ _k $, ist die Bedingung nicht erfüllt, sodass -1 ausgegeben wird. Ich werde.

Wenn $ k = 0, n $, ** $ a \ _ {k-1} $ und $ a \ _k $ nicht vorhanden sind **, müssen die Fälle getrennt werden. Wenn $ k = n $ ist, ist $ a \ _ {max} $ höchstens $ 10 ^ 9 $, also $ x = 10 ^ 9 $. Wenn andererseits $ k = 0 $, $ a \ _0 = 1 $, $ x \ geqq 1 $ ist, ist die Bedingung nicht erfüllt. In anderen Fällen erfüllt $ a \ _0-1 $ die Bedingung. (1WA hat einen Fehler gemacht, als $ k = n $ ...)

C.py

n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
if k==0:
    if a[0]==1:
        print(-1)
    else:
        print(a[0]-1)
elif k==n:
    print(a[-1])
else:
    if a[k-1]==a[k]:
        print(-1)
    else:
        print(a[k-1])

D Problem

Ich dachte, es sei unerwartet schwierig, aber es war ein Problem auf D-Problemstufe.

(In der folgenden Richtlinie dachte ich, dass -1 ausgegeben werden würde, wenn es nicht auf halber Strecke existiert, also fuhr ich mit der Überlegung fort, sodass es einige redundante Punkte gibt, aber bitte machen Sie sich keine Sorgen.) (Ich habe es falsch verstanden, aber das Problem der Person, die es falsch gelesen hat Wenn du machst ** Es scheint, dass du ein Problem auf der Ebene der ersten Hälfte von Grün machen kannst **.)

$ x $ kann nur durch 3 geteilt oder mit 2 multipliziert werden. Zum Beispiel kann es im Fall von $ 4,6 $ nicht durch Operation erstellt werden, aber ** Eingabe ist immer zufrieden ** (selbst wenn Sie denken, dass es möglicherweise nicht existiert und das Problem löst, können Sie es schließlich lösen. Die Implementierung wird jedoch leicht reduziert.

Wenn Sie zunächst auf die Operation "Teilen durch 3" unter den Operationen achten, ist das Subjekt nicht zufrieden, wenn das Vielfache von 3 beim Teilen durch 3 noch vorhanden ist und es kein Vielfaches von 3 mehr ist. Mit anderen Worten, aus der Operation des Teilens durch 3 können wir sehen, dass, wenn jedes ein Vielfaches von $ 3 ^ i $ ist, das größte ** $ 3 ^ i $ betrieben werden sollte **. Anhand der Multiplikation mit 2 können Sie auch erkennen, dass Sie mit dem kleinsten ** $ 2 ^ i $ ** arbeiten sollten.

Finden Sie daher heraus, wie oft $ a \ _i $ durch $ 2,3 $ als $ x \ _i, y \ _i $ geteilt werden kann, beginnend mit dem mit dem kleinsten ** $ x \ _i $ und dem größten $ y \ _i $. Prozess ** in der Reihenfolge (✳︎). Wenn Sie in dieser Reihenfolge verarbeiten, können Sie immer in der Reihenfolge sortieren, die das Thema unter den Bedingungen dieses Problems erfüllt, und in dieser Reihenfolge ausgeben.

(✳︎)… Wenn es nicht existiert, betrachten Sie GCD hier, aber es ist hier nicht notwendig.

D.py

from math import gcd
def gce(x):
    ret=x[0]
    for i in x:
        ret=gcd(ret,i)
    return ret
n=int(input())
a=list(map(int,input().split()))
g=gce(a)
a=[i//g for i in a]
b=[]
for i in range(n):
    d=[0,0]
    c=a[i]
    while c%2==0:
        c//=2
        d[0]+=1
    while c%3==0:
        c//=3
        d[1]+=1
    b.append(d)
b.sort(key=lambda x:x[0])
b.sort(reverse=True,key=lambda x:x[1])
ans=[]
for i in range(n):
    ans.append(str((2**b[i][0])*(3**b[i][1])*g))
print(" ".join(ans))

E Problem

Ich habe es in C ++ geschrieben, weil ich dachte, ich brauche DFS (rekursiv), aber am Ende habe ich es in BFS implementiert. Ich habe viele dumme Fehler gemacht, aber wie gesagt, ich glaube, das lag daran, dass ich mir kein Bild von der endgültigen Form der Implementierung machen konnte **.

Wenn Sie die Problemstellung lesen, haben Sie eine Richtlinie. Es ist ein bisschen lang, aber es erklärt nur, dass es sich um einen gängigen Diagrammtyp ohne Schleifen (die Seiten, die ihn verbinden) und ohne mehrere Seiten handelt. Was wir in dieser Frage fragen sollten, ist ** wie viele Verknüpfungskomponenten existieren, die in nur einem Zyklus hergestellt werden **. Hier müssen wir die Eigenschaften des Zyklus erfassen, bevor wir ihn implementieren. Die Figur ist wie folgt.

Außerdem verwende ich immer UnionFind, wenn ich die Verknüpfungskomponente finde, aber hier habe ich beschlossen, ** BFS zu verwenden, um an die Verknüpfungskomponente zu denken, die das Thema erfüllt **. Wenn in der obigen Abbildung ein Punkt zum Zeitpunkt des BFS als Startpunkt festgelegt ist, ** bei der Verfolgung von diesem Startpunkt ** Wenn die Reihenfolge jedes Scheitelpunkts 2 ist und schließlich zum Startpunkt zurückkehrt <font color = "red" "> (✳︎) </ font> ** Man kann sagen, dass die Verbindungskomponenten nur einen Zyklus bilden. Obwohl ich dies nur implementieren musste, machte ich es fehlerhaft, so dass ich mir eine einfachere Implementierungsmethode ** überlegte.

Dann habe ich mir die folgende Implementierung ausgedacht. Ich denke, es ist eine Implementierung, die einem in den Sinn kommt, wenn man die Bedingungen berücksichtigt, die erfüllt sind, wenn der Zyklus festgelegt wird.

Wählen Sie zuerst den Startpunkt aus. Der Startpunkt kann ein beliebiger Scheitelpunkt sein, der nicht durchsucht wurde. In BFS ist es außerdem einfach, den Startpunkt in deque zu setzen, die Scheitelpunkte, die mit den Scheitelpunkten in deque verbunden sind und nicht durchsucht wurden, in deque zu setzen und zu wiederholen, bis keine Elemente in deque vorhanden sind. .. Diesmal ** möchte ich jedoch in der folgenden Reihenfolge suchen **, sodass diese Implementierung nicht funktioniert ($ , da $ vom Startpunkt aus in zwei Richtungen fortschreitet, wenn sie unverändert bleibt).

Nachdem Sie den Startpunkt festgelegt und durchsucht haben, ** berücksichtigen Sie daher, dass ein (nur) mit diesem Startpunkt verbundener Punkt gesucht wurde, und suchen Sie in der Reihenfolge von diesem Punkt aus . Bereiten Sie hier zusätzlich zu der bei der BFS-Suche verwendeten Deque (d) eine Deque ( e) vor, die in der Suchreihenfolge gespeichert ist. Nach Durchführung dieser BFS-Suche wird der obige Zyklus beurteilt. Zu diesem Zeitpunkt, da die Informationen der Scheitelpunkte in "e" in der Reihenfolge "Suche" enthalten sind, "Ist die Reihenfolge aller Scheitelpunkte in" e "2 enthalten?" Und "Beliebig von" e " Wenn Sie die beiden Punkte von " aufeinanderfolgende Eckpunkte und ob der Startpunkt und der Endpunkt verbunden sind **" überprüfen, wird der Zyklus beurteilt.

In der vorherigen BFS werden nur zwei (maximal) der vom Startpunkt aus verbundenen Scheitelpunkte durchsucht. Wenn die Reihenfolge 2 oder mehr beträgt, sind möglicherweise nicht durchsuchte Scheitelpunkte ** vorhanden, sodass der Startpunkt erneut durchsucht wird. Fügen Sie es in d ein und führen Sie BFS durch, um die ** verbleibenden Scheitelpunkte zu überprüfen, die in dieser verketteten Komponente ** enthalten sind.

Anhand der obigen Ausführungen kann beurteilt werden, ob jede verbundene Komponente ein Zyklus ist, sodass die Gesamtzahl die Antwort ist.

(Ich arbeite immer hart an der ersten Implementierung, die ich mir ausgedacht habe, aber manchmal dachte ich, es sei wichtig, einen Teil der Richtlinie zu ändern, um sie einfacher zu machen **. Nicht nur die Fähigkeit, sie zu implementieren, sondern auch ** klarer und fehlerhafter. Ich denke, dass es auch die Montagekraft ist, über eine einfache Implementierung nachzudenken, ohne es zuzulassen **, also werde ich versuchen, beide Montageleistungen zu gewinnen.)

Nachtrag (25.09.2020)

Die Bedingung, dass die verkettete Komponente zu einem Zyklus wird, wird als (✳︎) </ font> geschrieben, aber diese Bedingung ist ** der gleiche Wert wie die Reihenfolge eines beliebigen Scheitelpunkts 2 ** Nachdem Sie die verkettete Komponente mit UnionFind gefunden haben, müssen Sie nur sicherstellen, dass die Reihenfolge aller Scheitelpunkte in der verketteten Komponente 2 ist, was erheblich einfacher zu implementieren ist. Ich hatte nicht genug Denkkraft ...

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

vector<bool> check;
vector<vector<ll>> tree;


//Organisieren Sie die Implementierung und stellen Sie sich vor ...
ll bfs(ll i){
    ll ret=1;
    deque<ll> d;
    deque<ll> e;
    check[i]=true;
    if(SIZE(tree[i])==0)return 0;
    e.PB(i);
    d.PB(tree[i][0]);
    e.PB(tree[i][0]);
    check[tree[i][0]]=true;
    //Angenommen, es gilt
    while(SIZE(d)){
        ll l=SIZE(d);
        REP(_,l){
            ll p=d.front();
            d.pop_front();
            FORA(j,tree[p]){
                if(check[j]==false){
                    check[j]=true;
                    d.PB(j);
                    e.PB(j);
                }
            }
        }
    }
    //FORA(i,e)cout<<i<<" ";
    //cout<<endl;
    for(auto j=e.begin();j!=e.end();j++){
        ll x,y;x=*j;
        if(j==--e.end()){
            y=*e.begin();
        }else{
            //y=*Ich habe es geschafft j
            auto k=j;k++;y=*k;
        }
        if(SIZE(tree[x])!=2){
            ret=0;
            break;
        }else{
            if(tree[x][0]==y or tree[x][1]==y){
                continue;
            }else{
                ret=0;
                break;
            }
        }
    }
    d.PB(i);
    while(SIZE(d)){
        ll l=SIZE(d);
        REP(_,l){
            ll p=d.front();
            d.pop_front();
            FORA(j,tree[p]){
                if(check[j]==false){
                    check[j]=true;
                    d.PB(j);
                    e.PB(j);
                }
            }
        }
    }
    return ret;
}

signed main(){
    //Code zur Beschleunigung der Eingabe
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n,m;cin>>n>>m;
    tree=vector<vector<ll>>(n);
    check=vector<bool>(n,false);
    REP(i,m){
        ll u,v;cin>>u>>v;
        tree[u-1].PB(v-1);
        tree[v-1].PB(u-1);
    }
    ll ans=0;
    REP(i,n){
        if(check[i]==false){
            ans+=bfs(i);
        }
    }
    cout<<ans<<endl;
}

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

    //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]].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,m;cin>>n>>m;
    vector<vector<ll>> tree(n);
    UnionFind uf(n);
    REP(i,m){
        ll u,v;cin>>u>>v;
        tree[u-1].PB(v-1);
        tree[v-1].PB(u-1);
        uf.unite(u-1,v-1);
    }
    uf.grouping();
    ll ans=0;
    FORA(i,uf.group){
        ll check=1;
        FORA(j,i.S){
            if(SIZE(tree[j])!=2){
                check=0;
                break;
            }
        }
        ans+=check;
    }
    cout<<ans<<endl;
}

n=int(input())
a=list(map(int,input().split()))
s=dict()
for i in range(n):
    if a[i]-1 in s:
        s[a[i]]=s[a[i]-1]+1
    else:
        s[a[i]]=1
ans=[-1,-1]
for i in s:
    if ans[1]<s[i]:
        ans=[i,s[i]]
ans_=[]
for i in range(n-1,-1,-1):
    if ans[0]==a[i]:
        ans[0]-=1
        ans[1]-=1
        ans_.append(i+1)
        if ans[1]==0:
            break
print(len(ans_))
print(" ".join(map(str,ans_[::-1])))