Codeforces Round # 639 (Div.2) Examen Bacha (9/4)

Les résultats de cette fois

スクリーンショット 2020-09-04 16.07.10.png

Impressions de cette époque

Problème A

Premièrement, si le plus petit de $ n $ et $ m $ est 1, vous pouvez le créer en connectant les parties concave et convexe dans l'ordre. Dans d'autres cas, il n'est valable que lorsque $ n = m = 2 $. (J'y ai bien réfléchi et j'ai fait 1WA.)

J'y ai pensé expérimentalement, mais si je le considère correctement, ce sera comme suit. ** Comme il y a peu de parties concaves, je veux l'utiliser autant que possible à la limite **. Par conséquent, cela peut être fait si le nombre de frontières est inférieur au nombre de parties concaves. Ici, la partie frontière n'est que de $ n \ fois (m-1) + (n-1) \ fois m $, mais le nombre d'énigmes (le nombre de parties concaves) est de $ n \ fois m $. Par conséquent, $ n \ times (m-1) + (n-1) \ times m \ leqq n \ times m $ doit tenir. À ce stade, il s'agit de $ (n -1) (m-1) \ leqq 1 , qui est " n = 1 $ ou $ m = 1 " ou " n = 2 $ et $ m = 2 $". Est la même valeur que. De cette manière, il ne pouvait être montré que par transformation de formule.

A.py


for _ in range(int(input())):
    x=list(map(int,input().split()))
    if min(x)==1 or max(x)==2:
        print("YES")
    else:
        print("NO")

Problème B

Premièrement, quand j'ai réfléchi au nombre de cartes dont j'avais besoin pour chaque pyramide, j'ai trouvé que lorsque la hauteur augmentait, elle augmentait de l'ordre de 2 $ \ rightarrow 7 \ rightarrow 15 \ rightarrow 26 \ rightarrow . Aussi, il est clair qu'il augmente récursivement **, et le nombre de cartes augmente en fonction de la colonne des nombres de différence ( a \ _ {i + 1} = a \ _ i + 3i + 5 $).

De plus, comme on vous demandera à plusieurs reprises dans la requête, ** demandez le nombre de cartes nécessaires pour créer chaque pyramide en premier **, mais comme le nombre de cartes est au maximum de 10 $ ^ 9 $, vous avez besoin de plus que cela. Vous n'avez pas à penser à la pyramide. De plus, des expériences ont montré que la hauteur d'une pyramide qui peut être faite avec ** 10 $ ^ 9 $ est au maximum de 25820 $ **, il est donc nécessaire de faire une pyramide d'une hauteur de 1 $ $ ~ 25820 $. Liste tous les nombres de cartes (check).

Pensez ensuite à traiter la requête. Ici, il est nécessaire de faire la plus haute pyramide qui puisse être faite avec les cartes $ n $ données, afin que vous puissiez faire une pyramide inférieure des pyramides trouvées par bisect_right à partir de check. est. ** Vous pouvez penser aux cartes excédentaires avec une fonction récursive ** et afficher le total.

B.py


check=[2]
i=0
while check[-1]<=10**9:
    check.append(check[-1]+3*i+5)
    i+=1
print(len(check))
from bisect import bisect_right
def dfs(x):
    if x<2:
        return 0
    return dfs(x-check[bisect_right(check,x)-1])+1
for _ in range(int(input())):
    n=int(input())
    print(dfs(n))

Problème C

J'ai trouvé ce problème intéressant.

Considérez s'il y a une correspondance à la suite de la lecture aléatoire. Premièrement, la généralisation de ce shuffle est $ k \ rightarrow k + a_ {k \ mod \ n} $. Considérant s'il sera dupliqué dans la lecture aléatoire à ce moment, il ne sera pas dupliqué lorsque ** $ mod \ n $ sont égaux **. Par exemple, $ k $ et $ k + n $ $ mod \ n $ sont égaux, mais $ k + n \ rightarrow k + n + a_ {k \ mod \ n} $, donc même si vous mélangez Cela ne se chevauche pas.

