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

Temps requis

スクリーンショット 2020-01-27 22.00.48.png

Impressions

D était un syndicat, j'ai essayé de le comprendre parce que j'ai essayé de l'utiliser et je suis mort. Je veux acquérir suffisamment de connaissances pour être à l'aise avec ABC.

Problème A

Pensez au nombre de fois que vous pouvez écouter b yen sans dépasser c.

answerA.py


a,b,c=map(int,input().split())
print(min(c,b//a))

Problème B

Toutes les recherches sont effectuées dans l'ordre décroissant du plus petit de a et b.

answerB.py


a,b,k=map(int,input().split())
check=0
m=min(a,b)
for i in range(m,0,-1):
    if a%i==0 and b%i==0:
        check+=1
        if check==k:
            print(i)
            break

Problème C

Si vous pensez que c'est un problème de motif qui considère la cohérence du nombre de bleu et de rouge en utilisant la pile, tous finiront par tomber, donc seuls les cubes de même couleur resteront à la fin.

answerC.py


s=input()
c=0
for i in s:
    c+=(i=="0")
    c-=(i=="1")
print(len(s)-abs(c))

Problème D

C'était vraiment difficile ... Ou plutôt, la puissance de l'algorithme ne suffit pas. UnionFindTree Je pense que c'est trop inexpérimenté pour comprendre. Pour le moment, j'ai implémenté UnionFindTree par essais et erreurs après Bachacon (j'ai renvoyé aux deux articles suivants [1], [2]), [3]. Premièrement, UnionFindTree est une structure de données qui détermine si deux éléments appartiennent au même ensemble et fusionne différents ensembles à grande vitesse (je n'expliquerai pas comment cela fonctionne, alors commentez dans le code et Voir l'article de référence.). Il est également important ici que ** UnionFindTree ne puisse pas être fractionné **. Ce problème nécessite une division (car le pont s'effondre) et nécessite une certaine ingéniosité (comme mentionné dans la réponse, mais en général ** il est difficile de supprimer le graphique. ** ). Ici, dans l'état final, aucun des ponts n'est connecté **, et si vous effectuez l'opération inverse, les ponts seront ajoutés un par un **, vous pouvez donc faire des allers-retours lors de l'ajout de ponts. Vous pouvez trouver la réponse en enregistrant les changements du nombre d'îles. Plus précisément, si vous ajoutez un pont qui relie les sommets a et b, le nombre d'éléments de l'ensemble premier qui inclut ces sommets est $ N_a, N_b $ et $ (N_a + N_b) \ times (N_a + N_b- 1) \ div 2 -N_a \ times (N_a-1) \ div 2-N_b \ times (N_b-1) \ div 2 $ augmentera le nombre de paires d'îles pouvant être visitées. Donc, si vous l'implémentez en notant que vous voulez ** le nombre de paires d'îles qui ne peuvent pas être atteintes ** (par rapport à l'état initial):

answerD.cc


#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
typedef long long ll;

//Référence: https://pyteyon.hatenablog.com/entry/2019/03/11/200000
//Référence: https://qiita.com/ofutonfuton/items/c17dfd33fc542c222396

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'arbre auquel les données x appartiennent de manière récursive
        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,m;cin >> n >> m;
    vector< pair<ll,ll> > ab(m);
    for(ll i=m-1;i>=0;i--){cin >> ab[i].first >> ab[i].second;}
    UnionFind uf(n);
    vector<ll> ans(m);ans[0]=(n*(n-1))/2;//cout << ans[0] << endl;
    for(ll i=0;i<m-1;i++){
        //Les mises à jour se produisent ici en même temps
        ll a,b;a=ab[i].first-1;b=ab[i].second-1;
        if(uf.same(a,b)){
        ans[i+1]=ans[i];
        }else{
        ll sa,sb;sa=uf.size(a);sb=uf.size(b);
        ans[i+1]=ans[i]+(sa*(sa-1))/2+(sb*(sb-1))/2;
        uf.unite(a,b);sa=uf.size(a);
        ans[i+1]-=(sa*(sa-1))/2;
        }
    }
    for(ll i=m-1;i>=0;i--){
        cout << ans[i] << endl;
    }
}

Recommended Posts

AtCoder Beginner Contest 102 Revue des questions précédentes
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 051 Revue des questions précédentes
AtCoder Beginner Contest 127 Revue des questions précédentes
AtCoder Beginner Contest 119 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 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 067 Revue des questions précédentes
AtCoder Beginner Contest 093 Revue des questions précédentes
AtCoder Beginner Contest 046 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 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 053 Revue des questions précédentes
AtCoder Beginner Contest 094 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 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
AtCoder Beginner Contest 108 Revue des questions précédentes
AtCoder Beginner Contest 106 Revue des questions précédentes
AtCoder Beginner Contest 122 Revue des questions précédentes
AtCoder Beginner Contest 125 Revue des questions précédentes
AtCoder Beginner Contest 109 Revue des questions précédentes
AtCoder Beginner Contest 118 Revue des questions précédentes
AtCoder Beginner Contest 080 Revue des questions précédentes