Codeforces Round # 673 (Div.2) Examen Bacha (10/22)
Les résultats de cette fois
Impressions de cette époque
J'écris un article sur la folie parce que je n'ai pas pu résoudre le problème D parce qu'il semblait résolu.
[Une addition] Si vous regardez de près, vous avez manqué les conditions évidentes. J'ai trop collé à la solution ... Ma tête est trop raide ...
Problème A
Sélectionnez $ i, j $ et ajoutez $ a \ _i $ à $ a \ _j $, de sorte que le nombre maximum d'opérations est de sélectionner le minimum $ a \ _i $ et d'effectuer l'opération **. Par conséquent, considérez le nombre maximum d'opérations lorsque vous opérez sur n'importe quel $ j $ sous $ i \ neq j $. Puisqu'il ne dépasse pas $ k $, $ [\ frac {k-a \ _ j} {a \ _ i}] $ est le nombre d'opérations en attente pour chaque $ j $.
A.py
for _ in range(int(input())):
n,k=map(int,input().split())
a=list(map(int,input().split()))
m=min(a)
l=a.index(m)
ans=0
for i in range(n):
if i!=l:
ans+=(k-a[i])//m
print(ans)
Problème B
$ f (b) = (nombre total de paires de $ i \ <j $ tel que b \ _i + b \ _j $ = $ T $), et $ f ($ f de $ c, d $ divisé par $ a $) Envisagez de minimiser c) + f (d) $. À ce stade, je pensais que si vous mettez ** $ x $ dans un tableau différent de $ T-x $, ** les deux peuvent être mis à 0.
S'il s'agit de $ x \ neq Tx $, il tiendra toujours, mais s'il y a trois $ x $ ou plus tels que ** $ x = Tx \ leftrightarrow x = \ frac {T} {2} $ ** $ X = \ frac {T} {2} $ les éléments qui ne peuvent pas être mis à 0 sont $ k $, et $ c et d $ sont $ \ frac {k} {2}, k- \ frac, respectivement. $ f (c) + f (d) $ est le minimum lors du tri de {k} {2} $ pièces à la fois.
Par conséquent, les cas suivants sont classés.
(1) Quand $ T $ est impair Mettez les éléments sous $ [\ frac {T} {2}] $ dans $ c $ et les éléments plus grands que $ [\ frac {T} {2}] $ dans $ d $.
(2) Quand $ T $ est pair ** $ [] avec des éléments inférieurs à $ [\ frac {T} {2}] $ en $ c $ et des éléments supérieurs à $ [\ frac {T} {2}] $ en $ d $ indexez l'élément de frac {T} {2}] $ une fois dans $ cand $ **. Puisque la taille de $ cand $ est $ k $, nous allouerons respectivement $ \ frac {k} {2} et k- \ frac {k} {2} $ à $ c et d $.
B.py
for _ in range(int(input())):
n,t=map(int,input().split())
a=list(map(int,input().split()))
ans=[-1]*n
cand=[]
for i in range(n):
if t%2==0:
if a[i]<t//2:
ans[i]=0
elif a[i]>t//2:
ans[i]=1
else:
cand.append(i)
else:
if a[i]<=t//2:
ans[i]=0
else:
ans[i]=1
l=len(cand)
for i in range(l):
if i<l//2:
ans[cand[i]]=0
else:
ans[cand[i]]=1
print(" ".join(map(str,ans)))
Problème C
C'était un peu fastidieux à mettre en œuvre, mais c'est juste implémenté. Je pense que la politique est plus facile à établir que B.
Trouvez le plus petit élément de toute sous-colonne contiguë de $ k $ de longueur avec tout $ k $. Tout d'abord, il va de soi que ** $ k $ diminue de façon monotone au fur et à mesure de sa croissance. À ce stade, en faisant attention au moment où chaque valeur sort (** chute du client principal! **), ** la plus petite longueur de la sous-chaîne continue de la longueur $ k $ qui satisfait la condition d'une certaine valeur. J'ai pensé que je devrais demander $ k $ **.
Par conséquent, il existe un ensemble d'index $ x \ _1, x \ _1,…, x \ _l $ (indexés à 0 par ordre croissant) avec une certaine valeur de $ x $, puis $ x \ _ 0 = -1, x \ _ { Quand l + 1} = n $, $ x \ _ {i + 1} -x \ _i \ leqq mi $ devrait être valable pour tout $ 0 \ leqq i \ leqq \ {l} $. Par conséquent, $ mi = max (x \ _ {i + 1} -x \ _ i) $ est la solution. (Je pense qu'il est facile de voir les conditions pour établir ** dessiner un diagramme **.)
Par conséquent, puisque la longueur minimale du sujet peut être obtenue à partir de chaque valeur ($ O (n) $), nous envisagerons de trouver l'élément minimum qui sera la réponse. En d'autres termes, l'implémentation ressemble à ceci:
$ values $ = (un tableau de <valeurs, longueur minimale de sous-chaînes contiguës> paires stockées dans l'ordre croissant des valeurs) $ now $ = (longueur la plus longue sans élément minimum fixe) $ ans [i] $ = (le plus petit élément de toute sous-colonne contiguë de longueur $ i + 1 $)
** Vous pouvez décider dans l'ordre à partir du plus petit élément **, alors envisagez de regarder le $ i $ e élément de $ values $ dans l'ordre croissant de $ i $. À ce stade, lorsque $ values [i] .S $ est inférieur à $ now $, $ now $ à $ values [i] .S $ doit être $ values [i] .F $. Ensuite, $ now $ est mis à jour en $ values [i] .S-1 $. De plus, si $ values [i] .S $ est plus grand que $ now $, vous pouvez regarder l'élément suivant de $ values $ sans effectuer le processus de mise à jour. De plus, s'il existe une sous-colonne de longueur $ k $ pour laquelle le plus petit élément ne peut pas être déterminé, $ ans [k-1] $ doit être mis à -1, donc $ ans $ est initialement initialisé avec -1. Je vais le laisser.
C.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
//S'il n'y a pas de D, la variable de boucle est incrémentée de 1, et s'il y a un D, la variable de boucle est décrémentée 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
signed main(){
//Spécification de sortie du nombre de chiffres fractionnaires
//cout<<fixed<<setprecision(10);
//Code pour accélérer la saisie
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll t;cin>>t;
REP(_,t){
map<ll,vector<ll>> m;
ll n;cin>>n;
REP(i,n){
ll a;cin>>a;
m[a].PB(i);
}
vector<pair<ll,ll>> values;
FORA(i,m){
ll s=SIZE(i.S);
ll mi=-1;
REP(j,s){
if(j==0){
mi=max(mi,i.S[j]+1);
}
if(j==s-1){
mi=max(mi,n-i.S[j]);
}
if(j!=s-1){
mi=max(mi,i.S[j+1]-i.S[j]);
}
}
values.PB(MP(i.F,mi));
}
vector<ll> ans(n,-1);
ll sv=SIZE(values);
#if 0
REP(i,sv){
if(i==sv-1)cout<<values[i].F<<" "<<values[i].S<<"\n";
else cout<<values[i].F<<" "<<values[i].S<<endl;
}
cout<<endl;
#endif
ll now=n;
REP(i,sv){
while(values[i].S<=now){
ans[now-1]=values[i].F;
now--;
}
}
REP(i,n){
if(i==n-1)cout<<ans[i]<<"\n";
else cout<<ans[i]<<" ";
}
}
}
Problème D
Vous pouvez l'utiliser librement pour moins de 3n $ fois, alors considérez ** quand cela vous convient **. La première chose à noter est que vous pouvez ajuster la valeur en définissant ** $ i = 1 $ **. De plus, je pensais que cela ne pouvait pas être réalisé lorsque ** $ \ sum_ {i = 1} ^ {n} {a \ _i} $ était un multiple de $ n $ **, et cela pourrait être réalisé dans d'autres cas.
Ici, lorsque $ i = 1 $ est sélectionné, $ a \ _1 $ change dans le sens décroissant, donc je pense qu'il serait préférable de collecter autant d'éléments que possible dans ** $ i = 1 $ puis de les trier **. (Je n'ai pas pu terminer la discussion d'ici).
De plus, lors du déplacement d'un élément de $ a \ _i $ vers $ a \ _1 $, $ a \ _i $ sera laissé par $ a \ _i \ mod \ i $. Ici, ** Pour déplacer ce surplus vers $ a \ _1 $ ** Une fois que vous déplacez $ i-a \ _i \ mod \ i $ de $ a \ _1 $ à $ a \ _i $ Vous pouvez obtenir $ a \ _i = 0 $ en passant à nouveau de $ a \ _i $ à $ a \ _1 $. À ce stade, $ a \ _1 \ geqq i-1 \ geqq i-a \ _i \ mod \ i $ doit être satisfait, mais dans l'ordre croissant de ** $ i $, $ a \ _i $ à $ a \ _1 $ En supposant que l'élément est déplacé vers **, cette condition est satisfaite à partir de $ a \ 1 = \ sum {j = 1} ^ {i-1} a \ _i \ geqq i-1 $.
Par conséquent, ce qui précède est effectué dans l'ordre croissant de $ i $ pour faire $ a \ 1 = \ sum {i = 1} ^ {n} {a \ _i} $ (maximum $ 2 (n-1) $ fois) puis tout À propos de $ i $ Déplacer les éléments de $ a \ _1 $ vers $ a \ i $ de $ b (= \ frac {\ sum {i = 1} ^ {n} {a \ _ i}} {n}) $ En louant (jusqu'à $ n-1 $ fois), tous les éléments peuvent être égalisés à $ b $ jusqu'à 3 $ (n-1) $ fois au total.
D.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
ans=[]
if sum(a)%n!=0:
print(-1)
continue
b=sum(a)//n
for i in range(1,n):
if a[i]%(i+1)==0:
ans.append([i+1,1,a[i]//(i+1)])
a[0]+=a[i]
a[i]=0
else:
x=i+1-a[i]%(i+1)
ans.append([1,i+1,x])
a[0]-=x
a[i]+=x
ans.append([i+1,1,a[i]//(i+1)])
a[0]+=a[i]
a[i]=0
for i in range(1,n):
ans.append([1,i+1,b])
l=len(ans)
print(l)
for i in range(l):
print(" ".join(map(str,ans[i])))
Après le problème E
Je vais sauter cette fois.
Recommended Posts