[PYTHON] Code de l'éducation forces Round 94 Bacha Review (9/3)
Les résultats de cette fois
Impressions de cette époque
Le temps a fondu indéfiniment parce que j'ai passé beaucoup de temps sur le problème B. En tant que reflet du problème B, je viens d'essayer de le résoudre analytiquement. ** Je pense que je pourrais le résoudre si j'exécutais intuitivement la méthode gourmande **, donc je le regrette.
Problème A
Alternez-vous 01 lorsque vous le voyez pour la première fois? Je pensais cela, mais je trouvais que c'était gênant parce que la position allait changer. Par conséquent, j'ai pensé que ce serait bien si tous les caractères étaient les mêmes pour ne pas dépendre de la position **. À ce stade, la condition en question montre que ** chaque chaîne contient $ s [n] $ **. Par conséquent, si vous créez une chaîne qui connecte $ n $ de ce caractère, le caractère correspondant à $ s [n] $ sera égal à n'importe quelle chaîne. Voilà donc la réponse.
A.py
for _ in range(int(input())):
n=int(input())
s=input()
print(n*s[n-1])
Problème B
Comme vous pouvez le voir dans l'impression, il peut être résolu par la ** méthode de la cupidité normale **.
Considérez que ** le plus léger est le meilleur ** pour en choisir le plus possible. De plus, $ s \ leqq w $ (sinon échangez la valeur). Tout d'abord, choisissez ** ce que vous emportez **, mais selon la combinaison, il peut être préférable d'en conserver les plus lourds, donc je ne suis que $ i (0 \ leqq i \ leqq cnts) $ plus légers Supposons que vous choisissiez. Aussi, à ce moment, il est nécessaire de satisfaire $ i \ times s \ leqq p $. En dessous, le nombre de plus lourds que vous pouvez choisir est $ min (\ frac {p-i \ times s} {w}, cntw) $. De plus, comme il est facile de savoir combien de chaque élément reste, ** vos abonnés doivent être sélectionnés avec avidité dans l'ordre du plus léger **. Par conséquent, le nombre de choses qui peuvent être volées lorsque $ i $ est défini est calculé par $ O (1) $, et il est possible d'écrire un programme suffisamment rapide.
B.py
for _ in range(int(input())):
p,f=map(int,input().split())
cnts,cntw=map(int,input().split())
s,w=map(int,input().split())
if s>w:
s,w=w,s
cnts,cntw=cntw,cnts
ans=0
for i in range(cnts+1):
if i*s>p:break
ans_sub=0
nows=cnts-i
ans_sub+=i
#s est sélectionné
rest1=p-i*s
#w
noww=cntw-min(rest1//w,cntw)
ans_sub+=min(rest1//w,cntw)
#Personne suivante
#s
ans_sub+=min(f//s,nows)
rest2=f-min(f//s,nows)*s
#w
ans_sub+=min(noww,rest2//w)
ans=max(ans,ans_sub)
print(ans)
Problème C
Puisque $ s $ est donné, ** $ w $ sera restauré **. Ici, quand $ s \ _i = 1 $, restaurez $ w $ à la condition que soit $ w \ _ {ix} = 1 $ soit $ w \ _ {i + x} = 1 $ soit maintenu. Comme c'est difficile, $ w $ à partir de la condition que les deux $ w \ _ {ix} = 1 $ et $ w \ _ {i + x} = 1 $ tiennent quand ** $ s \ _i = 0 $ ** J'ai décidé de restaurer.
De plus, bien qu'une partie de $ w $ ne soit pas restaurée par cette méthode, toute la partie qui n'a pas été restaurée pour satisfaire la condition ** $ s \ _i = 1 $ est mise à 1 **. À partir de ce qui précède, nous avons pu restaurer $ w $, mais nous ne savons pas s'il peut réellement être transformé de $ w $ en $ s $, nous devons donc confirmer s'il peut être transformé à la fin.
C.py
for _ in range(int(input())):
s=list(map(int,input()))
x=int(input())
n=len(s)
w=[1]*n
for i in range(n):
if s[i]==0:
if i-x>=0:
w[i-x]=0
if i+x<n:
w[i+x]=0
t=[1]*n
for i in range(n):
g=0
if i-x>=0:
if w[i-x]==1:
g+=1
if i+x<n:
if w[i+x]==1:
g+=1
if g>0:
t[i]=1
else:
t[i]=0
if s==t:
print("".join(map(str,w)))
else:
print(-1)
Problème D
Je suis devenu impatient avec MLE, mais j'étais soulagé de finir de le résoudre à temps. ** Converti pair <ll, ll> en ll et changé ll en ʻint` **.
J'ai senti que ce problème n'était pas si difficile à considérer et était un peu difficile à mettre en œuvre.
Recherchez $ i, j, k, l $ tel que $ a \ _i = a \ _k $ et $ a \ _j = a \ _l $ se trouvent sous $ i <j <k <l $. À ce moment, j'ai remarqué que ** $ (a \ _ i, a \ _ j) = (a \ _ k, a \ _l) $ détient **. De plus, comme il y a au plus 3000 $ n $, vous pouvez générer toutes les paires $ _ {3000} C_2 $. En outre, le même ensemble est assemblé par carte. En d'autres termes, supposons que $ m $ est un objet de carte, key est une paire de deux éléments et value est un vecteur, et la paire d'index qui sont les deux éléments est incluse.
Sous cela, il doit être ** $ a \ _ j <a \ _k $ ** pour être $ (a \ _i, a \ _j) = (a \ _ k, a \ _l) $. Par conséquent, utilisez upper_bound pour trouver le numéro de chaque paire de deux éléments qui satisfait cela. Cependant, il faut un temps linéaire pour connaître l'indice si vous utilisez la fonction de distance, alors ** implémentez votre propre dichotomie et renvoyez l'index **. En mettant en œuvre la dichotomie, j'ai fait référence à mon cet article.
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 int 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 4000 //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
//MLE
signed main(){
//Code pour accélérer la saisie
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll t;cin>>t;
REP(_,t){
ll n;cin>>n;
vector<ll> a(n);
REP(i,n)cin>>a[i];
//Géré par chaque valeur
map<ll,vector<ll>> m;
REP(i,n){
FOR(j,i+1,n-1){
m[a[i]*MOD+a[j]].PB(i*MOD+j);
}
}
long long ans=0;
FORA(i,m){
//Recherche de bisection
ll m=SIZE(i.S);
REP(j,m-1){
ll l,r;l=j+1;r=m-1;
if(i.S[j]%MOD<ll(i.S[l]/MOD)){
ans+=(m-j-1);
continue;
}
if(i.S[j]%MOD>=ll(i.S[r]/MOD)){
continue;
}
while(l+1<r){
ll k=l+(r-l)/2;
if(ll(i.S[k]/MOD)>i.S[j]%MOD){
r=k;
}else{
l=k;
}
}
ans+=(m-r);
}
}
cout<<ans<<endl;
}
}
Problème E
La récidive peut facilement devenir MLE avec PyPy, pourquoi ... Quoi qu'il en soit ** J'écrirai la récursivité en C ++ **.
Effectuez les deux opérations suivantes.
(1) Une opération qui sélectionne une certaine section et réduit le nombre inclus dans cette section de un (cependant, il y en a au moins une de chaque)
② Sélectionnez un nombre et réglez le nombre sur 0.
Tenez compte du nombre minimum d'opérations lors de l'exécution de ces opérations et du vidage de toutes les colonnes. L'opération de ② peut être facilement obtenue en calculant simplement le nombre d'opérations pour la longueur de la section. Par contre, le fonctionnement de ① est un peu compliqué comme suit.
Pour l'opération (1), il est préférable de sélectionner la section le plus longtemps possible. Je ne le prouverai pas cette fois, mais j'estime que le modèle ** selon lequel vous n'avez qu'à sélectionner le tout lorsque vous sélectionnez une section et effectuez une opération ** apparaît fréquemment (cette fois, vous pouvez réduire le nombre d'opérations en rétrécissant la section. Je pensais que ce n'était pas intuitif, j'ai donc appliqué cette politique. ** Cela devrait être justifié **, mais ...).
De plus, lors de l'exécution de l'opération de ①, effectuez l'opération au minimum de la section, et non ** 1 à la fois **. De plus, il y a un élément qui devient 0 après l'opération, et la section entière ne peut pas être exploitée telle quelle à partir de la condition de fonctionnement de ** ① **, donc ** Trouvez le nombre minimum d'opérations pour chaque section divisé par DFS * *.
Par conséquent, compte tenu de l'implémentation de DFS, c'est comme suit.
(1) Lorsque la longueur de l'intervalle donné $ x $ est 1.
Prend et renvoie le nombre d'éléments inclus dans l'intervalle $ x $ (le nombre d'opérations dans ①) et $ min $ dans 1 (le nombre d'opérations dans ②).
(2) Lorsque la longueur de l'intervalle donné $ x $ est supérieure à 1.
La longueur de l'intervalle est $ l $, le nombre minimum parmi les nombres inclus dans l'intervalle est $ m $, la valeur de retour est $ ret = 0 $ et le vecteur qui remplace les intervalles divisés est $ nex = $ { }ça ira.
Ci-dessous, nous allons regarder $ x [i] $ avec $ i = $ 0 ~ $ l $ -1, mais quand $ x [i]! = M $, nous pouvons le remplacer par nex. De plus, lorsque $ i = l $ -1, l'intervalle est fixe, appelez donc dfs avec nex comme intervalle et ajoutez la valeur de retour à ret. Quand $ x [i] = m $, si $ nex $ n'est pas vide, l'intervalle est fixe, donc appelez dfs avec $ nex $ comme intervalle et ajoutez la valeur de retour à ret. À ce stade, laissez $ nex $ vide pour l'intervalle suivant.
Vous pouvez trouver la solution simplement en effectuant le DFS ci-dessus. De plus, si le DFS n'est pas perfectionné, des problèmes de ce degré seront un problème, alors j'aimerais m'y consacrer.
E.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 int 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 dfs(vector<ll>& x){
ll l=SIZE(x);
//Si 0
if(l==1)return min(1,x[0]);
ll m=*min_element(ALL(x));
ll ret=m;
vector<ll> nex;
REP(i,l){
if(x[i]!=0){
nex.PB(x[i]-m);
if(i==l-1)ret+=dfs(nex);
}else{
if(SIZE(nex)){
ret+=dfs(nex);
nex.clear();
}
}
}
return min(ret,l);
}
signed main(){
ll n;cin>>n;
vector<ll> a(n);REP(i,n)cin>>a[i];
cout<<dfs(a)<<endl;
}
Après problème F
Je vais sauter cette fois
Recommended Posts