[PYTHON] AtCoder Beginner Contest 049 Rückblick auf frühere Fragen

Benötigte Zeit

Impressionen

Nein, ich konnte D nicht lösen und habe untreu geschlafen. Als ich feststeckte, dachte ich nur auf meinem iPad darüber nach und sagte es mir oft, aber ich gab bald wieder auf. Überhaupt nicht. Die Person, die es heute gelöst hat, hat zwei Stunden lang darüber nachgedacht, aber es wurde überhaupt nicht zu AC, also ist heute ein schlechter Tag ... (Wenn ich während des Studiums im Ausland flatterte, habe ich die Überprüfung um etwa fünf Tage verschoben.)

Problem A

Ich habe einen Rechtschreibfehler gemacht.

answerA.py

a=["a","e","i","o","u"]
print("vowel" if input() in a else "consonant")

B-Problem

Geben Sie den Eingang einfach zweimal aus.

answerB.py

h,w=map(int,input().split())
x=[input() for i in range(h)]
for i in range(h):
    print(x[i])
    print(x[i])

C-Problem

Ich fand es ziemlich schwierig. Zuerst habe ich normalerweise versucht, mich von vorne zu trennen. Ich fand es jedoch ziemlich schwierig zu bestimmen, wo beim Schneiden geschnitten werden soll. Hier habe ich beschlossen, ** umgekehrt von hinten zu denken **. Da die Schneidemethode immer auf eins festgelegt ist, kann gesagt werden, dass S = T gesetzt werden kann, wenn S durch Trennen des letzten Teils in der Reihenfolge zu einer leeren Zeichenkette gemacht werden kann.

answerC.py

s=input()
l=len(s)
while s!=0:
    l=len(s)
    if s.rfind("dream")==l-5:
        s=s[:l-5]
    elif s.rfind("dreamer")==l-7:
        s=s[:l-7]
    elif s.rfind("erase")==l-5:
        s=s[:l-5]
    elif s.rfind("eraser")==l-6:
        s=s[:l-6]
    else:
        break
if len(s)==0:
    print("YES")
else:
    print("NO")

D Problem

Ich verstehe nicht, warum ich es nicht lösen kann. Es ist zu süß, da meine Denkfähigkeit proportional zur Zeit abnimmt. In diesem Problem möchten wir Städte berücksichtigen, die miteinander verbunden sind und derselben Gruppe angehören. Daher kommen wir zu dem Gedanken, dass wir sie nach Union Find in Gruppen aufteilen möchten. Hier kann die ** Gruppierung von Städten, die durch Straßen verbunden sind, und die Gruppierung von Städten, die durch Eisenbahnen verbunden sind (✳︎) **, einfach durch Erstellen von Union Find und Aktualisieren jedes Wurzelknotens erfolgen. Ich kann. Es ist jedoch nicht wirklich unabhängig, und Sie müssen herausfinden, was sich in beiden Gruppen in derselben Gruppe befindet (✳︎). Zu diesem Zeitpunkt kam mir die Idee, dass es schwierig sein würde, beide gleichzeitig zu finden, daher sollte ich nacheinander suchen. In diesem Fall ist diese Idee schwierig (ich konnte hier nicht aus der Diskussion herauskommen ... ** Bild des Aufschreibens der notwendigen und ausreichenden Bedingungen **). Beachten Sie nun, dass Sie mit UnionFind jede Gruppe nummerieren können. Dann können Sie sehen, dass jede Stadt ** zwei Zahlen ** hat. Mit anderen Worten, wenn Sie die Bedingung umformulieren, dass beide (✳︎) in derselben Gruppe sind, die Bedingung, dass beide Zahlen gleich sind **. Daher kann es leicht implementiert werden, indem die Paare von zwei Zahlen im Wörterbuch bei jeder Gruppierung gespeichert und die Anzahl jedes Paares gezählt werden.

answerD.cc

