[PYTHON] Codeforces Round # 600 (Div.2) Examen Bacha (10/21)

Les résultats de cette fois

Impressions de cette époque

La critique de Bacha n'a pas rattrapé son retard car je me suis préparé pour l'annonce de la remise des diplômes d'aujourd'hui juste avant. Je veux être une personne capable d'équilibrer la recherche de fin d'études et les professionnels de la compétition.

De plus, je ne résoudrai pas le problème car l'examen ne rattrape pas. Je ferai de mon mieux à partir de demain.

Problème A

Je n'entrerai pas dans les détails du problème, mais envisagez d'égaliser $ a $ et $ b $ en une seule opération.

Ici, en ** paraphrasant le problème ** et en prenant les parties continues inégales de $ a $ et $ b $, ① lorsque le nombre de parties est de deux ou plus ② le nombre de parties est de un NON doit être affiché lorsque la différence au sein de la pièce n'est pas égale ou que la différence au sein de la pièce est $ b \ _i-a \ _i \ <0 $), et OUI doit être affiché à d'autres moments.

Les parties contiguës inégales de $ a $ et $ b $ peuvent être facilement extraites en utilisant la fonction ** groupby pour déterminer si $ b \ _i-a \ _i = 0 $ **. Aussi, il n'est pas difficile de juger ① et ② tant que cette partie continue peut être extraite.

A.py

from itertools import groupby
for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    b=list(map(int,input().split()))
    c=[a[i]-b[i] for i in range(n)]
    d=[[i,list(j)] for i,j in groupby(c,key=lambda x:x==0) if i==False]
    if len(d)>=2:
        print("NO")
    elif len(d)==0:
        print("YES")
    else:
        l=len(d[0][1])
        for i in range(l):
            if d[0][1][i]!=d[0][1][0]:
                print("NO")
                break
        else:
            if d[0][1][i]>0:
                print("NO")
            else:
                print("YES")

Problème B

Si vous ne résolvez pas le problème, ce sera presque $ O (n ^ 2) $, alors implémentez-le soigneusement. De plus, cette fois, nous n'avons pas à penser au nombre maximum ou minimum de jours, donc nous faisons juste ** une simulation simple **.

De plus, il y a certaines conditions, alors assurez-vous de ** les écrire **. Veuillez me pardonner si l'expression est légèrement différente de l'énoncé du problème. Si ce qui suit n'est pas valable pour chaque information d'entrée / sortie, cela vaut pour un jour.

① Lorsqu'une seule des touches + et - (+) apparaît ② Lorsque +, - (+) apparaît plus d'une fois ③ Quand-apparaît avant +

A ce moment, afin d'éviter le cas où la condition (2) apparaît plus d'une fois, si elle tient comme un jour **, il est immédiatement décidé que le jour tient. Cette explication n'est pas facile à comprendre, la mise en œuvre est donc expliquée ci-dessous.

$ s: $ Un groupe de personnes déjà venues $ b: $ Un groupe de personnes qui ne sont pas encore revenus $ now: $ Index des informations d'entrée / sortie que vous recherchez (moins de $ n $) $ ans: $ Dernier index des informations d'entrée / sortie donné pour un jour

Si vous préparez les quatre ci-dessus, vous pouvez simplement créer les ** cas ** suivants.

(1) Quand $ a [maintenant] > 0 $ [1] Lorsque $ a [now] $ est inclus dans $ s $ Puisque + apparaît deux fois, ② n'est pas satisfait. Sorties -1. [2] Lorsqu'il n'est pas inclus Ajoutez $ a [now] $ à $ s $ et $ b $.

(2) Quand $ a [maintenant] \ <0 $ [1] Lorsque $ -a [now] $ n'est pas inclus dans $ b $ -Est sorti en premier, ou +, - est déjà sorti, donc ni ② ni ③ ne sont satisfaits. Sorties -1. [2] Lorsqu'il est inclus Excluez $ -a [now] $ de $ b $.

