[PYTHON] Codeforces Round # 668 (Div.2) Examen Bacha (9/7)
Les résultats de cette fois
Impressions de cette époque
Cette fois, je pense que je faisais face à Bachacon avec une bonne concentration. Cependant, le problème D m'a demandé ce que je n'avais pas, mais je le regrette car c'était ** une connaissance que je devrais connaître **. C'est aussi un problème que vous auriez connu si vous recherchiez pendant le Bachacon, donc parfois il peut être bon d'utiliser la recherche.
Problème A
C'était un bâillon. Si vous ne le remarquez pas, vous deviendrez fou. ** Il est bon de penser comme ** $ p \ _1, p \ _2,…, p \ _n $ sans expérimenter étrangement.
$ p \ _1 + p \ _2, p \ _2 + p \ _3,…, p \ _ {n-1} + p \ _n $, donc si vous l'inversez, $ p \ _n + p \ _ {n-1 },…, P \ _3 + p \ _2, p \ _2 + p \ _1 $, et les nombres qui apparaissent sont exactement les mêmes.
Par conséquent, vous pouvez générer ceux-ci dans l'ordre inverse.
A.py
for _ in range(int(input())):
n=int(input())
p=list(map(int,input().split()))
print(" ".join(map(str,p[::-1])))
Problème B
Quand la quantité de calcul a atteint la limite, j'étais impatient sans passer, mais c'était bien de pouvoir récupérer.
Pensez à sélectionner $ i, j $ et à le changer en $ a \ _i-1, a \ _j + 1 $. À ce stade, si $ i \ <j $, aucune pièce n'est nécessaire, si $ i > j $, une pièce est nécessaire, et considérez le nombre minimum de pièces requis pour tout faire 0 Je vais.
Dans l'expérience avec l'exemple, si vous sélectionnez $ i, j $ où ** $ a \ _i> 0, a \ _j <0 $, vous pouvez effectuer un changement ** qui s'approche de 0 sans utiliser de pièces. Je vais. De plus, en effectuant ce changement, -et + sur le côté droit resteront finalement sur le côté gauche, et pour le moment, il n'y a pas d'autre choix que d'effectuer des opérations en utilisant des pièces de monnaie. Par exemple, dans le premier exemple, tous les éléments sont mis à 0 en effectuant une opération qui n'utilise pas de pièces de «-3 2 -3 4» à «-3 0 -1 4» et en utilisant 4 pièces de cet état. Peut être
Aussi, pour la première opération qui n'utilise pas de pièces, regardez les éléments qui satisfont $ a [i]> 0 $ dans l'ordre à partir du plus petit $ i $, et utilisez $ j (> i) $ qui satisfait $ a [j] <0 $. Cela peut être fait par la méthode gourmande d'opérer à partir du plus petit $ j $ (l'image est que $ \ car $ ** a moins de choix **!). Aussi, j'ai essayé de gérer un petit $ j $ avec une structure d'ensemble avec $ j (> i) $ qui satisfait $ a [j] <0 $, mais dans ce cas, il faut plusieurs heures pour insérer, supprimer et faire référence à l'ensemble. Ce sera TLE.
Ici, $ j $ est le plus petit indice qui satisfait $ i <j, a [j] <0 $, et quand $ i $ est incrémenté de 1, $ j $ augmente de façon monotone **. Ainsi, vous pouvez avoir $ j $ comme index unique et penser à une implémentation comme ** méthode d'échelle **. Par conséquent, il peut être mis en œuvre avec le montant de calcul de $ O (N) $.
B.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
for j in range(n):
if a[j]<0:
break
for i in range(n):
if a[i]>0:
j=max(i+1,j)
while True:
if j==n:
break
if a[j]<0:
m=min(a[i],-a[j])
a[i]-=m
a[j]+=m
if a[i]==0:
break
j+=1
if j==n:
break
ans=0
#print(a)
for i in range(n):
if a[i]>0:
ans+=a[i]
print(ans)
Problème C
Notez que les sous-colonnes sont ** continues **. J'étais vif sans m'en apercevoir.
C'est une sous-chaîne continue de $ k $ de longueur, et je veux voir la différence **, j'ai donc écrit la figure ci-dessous.
Puis j'ai remarqué que les éléments avec les index $ 0 $ et $ k $ sont égaux. De plus, si cela est généralisé, les éléments des index $ i $ et $ i + k $ sont égaux, donc si les restes de la division de l'indice par $ k $ sont égaux, alors ces éléments sont égaux . Je vais. Par conséquent, vérifiez d'abord si les éléments sont égaux ( 0 et 1 ne sont pas inclus en même temps **) en divisant chaque reste d'index. S'il y a des éléments inégaux à ce stade, NON est affiché.
De plus, il est ** exigé ** que tous les éléments soient égaux pour chaque indice de reste, et le nombre de 0 et de 1 qui apparaissent dans la partie continue de longueur $ k $ comme une ** condition suffisante ** doit être égal. Doit être. Par conséquent, trouvez l'élément lorsque le reste est $ l $ pour tout $ l $. Notez également que non seulement $ 0 $ et $ 1 $ mais aussi **? **, le nombre de 0 est $ ans0 $, le nombre de 1 est $ ans1 $, et le nombre de? Est $ ex $. Je vais.
Considérez suffisamment les conditions sous ceci, mais quand $ ex = 0 $, si $ ans0 = ans1 $, la condition est satisfaite, donc OUI est affiché, sinon NON est produit. Ensuite, quand $ ex \ neq 0 $, il peut être ajusté par le nombre de ?, Donc $ ans0 + ex \ geq [\ frac {k} {2}] $ et $ ans1 + ex \ geq [\ frac {k } {2}] Si c'est $, la condition est satisfaite, donc YES est affiché, sinon NO est affiché.
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
Dans ce qui suit, Alice sera abrégée en A et Bob en B. Soit A la distance parcourue une fois par $ da $, et la distance parcourue par B une fois par $ db $.
B fuit A. Puisque A est le premier joueur, ** si vous pouvez atteindre B la première fois, A gagne **. Par conséquent, considérez ** le mouvement optimal pour chaque ** alors que A ne peut pas atteindre B la première fois. Tout d'abord, considérons le mouvement optimal de B. ** B n'a pas besoin de bouger tant que A n'est pas proche de la limite **. Lorsque A s'approche de la limite, s'il y a un sommet dans la direction opposée à A, il vaut mieux s'y déplacer, mais s'il n'y a pas de tel sommet, il est nécessaire de se déplacer à travers A jusqu'à un sommet éloigné. En revanche, le mouvement optimal de A n'est pas de se rapprocher le plus possible de B, mais de se déplacer ** à une distance de $ da $. En effet, s'il se rapproche de cela, il sera plus facile pour B de s'échapper lorsqu'il chevauche A et s'échappe.
D'après les considérations ci-dessus, on pense que A est pris dans $ db \ leqq 2 \ times da $ et B continue de s'échapper dans $ db> 2 \ times da $. Cependant, ** B ne pourra peut-être pas s'échapper jusqu'ici **. Parce que $ db $ est jusqu'à $ n-1 $, mais que la distance entre les sommets de l'arbre peut être inférieure à $ n-1 $ (par exemple, un graphe en étoile). Autrement dit, $ db $ doit être ** remplacé ** par $ min (db, $ la distance maximale entre deux sommets sur l'arbre). Ici, je ne savais pas comment trouver la distance maximale entre deux sommets sur l'arbre ** dans le bachacon, mais quand je l'ai étudié, il semble que le ** diamètre de l'arbre ** corresponde à cela. Par conséquent, $ db = min (db, $ diamètre de l'arbre) doit être défini.
Le diamètre de l'arbre peut être calculé en suivant l'algorithme suivant en se référant à cet article.
Je ne vais pas en faire une bibliothèque car il est facile de faire deux fois BFS (ou DFS), mais j'aimerais pouvoir le résoudre quand je le verrai dans le futur. Aussi, comme pour la preuve, une simple est écrite dans l'article précédent.
Par conséquent, à partir de ce qui précède, il était possible de déterminer lequel de A et B gagne dans tous les cas.
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 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
ll n,a,b,da,db;
vector<vector<ll>> tree;
vector<ll> check;
vector<ll> check2;
signed main(){
//Code pour accélérer la saisie
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll t;cin>>t;
REP(_,t){
cin>>n>>a>>b>>da>>db;
tree=vector<vector<ll>>(n);
REP(i,n-1){
ll u,v;cin>>u>>v;
tree[u-1].PB(v-1);
tree[v-1].PB(u-1);
}
check=vector<ll>(n,INF);
deque<ll> d={a-1};
ll dep=0;
while(SIZE(d)){
ll l=SIZE(d);
REP(i,l){
ll now=d.front();
check[now]=dep;
FORA(j,tree[now]){
if(check[j]==INF)d.PB(j);
}
d.pop_front();
}
dep++;
}
check2=vector<ll>(n,INF);
d={ll(distance(check.begin(),max_element(ALL(check))))};
dep=0;
while(SIZE(d)){
ll l=SIZE(d);
REP(i,l){
ll now=d.front();
check2[now]=dep;
FORA(j,tree[now]){
if(check2[j]==INF)d.PB(j);
}
d.pop_front();
}
dep++;
}
//cout<<check[b-1]<<" "<<da<<endl;
if(check[b-1]<=da){
cout<<"Alice"<<endl;
//cout<<1<<endl;
continue;
}
if(min(db,*max_element(ALL(check2)))<=2*da){
cout<<"Alice"<<endl;
}else{
cout<<"Bob"<<endl;
}
}
}
Après le problème E
Je vais sauter cette fois
Recommended Posts