Codeforces Round # 669 (Div.2) Examen Bacha (9/9)
Les résultats de cette fois
Impressions de cette époque
Pendant le concours, j'ai mis sur écoute toute ma vie sans remarquer le ** bâillon de A **. Ensuite, j'ai eu moins de temps pour aller chez D. C'était un cercle vicieux.
Après avoir fait un bug en D pour le reste de ma vie, je sens que j'aurais passé un total d'environ 4 heures après le concours si j'avais résolu le problème D correctement sans trop prendre en compte le problème. Ce n'est pas bon mentalement, donc ce genre de problème devrait être résolu immédiatement.
Je n'ai pas pu résoudre ** D, mais je l'aime vraiment **, alors j'aimerais pouvoir le résoudre lorsque des problèmes similaires surviennent à l'avenir.
Problème A
Au début, j'ai pensé à gérer la différence entre 0 et 1 avec DP, mais j'ai senti que c'était gênant et je ne pouvais pas l'implémenter. Quand je le regardais sur Twitter, il y avait des gens qui pouvaient le résoudre avec DP, donc je pense que ce domaine n'est ** pas assez d'esprit **. Je vais me consacrer.
C'est facile si vous remarquez le bâillon.
Après tout, il reste plus de $ \ frac {n} {2} $, alors envisagez ** de choisir plus de $ \ frac {n} {2} $ **. Une idée simple consiste à ** définir tous les éléments sélectionnés sur 0 **, mais cela est possible s'il y a plus de $ \ frac {n} {2} $ 0 dedans. De plus, lorsque 0 est inférieur à $ \ frac {n} {2} $, 1 est $ \ frac {n} {2} + 1 $ ou plus, mais s'il existe un nombre pair de ** 1, le total est de 0 **. Vous pouvez générer $ \ frac {n} {2} $ ou $ \ frac {n} {2} + 1 $ 1s par la régularité de $ \ frac {n} {2} $.
A.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
if a.count(0)>=n/2:
print(n//2)
print(" ".join("0"*(n//2)))
else:
#À ce moment, 1 est n//2+1 ou plus
if (n//2)%2==0:
print(n//2)
print(" ".join("1"*(n//2)))
else:
print(n//2+1)
print(" ".join("1"*(n//2+1)))
Problème B
Comme l'énoncé du problème est un peu compliqué, pour résumer, la colonne numérique $ c $ est nouvellement ajoutée à la colonne numérique $ b $ en réorganisant la séquence $ a $ $ c \ _i = GCD (b \ _1, b \ _2,…, b \ _i) Le problème est de trouver $ b $ quand $ c $ est le maximum dans l'ordre lexical lorsqu'il est défini comme $. Aussi, pour $ b $, vous pouvez en trouver un qui répond aux conditions.
** Puisqu'il est dans l'ordre lexical, pensez à l'augmenter avidement à partir du premier élément ** Comme vous pouvez le voir, le premier élément de $ b $ est le plus grand élément de $ a $. De plus, pour le deuxième élément et les éléments suivants $ i $ th, si vous demandez le GCD (now) du premier à $ i-1 $ th éléments, c'est le plus grand parmi les éléments prenant now et GCD. Vous pouvez sélectionner l'élément de comme élément suivant. De plus, vous pouvez prendre la politique de ** $ O (N ^ 2) $ **, alors préparez un tableau check pour enregistrer l'élément que vous avez sélectionné, et l'élément de check [i] = False. Vous pouvez trouver l'élément qui maximise GCD dans l'ordre.
B.py
from math import gcd
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
check=[False]*n
b=[0]*n
b[0]=max(a)
check[a.index(max(a))]=True
now=b[0]
for i in range(1,n):
#valeur,indice
max1=[-1,-1]
for j in range(n):
if not check[j]:
if max1[0]<gcd(a[j],now):
max1=[gcd(a[j],now),j]
check[max1[1]]=True
b[i]=a[max1[1]]
now=max1[0]
print(" ".join(map(str,b)))
Problème C
J'ai résolu un problème interactif pour la première fois. Ce problème n'était pas difficile, mais je veux pouvoir résoudre des problèmes interactifs sans aucune résistance.
Pour résumer ce problème, "Pour une séquence inconnue $ p $ composée de 1 ~ $ n $, si vous passez $ i, j $, vous obtiendrez $ p \ _i \ mod \ \ _ {p \ _ j} $. Répétez-le au maximum 2n $ fois pour restaurer $ p $. "
Ici, je pensais que ce serait décidé dans l'ordre du plus grand élément ou du plus petit élément. Par exemple, $ p \ _i \ mod \ \ _ {p \ _ j} = n-1 $ est unique uniquement lorsque $ (p \ _ i, p \ _j) = (n-1, n) $ Si vous utilisez $ mod \ _ {n} $, les autres éléments seront déterminés de manière unique. Cependant, il est difficile de trouver les éléments qui sont ** $ n-1 $ et $ n $ car ce sera $ O (n ^ 2) $ **. J'ai abandonné le plus petit élément car il semble difficile de le déterminer uniquement en premier lieu.
Ici, en faisant attention à $ p \ _i \ mod \ \ _ {p \ _j} $, quand ** $ p \ _ j> p \ _i $, $ p \ _i $ est déterminé de manière unique ** J'ai remarqué. Cependant, puisque la taille n'est pas uniquement déterminée à partir de la valeur de $ p \ _i \ mod \ \ _ {p \ _j} $, ** $ p \ _ j \ mod \ \ _ {p \ _i} $ est combiné. J'ai pensé à décider de la taille **.
En supposant que $ p \ _j > p \ _i $, $ p \ _i \ mod \ \ _ {p \ _ j} = p \ _i $, $ p \ _ j \ mod \ \ _ {p \ _i Les deux équations de} \ <p \ _i $ sont valables. Par conséquent, il devient $ p \ _i \ mod \ \ _ {p \ _ j} > p \ _ j \ mod \ \ _ {p \ _i} $. Au contraire, quand $ p \ _i \ mod \ \ _ {p \ _ j} > p \ _j \ mod \ \ _ {p \ _i} $, $ p \ _j > p \ _i $ et $ p \ Puisque _i \ mod \ \ _ {p \ _j} = p \ _i $ tient, vous pouvez décider $ p \ _i $.
Par conséquent, le plus petit élément peut être déterminé en demandant ** $ p \ _i \ mod \ \ _ {p \ _ j} $ et $ p \ _ j \ mod \ \ _ {p \ _i} $ ** Je comprends. Par conséquent, en faisant cela pour n'importe quel élément, vous pouvez définir des éléments $ n-1 $ dans $ 2 (n-1) $ questions. De plus, le dernier élément restant est le plus grand élément, donc ce sera $ n $.
De plus, pour ** produire immédiatement **, Python doit donner $ flush = True $ comme argument à la fonction d'impression. Je l'utilise toujours pour des problèmes interactifs, donc je veux m'en souvenir.
C.py
for _ in range(int(input())):
n,k=map(int,input().split())
s=input()
t=[[] for i in range(k)]
for i in range(n):
t[i%k].append(s[i])
#S'il y a quelque chose de différent, non à ce stade
ans0,ans1=0,0
ex=0
for i in range(k):
if t[i].count("0")>0 and t[i].count("1")>0:
print("NO")
break
elif t[i].count("0")>0:
ans0+=1
elif t[i].count("1")>0:
ans1+=1
else:
ex+=1
else:
if ex==0:
if ans0==ans1:
print("YES")
else:
print("NO")
else:
if ans0+ex>=k//2 and ans1+ex>=k//2:
print("YES")
else:
print("NO")
Problème D
Même si j'ai trouvé la bonne réponse après le concours, ** j'ai passé beaucoup de temps à cause du manque de considération **. J'aimerais avoir un peu de temps pour vérifier si la solution est vraiment correcte avant la mise en œuvre.
Les discussions pendant le concours étaient assez sales, alors j'aimerais considérer celles qui semblent bonnes.
Tout d'abord, il n'y a pas de meilleur modèle pour sauter de droite à gauche, donc si vous pouvez ** saisir tous les moyens de sauter de gauche à droite, il est facile de saisir le saut en tant que ** transition DP **. Vous pouvez demander.
Aussi, comme saut, le deuxième ($ max (h \ _ {i + 1},…, h_ {j-1}) \ <min (h \ _ i, h \ _ j)
Considérez le deuxième saut. Facile pour $ h \ _i \ leqq h \ _j $, sautez de $ i $ au plus petit $ j $ ** qui rencontre ** $ j> i $ et $ h \ _j \ geqq h \ _i $ pouvez. Lorsque $ h \ _i \ geqq h \ _j $, vous pouvez sauter du maximum $ i $ ** qui satisfait ** $ i <j $ et $ h \ _i \ geqq h \ _j $ à $ j $. Je peux le faire.
En considérant le troisième saut de la même manière, il y a les quatre transitions suivantes. De plus, cela vaut si $ i <j $ est arbitraire.
(1) Passer de $ i $ au plus petit $ j $ qui satisfait $ h \ _i \ leqq h \ _j $
(2) Passer du maximum $ i $ qui satisfait $ h \ _i \ geqq h \ _j $ à $ j $
(3) Passer de $ i $ au plus petit $ j $ qui satisfait $ h \ _i \ geqq h \ _j $
(4) Passer du maximum $ i $ qui satisfait $ h \ _i \ leqq h \ _j $ à $ j $
Si c'est $ O (N ^ 2) $, il peut être facilement obtenu, mais c'est difficile à moins qu'il ne s'agisse de $ O (N \ log {N}) $ en raison de contraintes, alors ** les informations de la destination de la transition (ou de la source de la transition) sont efficaces. Pensez à bien épargner . La structure d'ensemble qui peut stocker les éléments par ordre croissant est utilisée ci-dessous. ( Mettre des informations non résolues dans un ensemble ou un multiset ** semble être typique.)
Premièrement, dans le cas de (1), les informations de (hauteur, index) sont stockées dans set. De plus, cet ensemble contient des ** éléments ** dont la destination de transition n'est pas déterminée lorsque l'on regarde le 0e au $ i $ th. Ici, quand vous regardez le $ i + 1 $ ème élément $ h [i + 1] $, pour les éléments qui sont inférieurs à $ h [i + 1] $ dans l'ensemble, ** destination de la transition Il peut être défini comme $ i + 1 $ **. Vous pouvez définir la transition en faisant cela pour tout $ i $. Aussi, dans le cas de (3), la transition peut être déterminée simplement en reformulant l'élément qui est inférieur à $ h [i + 1] $ avec l'élément qui est supérieur à $ h [i +] $.
Dans le cas de (2), les informations de (hauteur, index) sont stockées dans set. Cet ensemble a ** $ i $ ~ $ n $ th éléments ** dont la source de transition n'est pas fixe. Ici, en regardant le $ i-1 $ ème élément $ h [i-1] $, pour les éléments inclus dans l'ensemble qui sont $ h [i-1] $ ou plus, ** la source de la transition Il peut être défini comme $ i-1 $ **. Vous pouvez définir la transition en faisant cela pour tout $ i $. De plus, dans le cas de (4), la transition peut être déterminée simplement en reformulant l'élément supérieur ou égal à $ h [i] $ par l'élément supérieur ou égal à $ h [i] $.
Dans le cas de (1) et (3), il existe une possibilité que les destinations de transition se chevauchent **, et dans le cas de (2) et (4), il existe une possibilité que les sources de transition se chevauchent. Soyez prudent dans ce dernier cas.
Quoi qu'il en soit, puisque nous avons pu énumérer toutes les transitions des deuxième et troisième modèles par $ O (N \ log {N}) $, nous devrions considérer DP avec la transition du premier modèle.
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
//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 MOD 1000000007 //10^9+7:Droit commun
#define INF 1000000000000 //10^12
#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
signed main(){
//Code pour accélérer la saisie
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n;cin>>n;
vector<ll> h(n);REP(i,n)cin>>h[i];
vector<ll> move1(n);
vector<ll> move2(n);
vector<vector<ll>> move3(n);
vector<vector<ll>> move4(n);
//Autre que juste aller à droite
//Première minute
set<pair<ll,ll>> minm;
minm.insert(MP(h[0],0));
FOR(i,1,n-1){
if(SIZE(minm)==0){
minm.insert(MP(h[i],i));
continue;
}
//upper_Lié et dangereux à côté! !!(Je l'ai fait bug pour le reste de ma vie)
auto x=minm.begin();
while(x!=minm.end() and *x<=MP(h[i],n)){
move1[x->S]=i;
x=minm.erase(x);
}
minm.insert(MP(h[i],i));
}
//Puis max
set<pair<ll,ll>> maxm;
maxm.insert(MP(h[0],0));
FOR(i,1,n-1){
if(SIZE(maxm)==0){
maxm.insert(MP(h[i],i));
continue;
}
auto x=maxm.lower_bound(MP(h[i],0));
while(x!=maxm.end()){
move2[x->S]=i;
x=maxm.erase(x);
}
maxm.insert(MP(h[i],i));
}
//Depuis l'autre côté(Ce modèle!)
//Première minute
set<pair<ll,ll>> mint;
mint.insert(MP(h[n-1],n-1));
FORD(i,n-2,0){
if(SIZE(mint)==0){
mint.insert(MP(h[i],i));
continue;
}
//upper_Lié et dangereux à côté! !!(Je l'ai fait bug pour le reste de ma vie)
auto x=mint.begin();
while(x!=mint.end() and *x<=MP(h[i],n)){
move3[i].PB(x->S);
x=mint.erase(x);
}
mint.insert(MP(h[i],i));
}
//Puis max
set<pair<ll,ll>> maxt;
maxt.insert(MP(h[n-1],n-1));
FORD(i,n-2,0){
if(SIZE(maxt)==0){
maxt.insert(MP(h[i],i));
continue;
}
auto x=maxt.lower_bound(MP(h[i],0));
while(x!=maxt.end()){
move4[i].PB(x->S);
x=maxt.erase(x);
}
maxt.insert(MP(h[i],i));
}
vector<ll> dp(n,INF);
dp[0]=0;
REP(i,n-1){
dp[i+1]=min(dp[i+1],dp[i]+1);
dp[move1[i]]=min(dp[move1[i]],dp[i]+1);
dp[move2[i]]=min(dp[move2[i]],dp[i]+1);
FORA(j,move3[i])dp[j]=min(dp[j],dp[i]+1);
FORA(j,move4[i])dp[j]=min(dp[j],dp[i]+1);
}
cout<<dp[n-1]<<endl;
}
Après le problème E
Je vais sauter cette fois
Recommended Posts