[PYTHON] Codeforces Round # 479 (Div.3) Examen Bacha (9/25)

Les résultats de cette fois

Impressions de cette époque

Le problème E était un jeu d'implémentation, mais je le regrette car j'ai continué à faire des bugs quand je l'ai implémenté de force sans imaginer la forme finale de l'implémentation. C'était bien de passer au problème F en cours de route, mais ce n'est pas une bonne idée d'abandonner l'implémentation même si la politique est parfaitement correcte, donc je m'entraînerai à plusieurs reprises avec le bacha de Kodofo.

Problème A

C'est juste une question de penser au nombre comme une chaîne et de ** le simuler honnêtement **. J'étais un peu perdu car il n'y a pas beaucoup de problèmes comme celui-ci.

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

Problème B

J'ai eu un peu de mal à comprendre la signification de l'énoncé du problème, mais j'ai juste besoin de compter le nombre de chacun des deux caractères consécutifs (ci-après simplement appelés chaîne de caractères). En d'autres termes, si le dictionnaire $ check [i]: = $ (il y a plusieurs combinaisons d'index dont les chaînes de caractères sont $ i $), il y a $ n-1 $ combinaisons d'index, donc toutes devraient être $ check $. Vous pouvez l'enregistrer. Après l'enregistrement dans le dictionnaire, celui avec la plus grande combinaison d'index doit être sorti, et les éléments du dictionnaire sont triés dans l'ordre inverse et le premier est utilisé comme solution.

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

Problème C

C'est $ x \ in [1,10 ^ 9] $, donc vous devriez ** faire attention au cas du coin ** (j'ai remarqué que j'ai émis 1WA, soyez prudent ...).

Si $ x $ peut prendre n'importe quel entier, $ a \ _0, a \ _1, a \ _2,…, a \ _ {k-1} \ leqq x lors de l'organisation de la séquence $ a $ dans l'ordre croissant Prenez juste $ x $, qui est $ et $ x <a \ _k $. De plus, comme ils sont classés par ordre croissant, vous pouvez prendre $ x $, qui est $ a \ _ {k-1} \ leqq x <a \ k $. De plus, ** $ x = a \ _ {k-1} $ doit être défini **, mais si $ a {k-1} = a \ _k $, la condition n'est pas satisfaite, donc -1 est affiché. Je vais.

Aussi, lorsque $ k = 0, n $, ** $ a \ _ {k-1} $ et $ a \ _k $ n'existent pas **, il est donc nécessaire de séparer les cas. Quand $ k = n $, $ a \ _ {max} $ vaut au plus 10 $ ^ 9 $, donc $ x = 10 ^ 9 $. Par contre, lorsque $ k = 0 $, $ a \ _0 = 1 $, $ x \ geqq 1 $, la condition n'est pas satisfaite. Dans d'autres cas, $ a \ _0-1 $ satisfera la condition. (1WA a fait une erreur quand $ 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])

Problème D

Je pensais que c'était étonnamment difficile, mais c'était un problème de niveau D.

(Dans la politique suivante, je pensais que -1 serait affiché s'il n'existait pas à mi-chemin, j'ai donc procédé à l'examen, il y a donc des points redondants, mais ne vous inquiétez pas.) (Je l'ai mal lu, mais le problème de la personne qui l'a mal lu Si vous faites ** Il semble que vous puissiez faire un problème au niveau de la première moitié du vert **.)

$ x $ ne peut être divisé que par 3 ou multiplié par 2. De plus, par exemple, dans le cas de 4,6 $, il ne peut pas être créé par opération, mais ** l'entrée est toujours satisfaite ** (même si vous pensez que cela peut ne pas exister et résoudre le problème, vous pouvez le résoudre après tout. Cependant, la mise en œuvre sera légèrement réduite).

Tout d'abord, en faisant attention à l'opération de "diviser par 3" parmi les opérations, si le multiple de 3 subsiste encore lors de la division par 3 et qu'il n'est plus un multiple de 3, le sujet n'est pas satisfait. En d'autres termes, à partir de l'opération de division par 3, nous pouvons voir que si chacun est un multiple de 3 $ ^ i $, l'opération doit être effectuée à partir de celle avec le plus grand ** $ 3 ^ i $ **. De plus, à partir de l'opération de multiplication par 2, vous pouvez voir que vous devez opérer à partir du plus petit ** $ 2 ^ i $ **.

Par conséquent, découvrez combien de fois $ a \ _i $ peut être divisé par $ 2,3 $ comme $ x \ _i, y \ _i $, en commençant par ** $ x \ _i $ étant plus petit et $ y \ _i $ plus grand. Traitez ** dans l'ordre (✳︎). Si vous traitez dans cet ordre, vous pouvez toujours trier dans l'ordre qui satisfait le sujet dans les conditions de ce problème, et sortir dans cet ordre.

(✳︎)… S'il n'existe pas, considérez GCD ici, mais ce n'est pas nécessaire ici.

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

Problème E

Je l'ai écrit en C ++ parce que je pensais avoir besoin de DFS (récursif), mais j'ai fini par l'implémenter dans BFS. J'ai fait beaucoup d'erreurs stupides, mais comme je l'ai dit, je pense que c'était parce que je ne pouvais pas avoir une image de la forme finale de l'implémentation.

Si vous lisez l'énoncé du problème, vous aurez une politique. C'est un peu long, mais cela explique simplement que c'est un type de graphique courant sans boucles (les côtés qui le connectent) et sans côtés multiples. Ce que nous devrions demander dans cette question est ** combien de composants de liaison existent qui sont fabriqués en un seul cycle **. Ici, nous devons saisir les caractéristiques du cycle avant de le mettre en œuvre. La figure est la suivante.

De plus, j'utilise toujours UnionFind lors de la recherche d'un composant de liaison, mais ici j'ai décidé d'utiliser ** BFS pour penser à un composant de liaison qui satisfait le sujet **. Dans la figure ci-dessus, si un point au moment de BFS est choisi comme point de départ, ** lors du traçage à partir de ce point de départ ** Si l'ordre de chaque sommet est 2 et revient finalement au point de départ <font color = "red" "> (✳︎) </ font> ** On peut dire que les composants de connexion ne forment qu'un seul cycle. Cependant, même si je n'avais qu'à implémenter cela, je l'ai rendu bogué, alors j'ai pensé à une méthode d'implémentation plus simple **.

Ensuite, j'ai proposé l'implémentation suivante. Je pense que c'est une mise en œuvre qui me vient à l'esprit lorsque l'on considère les conditions qui sont réunies lorsque le cycle est établi.

Tout d'abord, ** sélectionnez le point de départ **. Le point de départ peut être n'importe quel sommet qui n'a pas été recherché. De plus, dans BFS, il est basique de mettre le point de départ dans deque, de créer les sommets qui sont connectés aux sommets dans deque et qui n'ont pas été recherchés, puis de les mettre en deque et de répéter jusqu'à ce qu'il n'y ait plus d'éléments dans deque. .. Cependant, cette fois, je veux rechercher dans l'ordre suivant **, donc cette implémentation ne fonctionnera pas ($ \ car $ elle procédera dans deux directions à partir du point de départ).

Par conséquent, après avoir choisi le point de départ et effectué sa recherche, ** on suppose qu'un point (seulement) connecté au point de départ a été recherché et la recherche est effectuée dans l'ordre à partir de ce point **. Ici, en plus du deque (d) utilisé dans la recherche BFS, préparez un deque (ʻe) qui est stocké dans l'ordre de recherche. Après avoir effectué cette recherche BFS, le cycle ci-dessus est évalué. A ce moment, puisque les informations des sommets sont conservées dans ʻe dans l'ordre de recherche , "L'ordre de tous les sommets est-il inclus dans ʻe 2?" Et "Arbitraire de ʻe" Si vous vérifiez les deux points de " sommets consécutifs et si le point de départ et le point final sont connectés **", le cycle sera jugé.

De plus, dans le BFS précédent, seuls deux (maximum) des sommets connectés à partir du point de départ sont recherchés, et si l'ordre est 2 ou plus, il peut y avoir des sommets non recherchés **, le point de départ est donc à nouveau recherché. Insérez-le dans d et exécutez BFS pour vérifier les ** sommets restants contenus dans ce composant concaténé **.

À partir de ce qui précède, il est possible de juger si chaque composant connecté est un cycle, donc le nombre total est la réponse.

(Je travaille toujours dur sur la première implémentation que j'ai proposée, mais parfois j'ai pensé qu'il était important de changer une partie de la politique pour la rendre plus facile **. Non seulement la puissance de l'implémenter, mais aussi ** plus claire et boguée. Je pense que c'est aussi la puissance de montage pour penser à une implémentation facile sans le laisser **, donc je vais essayer de gagner à la fois la puissance de montage.)

Postscript (25/09/2020)

La condition pour que le composant concaténé soit un cycle s'écrit (✳︎) </ font>, mais cette condition est ** la même valeur que l'ordre de tout sommet est 2 **, donc Après avoir trouvé le composant concaténé à l'aide d'UnionFind, il vous suffit de vous assurer que l'ordre de tout sommet du composant concaténé est 2, ce qui est considérablement plus facile à implémenter. Je n'avais pas assez de pouvoir de réflexion ...

//Options de débogage:-fsanitize=undefined,address

//Optimisation du compilateur
#pragma GCC optimize("Ofast")

//Inclure etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//macro
//pour boucle
//L'argument est(Variables dans la boucle,Amplitude de mouvement)Ou(Variables dans la boucle,Premier numéro,Nombre d'extrémités)、のどちらOu
//Les variables de boucle sans D sont incrémentées de 1 et les variables de boucle avec D sont décrémentées de 1.
//FORA est une gamme de déclaration(Si c'est difficile à utiliser, effacez-le)
#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 est un conteneur tel que vector
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//constant
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 100000 //10^5:Portée maximale de la baie
//Abréviation
#define PB push_back //Insérer
#define MP make_pair //constructeur de paires
#define F first //Le premier élément de paire
#define S second //Le deuxième élément de paire

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


//Organisez la mise en œuvre et imaginez ...
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;
    //Supposons qu'il tient
    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=*Je l'ai fait 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 pour accélérer la saisie
    //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;
}

//Options de débogage:-fsanitize=undefined,address

//Optimisation du compilateur
#pragma GCC optimize("Ofast")

//Inclure etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//macro
//pour boucle
//L'argument est(Variables dans la boucle,Amplitude de mouvement)Ou(Variables dans la boucle,Premier numéro,Nombre d'extrémités)、のどちらOu
//Les variables de boucle sans D sont incrémentées de 1 et les variables de boucle avec D sont décrémentées de 1.
//FORA est une gamme de déclaration(Si c'est difficile à utiliser, effacez-le)
#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 est un conteneur tel que vector
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//constant
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 100000 //10^5:Portée maximale de la baie
//Abréviation
#define PB push_back //Insérer
#define MP make_pair //constructeur de paires
#define F first //Le premier élément de paire
#define S second //Le deuxième élément de paire



//Ci-dessous, l'ensemble premier et l'arbre représentent la même chose.
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)
    map<ll,vector<ll>> group; //Gérer par set(key:Représentant de l'ensemble, valeur:Un tableau d'éléments de l'ensemble)
    ll n; //Nombre d'éléments

    //constructeur
    UnionFind(ll n_):n(n_),parent(n_),siz(n_,1){ 
        //Initialiser en tant que racine de tous les éléments est lui-même
        for(ll i=0;i<n;i++){parent[i]=i;}
    }

    //Récupère la racine de l'arborescence à laquelle appartient la donnée x(Effectuer également la compression d'itinéraire)
    ll root(ll x){
        if(parent[x]==x) return x;
        return parent[x]=root(parent[x]);//La valeur de l'expression d'affectation étant la valeur de la variable affectée, l'itinéraire peut être compressé.
    }

    //Fusionner les arbres x et y
    void unite(ll x,ll y){
        ll rx=root(x);//x racine
        ll ry=root(y);//racine de y
        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
    }

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

    //Obtenez la taille de l'ensemble premier de x
    ll size(ll x){
        return siz[root(x)];
    }

    //Regroupez chaque ensemble principal
    void grouping(){
        //Effectuez d'abord la compression d'itinéraire
        REP(i,n)root(i);
        //Gérer avec la carte(Utiliser la version par défaut)
        REP(i,n)group[parent[i]].PB(i);
    }

    //Supprimer le système prime set et initialiser
    void clear(){
        REP(i,n){parent[i]=i;}
        siz=vector<ll>(n,1);
        group.clear();
    }
};


signed main(){
    //Code pour accélérer la saisie
    //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])))