Par conséquent, lors de la lecture aléatoire, ** considérez quel $ mod \ n $ numéro de pièce à déplacer de chaque $ mod \ n $ numéro de pièce **, et ** $ mod \ n $ peuvent correspondre. Assurez-vous simplement de faire **. Par conséquent, pour $ i = 0 $ ~ $ n-1 $, trouvez $ (i + a_ {i \ mod \ n}) \ mod \ n $ pour trouver une correspondance. De plus, si vous affectez la valeur obtenue à la structure d'ensemble, il vous suffit de déterminer si la taille de la structure d'ensemble est $ n $.

C.py


for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    s=set()
    for i in range(n):
        s.add((i+a[i%n])%n)
    #print(s)
    print("YES" if len(s)==n else "NO")

Problème D

** J'ai mal compris le sujet et fait de nombreuses erreurs **. C'était regrettable. Immédiatement après le concours, la solution était de combler les bugs petit à petit, mais je pense que ** je pourrais le résoudre sans bugs et l'implémentation était légère si je pouvais terminer l'examen, donc je le regrette.

Premièrement, le sud peut être ** placé à votre convenance **. Ici, ** chaque mouvement est dans la même ligne ou colonne **, alors concentrons-nous sur chaque ligne (ou colonne). À ce stade, ** S'il n'y a pas de sud aux extrémités gauche et droite de la partie noire d'une ligne, cette ligne ne peut pas être tracée par le nord **. De plus, lorsque le sud est placé sur les bords gauche et droit, le nord peut passer entre eux, donc ** il doit être peint en noir du bord gauche au bord droit **.

En plus de ce qui précède, la règle 1 exige également qu'il y ait au moins un aimant sud dans chaque rangée et colonne. À ce stade, il suffit qu'une cellule noire existe dans une ligne et une colonne, mais ** Si elle n'existe pas mais ne partage pas une ligne et une colonne avec une autre cellule noire, placez-la au sud. Je peux**. De plus, si vous considérez ** les cellules comme l'intersection de lignes et de colonnes **, vous pouvez la paraphraser comme ** s'il y a au moins une ligne et une colonne sans cellules noires **.

Si le jugement ci-dessus est correct dans une ligne et une colonne, le sujet peut être satisfait. À ce stade, le nombre requis de ** nord correspond au nombre de composants connectés ** lorsque le carré noir est considéré comme l'apex. Le nombre de composants liés est toujours compté dans Union Find, mais comme il se trouve sur la grille **, le nombre est compté à l'aide de BFS **. Ensuite, sortez simplement cette valeur.

Le premier code est après le concours et le deuxième code est à réviser.

D_worse.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

deque<pair<ll,ll>> d;
vector<vector<bool>> bfs_chk;
ll n,m;

void bfs(){
    while(SIZE(d)){
        ll l=SIZE(d);
        REP(i,l){
            ll c0,c1;c0=d.front().F;c1=d.front().S;
            //cout<<c0<<" "<<c1<<endl;
            vector<pair<ll,ll>> nex={MP(c0-1,c1),MP(c0+1,c1),MP(c0,c1-1),MP(c0,c1+1)};
            FORA(j,nex){
                //cout<<1<<endl;
                if(0<=j.F and j.F<n and 0<=j.S and j.S<m){
                    //cout<<j.F<<" "<<j.S<<endl;
                    if(!bfs_chk[j.F][j.S]){
                        bfs_chk[j.F][j.S]=true;
                        d.PB(j);
                        //cout<<1<<endl;
                    }
                }
            }
            d.pop_front();
        }
    }
}