De plus, si ** $ b $ est vide, il tient comme un jour **, alors effacez tout le contenu de $ s $ et ajoutez $ now $ à $ ans $.

Si $ b $ n'est pas vide après avoir effectué la classification des cas ci-dessus dans l'ordre avec des informations d'entrée / sortie arbitraires, ① n'est pas satisfait. Dans ce cas, -1 est émis.

De plus, puisque la sortie est ** la longueur lorsque les informations d'entrée / sortie sont divisées **, $ ans [i] -ans [i-1] $ doit être affiché dans l'ordre croissant de $ i $.

(C'est une longue explication, mais je ne pense qu'aux conditions ** ① à ③ et à ce qui est nécessaire en tant que variable **.)

B.py

n=int(input())
a=list(map(int,input().split()))
#Les gens qui sont déjà venus
s=set()
#Ceux qui doivent se débarrasser maintenant
b=set()
#Jusqu'à quel jour
now=0
#Tableau de réponses
ans=[]
while now<n:
    if a[now]>0:
        if a[now] in s:
            print(-1)
            exit()
        else:
            s.add(a[now])
            b.add(a[now])
    else:
        if -a[now] not in b:
            print(-1)
            exit()
        else:
            b.remove(-a[now])
    if len(b)==0:
        ans.append(now+1)
        s=set()
    now+=1
if len(b)!=0:
    print(-1)
    exit()
for i in range(len(ans)-1,0,-1):
    ans[i]-=ans[i-1]
print(len(ans))
print(" ".join(map(str,ans)))

Problème C

** J'ai été confus par le réglage du problème **, mais si vous pensez calmement, c'est un problème avec de nombreuses parties évidentes.

Pensez à choisir une pièce de $ k $. À ce stade, il est préférable de sélectionner ** $ k $ pièces ** parmi les plus petites. De plus, lors de la sélection de pièces de $ k $, il est préférable de ** sélectionner des pièces de $ m $ par ordre décroissant de douceur ** chaque jour. Par conséquent, si vous pensez à $ m = 2 $, ce sera comme indiqué dans la figure ci-dessous. (La double flèche représente $ m $ pièces, la partie encerclée est le jour où chaque confiserie est sélectionnée et la partie affichée en rouge est le montant du changement.)

