[PYTHON] Codeforces Round # 603 (Div.2) Examen Bacha (10/15)

Les résultats de cette fois

Impressions de cette époque

J'ai pu résoudre jusqu'à D, mais E sentait qu'il était toujours hors de portée. L'idée était que le problème E est apparu, mais la mise en œuvre a explosé. Je pense que c'était bien d'avoir pu résoudre D à ce moment-là (bien que C ait mis beaucoup de temps à mystère). De plus, ce numéro était très difficile à lire, donc je n'en veux pas à Writer.

Problème A

Cela semblait intuitif et difficile à résoudre. Dans ce qui suit, nous allons poursuivre la discussion comme $ r \ <g \ <b $.

Au début, j'ai pris la politique de sélectionner beaucoup de $ g et b $ et de combiner le reste avec $ r $, mais c'était une merveilleuse solution de mensonge sans même passer un échantillon. De l'idée de ** combiner du plus, ** (TLE si c'est idiot), j'ai trouvé la solution suivante (non prouvée, mais probablement correcte).

① Combinez $ g et b $ jusqu'à $ g = r $ Pour le moment, seuls $ m = g-r $ peuvent être appariés. Les $ g et b $ utilisés pour la paire seront mis à jour.

② Considérons une combinaison sous $ r = g \ <b $

(1) Quand $ r + g \ leqq b $ À ce stade, $ r et g $ peuvent être combinés avec $ b $, donc $ m + r + g $ est affiché.

(2) Lorsque $ r + g> b $ $ r, g $ sont décalés de $ b $. Autrement dit, $ r et g $ peuvent être combinés avec $ b $ par $ [\ frac {b} {2}] $. De plus, comme les $ r et g $ restants sont le même nombre, vous pouvez combiner $ r et g $ ensemble. Par conséquent, vous pouvez afficher $ m + [\ frac {b} {2}] \ times 2 + r (= m + [\ frac {b} {2}] \ times 2 + g) $ ($ dans cette formule). r, g $ est le reste).

A.py

