[PYTHON] Codeforces Runde # 673 (Div. 2) Bacha Review (10/22)
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Ich schreibe einen Artikel über Wahnsinn, weil ich das D-Problem nicht lösen konnte, weil es gelöst zu sein schien.
[Zusatz] Wenn Sie genau hinschauen, haben Sie die offensichtlichen Bedingungen verpasst. Ich habe mich zu sehr an die Lösung gehalten ... Mein Kopf ist zu steif ...
Problem A
Wählen Sie $ i, j $ und fügen Sie $ a \ _i $ zu $ a \ _j $ hinzu. Die maximale Anzahl von Operationen ** besteht darin, die minimale Anzahl von $ a \ _i $ auszuwählen und die Operation auszuführen. Berücksichtigen Sie daher die maximale Anzahl von Operationen, wenn Sie mit $ j $ unter $ i \ neq j $ arbeiten. Da es $ k $ nicht überschreitet, ist $ [\ frac {k-a \ _ j} {a \ _ i}] $ die ausstehende Anzahl von Operationen für jedes $ 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)
B-Problem
$ f (b) = (Gesamtzahl der Paare von $ i \ <j $, so dass b \ _i + b \ _j $ = $ T $) und $ f ($ f von $ c, d $ geteilt durch $ a $) Erwägen Sie, c) + f (d) $ zu minimieren. Zu diesem Zeitpunkt dachte ich, wenn Sie ** $ x $ in ein anderes Array als $ T-x $ einfügen, ** können beide auf 0 gesetzt werden.
Wenn es $ x \ neq Tx $ ist, gilt es immer, aber wenn es drei oder mehr $ x $ gibt, wie z. B. ** $ x = Tx \ leftrightarrow x = \ frac {T} {2} $ ** $ X = \ frac {T} {2} $ Elemente, die nicht auf 0 gesetzt werden können, sind $ k $, und $ c und d $ sind $ \ frac {k} {2} bzw. k- \ frac. $ f (c) + f (d) $ ist das Minimum, wenn {k} {2} $ Teile gleichzeitig sortiert werden.
Daher werden die folgenden Fälle klassifiziert.
(1) Wenn $ T $ ungerade ist Setzen Sie Elemente unter $ [\ frac {T} {2}] $ in $ c $ und Elemente, die größer als $ [\ frac {T} {2}] $ in $ d $ sind.
(2) Wenn $ T $ gerade ist ** $ [] mit Elementen kleiner als $ [\ frac {T} {2}] $ in $ c $ und Elementen größer als $ [\ frac {T} {2}] $ in $ d $ indiziere das Element von frac {T} {2}] $ einmal in $ cand $ **. Da die Größe von $ cand $ $ k $ ist, weisen wir $ c bzw. d $ $ \ frac {k} {2} und k- \ frac {k} {2} $ zu.
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)))
C-Problem
Die Implementierung war etwas mühsam, aber nur implementiert. Ich denke, die Richtlinie ist einfacher festzulegen als B.
Suchen Sie das kleinste Element in einer zusammenhängenden Unterspalte mit einer Länge von $ k $ mit einem beliebigen $ k $. Zunächst ist es selbstverständlich, dass ** $ k $ mit zunehmendem Wachstum monoton abnimmt. Achten Sie zu diesem Zeitpunkt auf den Zeitpunkt, zu dem jeder Wert herauskommt (** Hauptkundensturz! **), ** die kleinste Länge des fortlaufenden Teilstrings der Länge $ k $, die die Bedingung eines bestimmten Werts erfüllt. Ich dachte, ich sollte nach $ k $ ** fragen.
Daher gibt es eine Reihe von Indizes $ x \ _1, x \ _1,…, x \ _l $ (0 in aufsteigender Reihenfolge indiziert) mit einem bestimmten Wert von $ x $ und dann $ x \ _ 0 = -1, x \ _ { Wenn l + 1} = n $, sollte $ x \ _ {i + 1} -x \ _i \ leqq mi $ für $ 0 \ leqq i \ leqq \ {l} $ gelten. Daher ist $ mi = max (x \ _ {i + 1} -x \ _ i) $ die Lösung. (Ich denke, es ist leicht, die Bedingungen für das Erstellen eines Diagramms zu erkennen.)
Da die Mindestlänge des Subjekts aus jedem Wert ($ O (n) $) erhalten werden kann, werden wir daher in Betracht ziehen, das Mindestelement zu finden, das die Antwort sein wird. Mit anderen Worten, die Implementierung sieht folgendermaßen aus:
$ values $ = (ein Array von <Werten, Mindestlänge zusammenhängender Teilzeichenfolgen> -Paaren, die in aufsteigender Reihenfolge der Werte gespeichert sind) $ now $ = (längste Länge ohne festes Mindestelement) $ ans [i] $ = (das kleinste Element in einer zusammenhängenden Unterspalte der Länge $ i + 1 $)
** Sie können in der Reihenfolge des kleinsten Elements entscheiden **. Betrachten Sie also das $ i $ -te Element der $ -Werte $ in aufsteigender Reihenfolge von $ i $. Zu diesem Zeitpunkt, wenn $ values [i] .S $ kleiner als $ now $ ist, sollten $ now $ bis $ values [i] .S $ $ values [i] .F $ sein. Dann wird $ now $ auf $ values [i] .S-1 $ aktualisiert. Wenn $ values [i] .S $ größer als $ now $ ist, können Sie das nächste Element von $ values $ anzeigen, ohne den Aktualisierungsvorgang auszuführen. Wenn es eine Unterspalte der Länge $ k $ gibt, für die das kleinste Element nicht bestimmt werden kann, muss $ ans [k-1] $ auf -1 gesetzt werden, sodass $ ans $ anfänglich mit -1 initialisiert wird. Ich werde es verlassen.
C.cc
//Debug-Optionen:-fsanitize=undefined,address
//Compileroptimierung
#pragma GCC optimize("Ofast")
//Einschließen usw.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//Makro
//für Schleife
//Das Argument ist(Variablen in der Schleife,Bewegungsumfang)Oder(Variablen in der Schleife,Erste Nummer,Anzahl der Enden)、のどちらOder
//Schleifenvariablen ohne D werden um 1 erhöht, und Schleifenvariablen mit D werden um 1 dekrementiert.
//FORA ist ein Bereich für Aussagen(Wenn es schwer zu bedienen ist, löschen Sie es)
#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 ist ein Container wie ein Vektor
#define ALL(x) x.begin(),x.end()
#define SIZE(x) ll(x.size())
//Konstante
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Gemeinsames Recht
#define MAXR 100000 //10^5:Maximale Reichweite des Arrays
//Abkürzung
#define PB push_back //Einfügen
#define MP make_pair //Paarkonstruktor
#define F first //Das erste Element des Paares
#define S second //Das zweite Element des Paares
signed main(){
//Ausgabespezifikation der Anzahl der Bruchstellen
//cout<<fixed<<setprecision(10);
//Code zur Beschleunigung der Eingabe
//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]<<" ";
}
}
}
D Problem
Sie können es für weniger als $ 3n $ mal frei bedienen, also überlegen Sie **, wann es Ihnen passt **. Das erste, was Sie bemerken müssen, ist, dass Sie den Wert anpassen können, indem Sie ** $ i = 1 $ ** setzen. Außerdem dachte ich, dass es nicht erreicht werden könnte, wenn ** $ \ sum_ {i = 1} ^ {n} {a \ _i} $ ein Vielfaches von $ n $ ** ist, und es könnte in anderen Fällen erreicht werden.
Wenn hier $ i = 1 $ ausgewählt ist, ändert sich $ a \ _1 $ in abnehmender Richtung. Ich denke, es wäre besser, so viele Elemente wie möglich in ** $ i = 1 $ zu sammeln und sie dann zu sortieren **. (Ich konnte die Diskussion von hier aus nicht beenden).
Wenn Sie ein Element von $ a \ _i $ nach $ a \ _1 $ verschieben, bleibt $ a \ _i $ von $ a \ _i \ mod \ i $ übrig. Hier ** Um diesen Überschuss nach $ a \ _1 $ zu verschieben ** Sobald Sie $ i-a \ _i \ mod \ i $ von $ a \ _1 $ nach $ a \ _i $ verschoben haben Sie können $ a \ _i = 0 $ erreichen, indem Sie erneut von $ a \ _i $ zu $ a \ _1 $ wechseln. Zu diesem Zeitpunkt muss $ a \ _1 \ geqq i-1 \ geqq i-a \ _i \ mod \ i $ erfüllt sein, jedoch in aufsteigender Reihenfolge von ** $ i $, $ a \ _i $ bis $ a \ _1 $ Unter der Annahme, dass das Element nach ** verschoben wird, ist diese Bedingung von $ a \ 1 = \ sum {j = 1} ^ {i-1} a \ _i \ geqq i-1 $ erfüllt.
Daher wird das Obige in aufsteigender Reihenfolge von $ i $ ausgeführt, um $ a \ 1 = \ sum {i = 1} ^ {n} {a \ _i} $ (maximal $ 2 (n-1) $ mal) und dann beliebig zu machen Über $ i $ Verschieben Sie Elemente von $ a \ _1 $ nach $ a \ i $ um $ b (= \ frac {\ sum {i = 1} ^ {n} {a \ _ i}} {n}) $ Durch Vermieten (bis zu $ n-1 $ mal) können alle Elemente zu $ b $ bis zu $ 3 (n-1) $ mal ausgeglichen werden.
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])))
Nach dem E-Problem
Ich werde diesmal überspringen.
Recommended Posts