Compte tenu du mouvement de la section de longueur ** $ m $ ** dans la figure ci-dessus, en augmentant $ k $, l'incrément de douceur totale sera l'indice ** avec le reste de ** $ m $. (** Paraphrase avec un haut degré d'abstraction! **). En d'autres termes, le reste de la division de l'indice (indexé à 0) par $ m $ est inclus dans $ k $ des index qui sont $ (k-1) \% \ m $. En outre, cela peut être facilement calculé en prenant la somme cumulée des restes pour chaque indice. De plus, puisque la somme cumulée est l'incrément, vous pouvez trouver la réponse pour tout $ k $ en prenant la somme cumulée à la fin.

(✳︎)… Puisque l'incrément est la somme cumulée de chaque reste pendant Bachacon, j'ai écrit ici que je pensais pouvoir obtenir les indices.

C.py

n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
tod=[[] for i in range(k)]
for i in range(n):
    tod[i%k].append(a[i])
from itertools import accumulate
for i in range(k):
    tod[i]=list(accumulate(tod[i]))
ans=[]
now=0
for i in range(n):
    now+=tod[i%k][i//k]
    ans.append(now)
print(" ".join(map(str,ans)))

Problème D

C'est peut-être mon problème préféré avec UnionFind.

Il est facile de voir ce qu'il faut faire, donc je ferai de mon mieux pour bien l'implémenter.

Quand $ (l, r) $ est connecté, $ (l, l + 1) $, $ (l, l + 2) $… $ (l, r-1) $ sont également connectés, c'est-à-dire * * Tous les nœuds avec des nombres entre $ [l, r] $ doivent être dans le même composant concaténé **. Étant donné que l'échantillon 1 est facile à comprendre, compte tenu de ce cas, il sera le suivant.

1-2-5-7
3-4-6-8
9
10
11-12

À ce stade, $ (1,7) $ est connecté, donc les nœuds avec les nombres inclus dans $ [1,7] $ doivent avoir le même composant de connexion. Autrement dit, les premier et deuxième composants de liaison doivent être le même composant de liaison et la réponse est 1.

1-2-3-4-5-6-7-8
9
10
11-12

Par conséquent, effectuez d'abord la recherche d'union pour séparer les composants liés. De plus, après avoir exécuté Union Find, il est nécessaire d'attacher les composants connectés les uns aux autres un minimum de fois pour satisfaire le thème. Ici, si $ l $ et $ r $ sont connectés, tous les nœuds inclus dans $ [l, r] $ sont connectés, donc seul le nœud avec le plus petit et le plus grand nombre ** du composant concaténé est sauvegardé. Tu peux le faire **.

Par conséquent, selon UnionFind, si $ l \ _i $ est la valeur minimale et $ r \ _i $ est la valeur maximale du $ i $ ème composant concaténé, alors $ [l \ _1, r \ _1], [l \ _2, Vous pouvez obtenir l'intervalle r \ _2],…. [L \ _ k, r_k] $.

Si vous arrangez ces sections dans l'ordre croissant de ** $ l $ ** (✳︎), quand ** $ hashi > l \ _i $ tient en définissant l'extrémité droite de la section qui devrait avoir le même composant de connexion que $ hashi $ $ [l \ _i, r \ _i] $ doit également être le même composant concaténé **, auquel moment il sera mis à jour comme $ hash = max (hashi, r \ _i) $.

Au contraire, dans le cas de $ hashi \ <l \ _i $, ** il n'est pas nécessaire de mettre à jour et le sujet est satisfait **, donc si vous enregistrez le nombre de composants liés d'origine contenus dans ce composant lié dans $ now $ , $ Now-1 $ est le nombre minimum de côtés requis pour créer ce composant concaténé. (En même temps, mettez à jour les valeurs de $ hashi $ et $ now $ pour le prochain composant concaténé que vous souhaitez vérifier.)

Par conséquent, si le nombre minimum de côtés supplémentaires que vous souhaitez trouver en tant que réponse est $ ans $, vous pouvez trouver la réponse en vérifiant dans n'importe quelle section et en ajoutant $ now-1 $ à $ ans $, puis ajoutez $ ans $. Il vous suffit de le sortir.

(✳︎)… Lorsque vous pensez à fusionner des sections, il est courant de trier par le bord gauche ou droit **

D.cc

//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
//S'il n'y a pas de D, la variable de boucle est incrémentée de 1, et s'il y a un D, la variable de boucle est décrémentée 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,set<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]);//Puisque la valeur de l'expression d'affectation est 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éterminer 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]].insert(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(){
    //Spécification de sortie du nombre de chiffres fractionnaires
    //cout<<fixed<<setprecision(10);
    //Code pour accélérer la saisie
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n,m;cin>>n>>m;
    UnionFind uf(n);
    REP(i,m){
        ll u,v;cin>>u>>v;
        uf.unite(u-1,v-1);
    }
    uf.grouping();
    vector<pair<ll,ll>> segments;
    FORA(i,uf.group){
        segments.PB(MP(*i.S.begin(),*--i.S.end()));
    }
    sort(ALL(segments));
    ll hashi=segments[0].S;
    ll now=1;
    ll ans=0;
    FOR(i,1,SIZE(segments)-1){
        if(hashi<segments[i].F){
            ans+=(now-1);
            now=1;
            hashi=segments[i].S;
        }else{
            hashi=max(hashi,segments[i].S);
            now++;
        }
    }
    ans+=(now-1);
    cout<<ans<<endl;
}

Après le problème E

Je vais sauter cette fois.