AtCoder Beginner Contest 049 Revue des questions précédentes

Temps requis

スクリーンショット 2020-02-29 16.55.33.png

Impressions

Non, je n'ai pas pu résoudre D et j'ai dormi infidèlement. Quand je suis resté coincé, j'y ai juste pensé sur mon iPad et je me suis dit plusieurs fois, mais j'ai renoncé à nouveau bientôt. Pas du tout. La personne qui l'a résolu aujourd'hui y a pensé pendant deux heures, mais ce n'est pas du tout devenu AC, donc aujourd'hui est une mauvaise journée ... (Si je papillonnais pendant mes études à l'étranger, j'ai reporté l'examen d'environ cinq jours.)

Problème A

J'ai fait une erreur d'orthographe.

answerA.py


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

Problème B

Sortez simplement l'entrée deux fois.

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])

Problème C

J'ai trouvé cela assez difficile. Premièrement, j'essayais généralement de me séparer de l'avant. Cependant, j'ai trouvé assez difficile de déterminer où couper lors de la coupe. Ici, j'ai décidé de ** au contraire penser par derrière **. Ensuite, puisque la méthode de coupe est toujours fixée à un, on peut dire que S = T peut être défini si S peut devenir une chaîne de caractères vide en séparant la dernière partie dans l'ordre.

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")

Problème D

Je ne comprends pas pourquoi je ne peux pas le résoudre. C'est trop doux, car ma capacité de réflexion diminue avec le temps. Dans ce problème, nous voulons considérer les villes qui sont connectées et appartiennent au même groupe, nous en venons donc à l'idée que nous voulons les diviser en groupes par Union Find. Ici, ** le regroupement des villes reliées par des routes et le regroupement des villes reliées par des chemins de fer (✳︎) ** peuvent être facilement réalisés en créant Union Find et en mettant à jour chaque nœud racine. Je peux. Cependant, il n'est pas vraiment indépendant et vous devez savoir ce qui est dans le même groupe dans les deux (✳︎). À ce stade, j'ai eu l'idée qu'il serait difficile de trouver les deux en même temps, donc je devrais en chercher un à la fois. Dans ce cas, cette idée est difficile (je n'ai pas pu sortir de la discussion ici ... ** Image de l'écriture des conditions nécessaires et suffisantes **). Notez maintenant que UnionFind vous permet de numéroter chaque groupe. Ensuite, vous pouvez voir que chaque ville a ** deux nombres **. En d'autres termes, si vous reformulez la condition que les deux (✳︎) sont dans le même groupe, la condition que les deux nombres sont les mêmes **. Par conséquent, il peut être facilement implémenté en sauvegardant les paires de deux nombres dans le dictionnaire à chaque regroupement et en comptant le nombre de chaque paire.

answerD.cc


//Référence: http://ehafib.hatenablog.com/entry/2015/12/23/164517
//Comprendre
#include<algorithm>//sort,Recherche de bisection,Tel
#include<bitset>//Jeu de bits de longueur fixe
#include<cmath>//pow,journal etc.
#include<complex>//Nombre complexe
#include<deque>//File d'attente d'accès double
#include<functional>//trier plus
#include<iomanip>//setprecision(Erreur de sortie en virgule flottante)
#include<iostream>//Entrée sortie
#include<map>//map(dictionnaire)
#include<numeric>//iota(Génération d'une chaîne entière),pgcd et lcm(c++17)
#include<queue>//queue
#include<set>//ensemble
#include<stack>//empiler
#include<string>//Chaîne
#include<unordered_map>//Carte avec itérateur mais sans ordre
#include<unordered_set>//Il y a un itérateur mais l'ordre n'est pas maintenu défini
#include<utility>//pair
#include<vector>//Tableau de longueur variable

using namespace std;
typedef long long ll;