//Referenz: http://ehafib.hatenablog.com/entry/2015/12/23/164517
//Einschließen
#include<algorithm>//sort,Halbierungssuche,Eine solche
#include<bitset>//Bit mit fester Länge gesetzt
#include<cmath>//pow,Protokoll usw.
#include<complex>//Komplexe Zahl
#include<deque>//Double-Ended-Zugriffswarteschlange
#include<functional>//größer sortieren
#include<iomanip>//setprecision(Gleitkomma-Ausgabefehler)
#include<iostream>//Input-Output
#include<map>//map(Wörterbuch)
#include<numeric>//iota(Generierung einer Ganzzahlzeichenfolge),gcd und lcm(c++17)
#include<queue>//Warteschlange
#include<set>//einstellen
#include<stack>//Stapel
#include<string>//String
#include<unordered_map>//Karte mit Iterator, aber ohne Ordnung
#include<unordered_set>//Es gibt einen Iterator, aber die Reihenfolge wird nicht festgelegt
#include<utility>//pair
#include<vector>//Array mit variabler Länge

using namespace std;
typedef long long ll;

//Makro
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //Ich möchte Argumente wie sort weglassen
#define FORALL(i,x) for(auto i=x.begin();i!=x.end();i++)
#define SIZE(x) ((ll)(x).size()) //Größe zu Größe_Wechseln Sie von t nach ll
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000
#define MOD 10000007
#define PB push_back
#define MP make_pair
#define F first
#define S second


class UnionFind {
public:
    vector<ll> parent; //parent[i]Ist der Elternteil von i
    vector<ll> siz; //Ein Array, das die Größe der Primzahl darstellt(Initialisieren Sie mit 1)

    //Vom Konstruktor:Dahinter werden Mitgliedsvariablen initialisiert
    UnionFind(ll n):parent(n),siz(n,1){ //Initialisieren Sie, da zunächst alles root ist
        for(ll i=0;i<n;i++){parent[i]=i;}
    }

    ll root(ll x){ //Holen Sie sich die Wurzel des Baums, zu dem die Daten x rekursiv gehören
        if(parent[x]==x) return x;
        //Der Wert des Zuweisungsausdrucks ist der Wert der zugewiesenen Variablen!
        //Pfadkomprimierung(Optimieren Sie Berechnungen, indem Sie Elemente direkt mit der Wurzel verbinden)
        return parent[x]=root(parent[x]);
        //Aktualisieren Sie das übergeordnete Element, wenn Sie rekursiv arbeiten
    }

    void unite(ll x,ll y){ //X- und y-Bäume zusammenführen
        ll rx=root(x);//Die Wurzel von x ist rx
        ll ry=root(y);//y root ry
        if(rx==ry) return; //Wenn im selben Baum
        //Füge einen kleinen Satz zu einem großen Satz zusammen(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
    }

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

    ll size(ll x){ //Grundsatzgröße
        return siz[root(x)];
    }
};

signed main(){
    ll n,k,l;cin >> n >> k >> l;

    UnionFind uf1(n);
    vector< pair<ll,ll> > pq(k);
    REP(i,k){cin >> pq[i].F >> pq[i].S;pq[i].F-=1;pq[i].S-=1;}
    REP(i,k){uf1.unite(pq[i].F,pq[i].S);}

    UnionFind uf2(n);
    vector< pair<ll,ll> > rs(l);
    REP(i,l){cin >> rs[i].F >> rs[i].S;rs[i].F-=1;rs[i].S-=1;}
    REP(i,l){uf2.unite(rs[i].F,rs[i].S);}

    vector< pair<ll,ll> > num(n);
    REP(i,n){num[i].F=uf1.root(i);num[i].S=uf2.root(i);}
    map< pair<ll,ll>, ll> group;
    REP(i,n){
        if(group.find(num[i])==group.end()){
            group[num[i]]=1;
        }else{
            group[num[i]]+=1;
        }
    }
    REP(i,n){
        if(i!=n-1){
            cout << group[num[i]] << " ";
        }else{
            cout << group[num[i]] << endl;
        }
    }
}