[PYTHON] Codeforces Round # 639 (Div.2) Examen Bacha (9/4)
Les résultats de cette fois
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
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
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