signed main(){
    //Code pour accélérer la saisie
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    cin>>n>>m;
    vector<string> s(n);REP(i,n)cin>>s[i];
    bfs_chk=vector<vector<bool>>(n,vector<bool>(m,true));
    REP(i,n)REP(j,m)bfs_chk[i][j]=(s[i][j]=='.');
    ll ans=0;
    //cout<<1<<endl;
    REP(i,n){
        REP(j,m){
            if(bfs_chk[i][j]==false){
                bfs_chk[i][j]=true;
                d.PB(MP(i,j));
                bfs();
                ans++;
            }
        }
    }
    //cout<<1<<endl;
    vector<bool> r(n,false);
    vector<bool> c(m,false);
    REP(i,n){
        REP(j,m){
            if(s[i][j]=='#'){
                FOR(k,j,m-1){
                    if(s[i][k]=='.'){
                        FOR(l,k,m-1){
                            if(s[i][l]=='#'){
                                //cout<<2<<endl;
                                cout<<-1<<endl;
                                return 0;
                            }
                        }
                        break;
                    }else{
                        c[j]=true;
                        r[i]=true;
                    }
                }
                break;
            }
        }
    }
    REP(i,m){
        REP(j,n){
            if(s[j][i]=='#'){
                FOR(k,j,n-1){
                    if(s[k][i]=='.'){
                        FOR(l,k,n-1){
                            if(s[l][i]=='#'){
                                //cout<<3<<endl;
                                cout<<-1<<endl;
                                return 0;
                            }
                        }
                        break;
                    }else{
                        r[j]=true;
                        c[i]=true;
                    }
                }
                break;
            }
        }
    }

    //Si vous pouvez ajouter
    pair<vector<ll>,vector<ll>> addition;
    REP(i,n){
        ll co=0;
        REP(j,m){
            co+=ll(s[i][j]=='#');
        }
        if(co==0)addition.F.PB(i);
    }
    REP(j,m){
        ll co=0;
        REP(i,n){
            co+=ll(s[i][j]=='#');
        }
        if(co==0)addition.S.PB(j);
    }
    FORA(i,addition.F){
        FORA(j,addition.S){
            r[i]=true;
            c[j]=true;
        }
    }

    //REP(i,n)cout<<r[i]<<endl;
    //REP(i,m)cout<<c[i]<<endl;
    if(all_of(ALL(r),[](boolx){returnx;})andall_of(ALL(c),[](boolx){returnx;})){
        cout<<ans<<endl;
    }else if(all_of(ALL(r),[](boolx){return!x;})andall_of(ALL(c),[](boolx){return!x;})){
        cout<<ans<<endl;
    }else{
        //cout<<4<<endl;
        cout<<-1<<endl;
    }
}

D_better.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

deque<pair<ll,ll>> d;
vector<vector<bool>> bfs_chk;
ll n,m;

void bfs(){
    while(SIZE(d)){
        ll l=SIZE(d);
        REP(i,l){
            ll c0,c1;c0=d.front().F;c1=d.front().S;
            //cout<<c0<<" "<<c1<<endl;
            vector<pair<ll,ll>> nex={MP(c0-1,c1),MP(c0+1,c1),MP(c0,c1-1),MP(c0,c1+1)};
            FORA(j,nex){
                //cout<<1<<endl;
                if(0<=j.F and j.F<n and 0<=j.S and j.S<m){
                    //cout<<j.F<<" "<<j.S<<endl;
                    if(!bfs_chk[j.F][j.S]){
                        bfs_chk[j.F][j.S]=true;
                        d.PB(j);
                        //cout<<1<<endl;
                    }
                }
            }
            d.pop_front();
        }
    }
}

signed main(){
    //Code pour accélérer la saisie
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    cin>>n>>m;
    vector<string> s(n);REP(i,n)cin>>s[i];
    
    //cout<<1<<endl;
    ll f=0;ll g=0;
    REP(i,n){
        ll li=-1;ll ri=-1;
        //Extrémité gauche
        REP(j,m){
            if(s[i][j]=='#'){
                li=j;
                break;
            }
        }
        //Extrémité droite
        REPD(j,m){
            if(s[i][j]=='#'){
                ri=j;
                break;
            }
        }
        if(li==-1 and ri==-1){
            f++;
            continue;
        }
        FOR(j,li,ri){
            if(s[i][j]!='#'){
                cout<<-1<<endl;
                return 0;
            }
        }
    }
    REP(j,m){
        ll ui=-1;ll di=-1;
        //Bord supérieur
        REP(i,n){
            if(s[i][j]=='#'){
                ui=i;
                break;
            }
        }
        //Bas de gamme
        REPD(i,n){
            if(s[i][j]=='#'){
                di=i;
                break;
            }
        }
        if(ui==-1 and di==-1){
            g++;
            continue;
        }
        FOR(i,ui,di){
            if(s[i][j]!='#'){
                cout<<-1<<endl;
                return 0;
            }
        }
    }
    //Quand tu ne peux pas mettre le sud dans le bon sens
    if((f==0 and g!=0)or(f!=0 and g==0)){
        cout<<-1<<endl;
        return 0;
    }
    bfs_chk=vector<vector<bool>>(n,vector<bool>(m,true));
    REP(i,n)REP(j,m)bfs_chk[i][j]=(s[i][j]=='.');
    ll ans=0;
    //cout<<1<<endl;
    REP(i,n){
        REP(j,m){
            if(bfs_chk[i][j]==false){
                bfs_chk[i][j]=true;
                d.PB(MP(i,j));
                bfs();
                ans++;
            }
        }
    }
    cout<<ans<<endl;
}