//macro
#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() //Je souhaite omettre des arguments tels que le tri
#define FORALL(i,x) for(auto i=x.begin();i!=x.end();i++)
#define SIZE(x) ((ll)(x).size()) //taille à la taille_Changement de t à 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]Est le parent de i
    vector<ll> siz; //Un tableau représentant la taille de l'ensemble premier(Initialiser avec 1)

    //Du constructeur:Derrière l'initialisation des variables membres
    UnionFind(ll n):parent(n),siz(n,1){ //Initialisez car tout est root au début
        for(ll i=0;i<n;i++){parent[i]=i;}
    }

    ll root(ll x){ //Récupère la racine de l'arborescence à laquelle appartient la donnée x
        if(parent[x]==x) return x;
        //La valeur de l'expression d'affectation sera la valeur de la variable affectée!
        //Compression de chemin(Rationalisez les calculs en connectant les éléments directement à la racine)
        return parent[x]=root(parent[x]);
        //Mettre à jour le parent lors de l'obtention par récursif
    }

    void unite(ll x,ll y){ //Fusionner les arbres x et y
        ll rx=root(x);//La racine de x est rx
        ll ry=root(y);//y root ry
        if(rx==ry) return; //Quand dans le même arbre
        //Fusionner un petit ensemble dans un grand ensemble(Fusionné de ry à rx)
        if(siz[rx]<siz[ry]) swap(rx,ry);
        siz[rx]+=siz[ry];
        parent[ry]=rx; //Lorsque x et y ne sont pas dans le même arbre, attachez la racine y ry à la racine x rx
    }

    bool same(ll x,ll y){//Renvoie si l'arbre auquel appartiennent x et y est le même
        ll rx=root(x);
        ll ry=root(y);
        return rx==ry;
    }

    ll size(ll x){ //Taille de l'ensemble élémentaire
        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;
        }
    }
}

Recommended Posts

AtCoder Beginner Contest 072 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 127 Revue des questions précédentes
AtCoder Beginner Contest 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes
AtCoder Beginner Contest 112 Revue des questions précédentes
AtCoder Beginner Contest 076 Revue des questions précédentes
AtCoder Beginner Contest 089 Revue des questions précédentes
AtCoder Beginner Contest 069 Revue des questions précédentes
AtCoder Beginner Contest 079 Revue des questions précédentes
AtCoder Beginner Contest 056 Revue des questions précédentes
AtCoder Beginner Contest 087 Revue des questions précédentes
AtCoder Beginner Contest 067 Revue des questions précédentes
AtCoder Beginner Contest 093 Revue des questions précédentes
AtCoder Beginner Contest 123 Revue des questions précédentes
AtCoder Beginner Contest 049 Revue des questions précédentes
AtCoder Beginner Contest 078 Revue des questions précédentes
AtCoder Beginner Contest 081 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 060 Revue des questions précédentes
AtCoder Beginner Contest 104 Revue des questions précédentes
AtCoder Beginner Contest 057 Revue des questions précédentes
AtCoder Beginner Contest 121 Revue des questions précédentes
AtCoder Beginner Contest 126 Revue des questions précédentes
AtCoder Beginner Contest 090 Revue des questions précédentes
AtCoder Beginner Contest 103 Revue des questions précédentes
AtCoder Beginner Contest 061 Revue des questions précédentes
AtCoder Beginner Contest 059 Revue des questions précédentes
AtCoder Beginner Contest 044 Revue des questions précédentes
AtCoder Beginner Contest 083 Revue des questions précédentes
AtCoder Beginner Contest 048 Revue des questions précédentes
AtCoder Beginner Contest 124 Revue des questions précédentes
AtCoder Beginner Contest 116 Revue des questions précédentes
AtCoder Beginner Contest 097 Revue des questions précédentes
AtCoder Beginner Contest 088 Revue des questions précédentes
AtCoder Beginner Contest 092 Revue des questions précédentes
AtCoder Beginner Contest 099 Revue des questions précédentes
AtCoder Beginner Contest 065 Revue des questions précédentes
AtCoder Beginner Contest 053 Revue des questions précédentes
AtCoder Beginner Contest 094 Revue des questions précédentes
AtCoder Beginner Contest 063 Revue des questions précédentes
AtCoder Beginner Contest 107 Revue des questions précédentes
AtCoder Beginner Contest 071 Revue des questions précédentes
AtCoder Beginner Contest 064 Revue des questions précédentes
AtCoder Beginner Contest 082 Revue des questions précédentes
AtCoder Beginner Contest 084 Revue des questions précédentes
AtCoder Beginner Contest 068 Revue des questions précédentes
AtCoder Beginner Contest 058 Revue des questions précédentes
AtCoder Beginner Contest 043 Revue des questions précédentes
AtCoder Beginner Contest 098 Revue des questions précédentes
AtCoder Beginner Contest 114 Revue des questions précédentes
AtCoder Beginner Contest 045 Revue des questions précédentes
AtCoder Beginner Contest 120 Revue des questions précédentes