for _ in range(int(input())):
    r,g,b=sorted(list(map(int,input().split())))
    m=g-r
    g-=m
    b-=m
    #print(r,g,b)
    if r+g<=b:
        print(m+r+g)
    else:
        n=b
        r-=n//2
        g-=n//2
        print(m+n//2*2+r)

Problème B

Puisque ** $ n $ vaut au plus 10 **, vous pouvez tout changer en ne changeant qu'un seul chiffre. Par conséquent, le nombre minimum de modifications à modifier est de (le nombre du même code PIN) -1, et vous pouvez l'enregistrer dans le dictionnaire en tant que (PIN, nombre) et le compter. De plus, ** générez un code PIN pour que le nouveau ne corresponde pas à celui d'origine, mais vous pouvez utiliser le dictionnaire ci-dessus et le modifier le nombre minimum de fois afin que seul le premier chiffre ne soit pas couvert. .. L'idée en elle-même est simple, je ferai donc de mon mieux en ** concevant l'implémentation **.

B.py

for _ in range(int(input())):
    n=int(input())
    d=dict()
    c=[]
    for i in range(n):
        x=input()
        if x in d:
            d[x]+=1
        else:
            d[x]=1
        c.append(x)
    ans=0
    for i in d:
        ans+=(d[i]-1)
    ansa=[]
    for i in range(n):
        if d[c[i]]==1:
            ansa.append(c[i])
            continue
        for j in range(10):
            x=f"{j}"+c[i][1:]
            if x not in d:
                d[c[i]]-=1
                d[x]=1
                ansa.append(x)
                break
    print(ans)
    for i in range(n):
        print(ansa[i])

Problème C

J'en suis accro pour une raison quelconque. Vous devriez aimer ce genre de problème ...

Puisque $ n $ est fixé à $ [\ frac {n} {k}] $, nous allons expérimenter pour voir le comportement en déplaçant ** $ k $ **. Ici, $ n $ donné dans l'exemple est petit et le comportement ne peut pas être saisi, donc si vous pensez à $ n = 100 $, ce sera comme suit. De plus, [] est omis.

Ensuite, vous pouvez voir que les réponses sont continues à $ k \ geqq 8 $. Par conséquent, ** on suppose que tous les nombres après le nombre continu sont continus jusqu'à 0 **, tous sont répertoriés jusqu'à ce que les nombres continus apparaissent, et après cela, ils sont répertoriés dans l'ordre jusqu'à 0 et le tri croissant est sorti. J'ai décidé de. Aussi, bien que je ne l'ai pas prouvé, considérons le graphique de ** $ f (k) = \ frac {n} {k} $ ** et la pente devient plus petite à mesure que $ k $ augmente, et $ k $ devient Cela va de soi car il approche progressivement de 0 à mesure qu'il grossit.

C.py

for _ in range(int(input())):
    n=int(input())
    ans=[]
    i=1
    while i<n:
        if len(ans)!=0:
            if ans[-1]==n//i:
                break
        ans.append(n//i)
        i+=1
    if len(ans)==0:
        print(2)
        print("0 1")
        continue
    for i in range(ans[-1]-1,-1,-1):
        ans.append(i)
    print(len(ans))
    print(" ".join(map(str,ans[::-1])))

Problème D

Je pensais que D était plus facile que C. Mettez-le simplement en œuvre. Cela a pris du temps car $ a, b, c $ sont apparus dans l'énoncé du problème et j'ai été confondu avec l'alphabet.

Pour résumer brièvement l'énoncé du problème, outre le fait que ceux contenant le même alphabet peuvent être considérés comme le même mot de passe, les mots de passe de ○, △, □ incluent le même alphabet entre ○, △ et entre △, □. Si le même alphabet est inclus dans, ○, △, □ peut être considéré comme le même mot de passe.

Par conséquent, si vous pensez que ** le même ensemble de mots de passe est transformé en le même ensemble **, vous pouvez compter le nombre d'ensembles ** dans le système d'ensemble élémentaire, vous pouvez donc penser à Union Find.

Tant qu'ils contiennent le même alphabet, nous examinerons chaque mot de passe pour voir s'il contient les alphabets $ a $ ~ $ z $. Puis enregistrez-le sous $ ca [i]: = $ (un tableau contenant l'index du mot de passe contenant l'alphabet $ i $). Ensuite, tout ce que vous avez à faire est d'unir les éléments de chaque tableau, afin que vous puissiez unir les éléments (index) avant et après ** dans ce tableau **. Si vous faites cela dans n'importe quel alphabet puis appelez la fonction de groupe, la taille du groupe sera la réponse. De plus, si vous séparez la boucle qui stocke dans le tableau et la boucle qui unit, vous pouvez éviter toute confusion dans l'implémentation.

C.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
//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é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]].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;cin>>n;
    UnionFind uf(n);
    vector<vector<ll>> alp(26);
    REP(i,n){
        string s;cin>>s;
        vector<bool> ca(26);
        FORA(i,s){
            ca[ll(i-'a')]=true;
        }
        REP(j,26){
            if(ca[j])alp[j].PB(i);
        }
    }
    REP(i,26){
        ll l=SIZE(alp[i]);
        if(l==0 or l==1)continue;
        REP(j,l-1){
            uf.unite(alp[i][j],alp[i][j+1]);
        }
    }
    uf.grouping();
    cout<<SIZE(uf.group)<<endl;
}

Problème E

Je ne vais pas améliorer cette fois car j'ai rendu l'implémentation boguée et flétrie. La solution est décrite ci-dessous.

** Puisqu'il s'agit d'une chaîne de parenthèses, c'est une condition qu'il soit toujours 0 ou plus et le dernier élément est 0 lorsque la somme cumulée est prise avec (+1,) comme -1. De plus, en réécrivant les parenthèses à la position du curseur, ** la somme cumulée après cette position change uniformément dans la plage de -2 à 2 **. Vous devez également trouver la profondeur d'imbrication maximale lorsque les parenthèses sont maintenues, qui est ** le maximum des sommes cumulées **.

Par conséquent, il peut être résolu en ayant la position du curseur, la chaîne de caractères actuelle et les deux arbres de segment de RMQ (min) et RMQ (max) pour mettre à jour l'intervalle. Cependant, je n'avais pas d'arbre seg, donc je l'ai fait bugger. Je pense utiliser une version améliorée de l'arborescence Seg fournie par ACL ou l'arborescence Seg de quelqu'un d'autre, mais ce n'est pas facile à mettre en œuvre. Peut-être que je le maintiendrai quand j'en aurai envie.

Après problème F

Je vais sauter cette fois.