Après le problème E

Je vais sauter cette fois

Recommended Posts

Codeforces Round # 654 (Div.2) Critique Bacha (8/18)
Codeforces Round # 594 (Div.2) Examen Bacha (10/29)
Codeforces Round # 609 (Div.2) Critique Bacha (10/8)
Codeforces Round # 597 (Div.2) Examen Bacha (10/27)
Codeforces Round # 666 (Div.2) Examen Bacha (9/2)
Codeforces Round # 651 (Div.2) Critique Bacha (8/20)
Codeforces Round # 659 (Div.2) Critique Bacha (8/5)
Codeforces Round # 610 (Div.2) Critique Bacha (10/5)
Codeforces Round # 603 (Div.2) Examen Bacha (10/15)
Codeforces Round # 600 (Div.2) Examen Bacha (10/21)
Codeforces Round # 481 (Div.3) Examen Bacha (9/24)
Codeforces Round # 639 (Div.2) Examen Bacha (9/4)
Codeforces Round # 612 (Div.2) Examen Bacha (10/2)
Codeforces Round # 521 (Div.3) Examen Bacha (10/9)
Codeforces Round # 652 (Div.2) Examen Bacha (8/24)
Codeforces Round # 673 (Div.2) Examen Bacha (10/22)
Codeforces Round # 606 (Div.3) Examen Bacha (10/13)
Codeforces Round # 613 (Div.2) Examen Bacha (10/1)
Codeforces Round # 665 (Div.2) Examen Bacha (8/23)
Codeforces Round # 592 (Div.2) Examen Bacha (11/03)
Codeforces Round # 662 (Div.2) Critique Bacha (8/8)
Codeforces Round # 618 (Div.2) Examen Bacha (9/26)
Codeforces Round # 648 (Div.2) Critique Bacha (9/5)
Codeforces Round # 676 (Div.2) Examen Bacha (10/31)
Codeforces Round # 675 (Div.2) Examen Bacha (10/30)
Codeforces Round # 486 (Div.3) Examen Bacha (9/23)
Codeforces Round # 671 (Div.2) Examen Bacha (9/22)
Codeforces Round # 669 (Div.2) Examen Bacha (9/9)
Codeforces Round # 672 (Div.2) Examen Bacha (10/16)
Codeforces Round # 638 (Div.2) Examen Bacha (9/16)
Codeforces Round # 663 (Div.2) Examen Bacha (8/13)
Codeforces Round # 668 (Div.2) Examen Bacha (9/7)
Codeforces Round # 663 (Div.2) Examen Bacha (8/16)
Codeforces Round # 609 (Div.2) Examen Bacha (10/6)
Codeforces Round # 645 (Div.2) Critique Bacha (9/10)
Codeforces Round # 664 (Div.2) Examen Bacha (8/13)
Codeforces Round # 660 (Div.2) Critique Bacha (8/4)
Codeforces Round # 643 (Div.2) Révision
Codeforces Round # 679 (Div.2) Révision (10/25)
Codeforces Round # 657 (Div.2) Révision
Code de l'éducation forces Round 93 Bacha Review (8/17)
Code de l'éducation forces Round 94 Bacha Review (9/3)
Code de l'éducation forces Round 91 Bacha Review (7/28)
Code de l'éducation forces Round 88 Bacha Review (8/4)
Code de l'éducation forces Round 86 Bacha Review (9/17)
Code de l'éducation forces Round 89 Bacha Review (9/8)
Code de l'éducation forces Round 92 Bacha Review (7/30)
Code de l'éducation forces Round 90 Bacha Review (8/19)
Codeforces Round # 609 (Div.2) (jusqu'à B)
Code de l'Éducation Forces Round 87
Codeforces Beta Round # 13
Codeforces Beta Round # 1
Codeforces Beta Round # 2
DP100 Question Bacha Review 1 ~ 10 (8 / 26,27)
Codeforces Round # 626 B.Compte des sous-rectangles