[PYTHON] Codeforces Runde # 612 (Div. 2) Bacha Review (10/2)
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Dieses Mal konnte ich das Problem, das ich wegwerfen musste, nicht herausfinden, und ich war überwältigt vom Erscheinen des Implementierungsspiels.
Außerdem konnte ich ** nicht aus der Perspektive debuggen, ob es ein Problem mit der Überlegung oder der Implementierung gibt, daher werde ich es mit dem heutigen Yukicoder verwenden.
Problem A
** Ich habe falsch verstanden, was am Anfang ausgegeben werden soll **.
Ändern Sie die Person neben A zu A zu jedem Zeitpunkt und wiederholen Sie dies, bis es sich nicht mehr ändert. Zu jedem Zeitpunkt wechselt mindestens eine Person zu A, schreiben Sie also ein Programm mit dummem $ O (N ^ 2) $ tun können.
A.py
for _ in range(int(input())):
n=int(input())
s=[i=="A" for i in list(input())]
tim=[s]
ans=0
while True:
t=[s[0]]
for i in range(n-1):
if tim[-1][i]==1:
t.append(True)
else:
t.append(tim[-1][i+1])
#print(s,t)
if tim[-1]==t:
break
ans+=1
tim.append(t)
#print(s,t)
print(ans)
B-Problem
Es war das schwierigste Problem, das ich dieses Mal gelöst habe. Wenn Sie kein effizientes Programm schreiben, wird es um ein konstantes Vielfaches gelöscht. Ich bedauere, dass ich normalerweise nicht so viel Bewusstsein hatte.
(Im Folgenden impliziert die Diskussion die Bedingung, dass ** keine Karte die gleichen Eigenschaften hat **.)
Zunächst wollte ich jedes Feature einzeln durch Rekursion betrachten, aber es ist schwierig, da jedes Feature nicht unabhängig betrachtet werden kann. Ich stecke hier fest, aber wenn ich das Problem ruhig betrachte, habe ich die Grenze erreicht, an der $ O (KN ^ 3) $ einfach sein kann und $ N $ maximal etwa 1500 beträgt, also $ O (N ^ 2) Mir ist aufgefallen, dass ein Programm von ungefähr $ pünktlich sein würde (** Wenn Sie in einer Richtlinie stecken bleiben, ziehen Sie eine einfache Lösung in Betracht! **).
Entscheiden Sie sich daher für zwei Karten. Dann können Sie sehen, dass ** die verbleibenden Karten eindeutig bestimmt sind **. Mit anderen Worten, wenn für ein bestimmtes Merkmal die beiden entschiedenen Karten gleich sind, sind die verbleibenden Karten gleich, und wenn die zwei entschiedenen Karten unterschiedlich sind, ist die verbleibende Karte auch ein anderes Merkmal. Daher sollten Sie ** prüfen, ob die verbleibenden Karten in der angegebenen Karte enthalten sind . Wenn die angegebene Karte in der festgelegten Struktur gespeichert ist, wird $ O (k \ log {n}) $ verwendet, um zu bestimmen, ob sie in $ O (k) $ enthalten ist, um die Karten zu finden, die kombiniert werden können. Wenn Sie es also zusammenstellen, können Sie es mit $ O (k \ log {n}) $ implementieren. Daher beträgt der Gesamtbetrag der Berechnung $ O (n ^ 2k \ log {n}) $, und $ n ^ 2k \ log {n} $ beträgt maximal etwa $ 10 ^ 8 $ ~ $ 10 ^ 9 $. Selbst in C ++ ist es gerade noch genug, also " das Urteil erleichtern **", "weil es drei Zeichen $ S, E, T $ ist, ** es in eine ternäre Zahl umwandeln (einfach zu implementieren, wenn es eine quaternäre Zahl ist) ** , "Wenn Sie nach einem Satz von drei Karten fragen, werden diese dupliziert, aber zu diesem Zeitpunkt werden Sie nach der dreifachen Antwort gefragt, sodass ** keine Notwendigkeit besteht, Duplikate zu beurteilen ** (die Anzahl der Dinge, die die Bedingungen erfüllen) $ \ div 3 $ Wenn Sie "Gute Sache" verwenden, können Sie eine bestimmte Anzahl von Malen beschleunigen und diese mit einer Marge ($ 732ms $) weitergeben.
✳︎… set und map können mit $ O (\ log {n}) $ eingefügt werden, aber ** einige Elemente sind nicht $ O (\ log {n}) $ ** Vorsicht ist geboten. Beispielsweise ist eine Zeichenfolge mit einer Länge von $ l $ um die Länge der Zeichenfolge $ O (l \ log {n}) $ langsamer. Wenn Sie mit einer Zeichenfolge wie dieser arbeiten, müssen Sie daher den Rechenaufwand sorgfältig analysieren.
B.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 Endungen)、のどちらOder
//Wenn es kein D gibt, wird die Schleifenvariable um 1 erhöht, und wenn es ein D gibt, wird die Schleifenvariable 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
ll k;
vector<ll> cards;
//Gibt die i-te Nummer zurück
inline ll quadrant(ll x,ll i){
return ((x>>(2*i))&1)+((x>>(2*i+1))&1)*2;
}
signed main(){
//Code zur Beschleunigung der Eingabe
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n;cin>>n>>k;
//Vektor in Quartär konvertieren!(Echte Binärzahl)
cards=vector<ll>(n);
map<ll,ll> ma;
vector<ll> po(k);
REP(i,k)po[i]=1LL<<(2*i);
REP(j,n){
string s;cin>>s;
ll calc=0;
REP(i,k){
if(s[i]=='S'){
calc+=1*po[i];
}else if(s[i]=='T'){
calc+=2*po[i];
}else{
calc+=3*po[i];
}
}
cards[j]=calc;
ma[cards[j]]=j;
}
//Stoppen Sie die Verwaltung von Kandidaten mit Cand(Teilen Sie einfach durch 3)
//Beschneidung?
ll ans=0;
REP(i,n){
FOR(j,i+1,n-1){
ll ne=0;
REP(l,k){
ll temp=quadrant(cards[i],l)*quadrant(cards[j],l);
if(temp==1 or temp==6){
ne+=po[l];
}else if(temp==3 or temp==4){
ne+=2*po[l];
}else{
ne+=3*po[l];
}
}
if(ma.find(ne)!=ma.end()){
ans++;
}
}
}
cout<<ll(ans/3)<<endl;
}
C-Problem
Obwohl es sich um einen DP handelt, ist die Implementierung schwer geworden. Das ist schlecht ...
Da $ n $ 100 ist, lesen Sie zunächst die Problemstellung mit einem Bewusstsein von ** $ O (n ^ 3) $. Die Komplexität wird auch dadurch bestimmt, ** wie viele benachbarte Zahlen unterschiedliche Ereignisse und Gewinnchancen haben **. Außerdem wird nur 1 ~ $ n $ herauskommen und ** nur die Gewinnchancen müssen bekannt sein **, also $ [\ frac {n} {2}] $ gerade und $ n - [\ frac {n } {2}] Richten Sie einfach $ Odds aus.
Wenn Sie von vorne in der Reihenfolge entscheiden, ist es ** schwierig, gierig zu entscheiden **, aber wenn Sie sich das $ i $ -te Element ansehen, wie viele ** gerade und ungerade werden bis zu diesem Punkt verwendet ** und ** Ich fand es nicht schwierig, die minimale Komplexität zu finden, wenn ich die Gleichmäßigkeit ** des letzten Elements speicherte. Sie können auch leicht erkennen, dass dieser DP $ O (n ^ 3) $ ist. Stellen Sie daher den DP wie folgt ein.
$ dp [i] [j] [k]: = $ (Bestimmen Sie bis zum $ i $ -ten Element, verwenden Sie nur $ j $ gerade und teilen Sie das $ i $ -te Element durch 2, um den Rest von $ k $ zu erhalten Minimale Zeitkomplexität)
In Anbetracht des Übergangs von $ p [i-1] $ zu $ p [i] $ wird es daher wie folgt. Außerdem sollte der Übergang $ min $ anstelle von $ = $ dauern, aber er ist so geschrieben, um nicht redundant zu sein.
(1) Wenn $ p [i]! = 0 $ und $ p [i] $ gerade ist
Wenn $ p [i-1] $ gerade ist, ändert sich die Gleichmäßigkeit nicht, so dass $ dp [i] [j + 1] [0] = dp [i-1] [j] [k] $.
Wenn $ p [i-1] $ ungerade ist, ändert sich die Gleichmäßigkeit, so dass $ dp [i] [j + 1] [0] = dp [i-1] [j] [k] + 1 $.
(2) Wenn $ p [i]! = 0 $ und $ p [i] $ ungerade ist
Wenn $ p [i-1] $ ungerade ist, ändert sich die Gleichmäßigkeit nicht, so dass $ dp [i] [j + 1] [1] = dp [i-1] [j] [k] $.
Wenn $ p [i-1] $ gerade ist, ändert sich die Gleichmäßigkeit, so dass $ dp [i] [j + 1] [1] = dp [i-1] [j] [k] + 1 $.
(3) Wenn $ p [i] = 0 $
Da $ p [i] $ eine beliebige Anzahl von Gewinnchancen und Gewinnchancen haben kann, ist es ausreichend, die Übergänge von (1) und (2) zu kombinieren.
Aus dem Obigen kann der Übergang betrachtet werden, und der zu erhaltende Endwert ist der Minimalwert, wenn ** $ i = n-1, j = n // 2 $ **, also $ min (dp [-1] [ n // 2]) Gib einfach $ aus.
C.py
n=int(input())
p=list(map(int,input().split()))
inf=10**12
dp=[[[inf,inf] for j in range(101)] for i in range(n)]
if p[0]!=0:
if p[0]%2==0:
dp[0][1][0]=0
else:
dp[0][0][1]=0
else:
dp[0][1][0]=0
dp[0][0][1]=0
for i in range(1,n):
for j in range(101):
for k in range(2):
if dp[i-1][j][k]==inf:
continue
if p[i]!=0:
if p[i]%2==0:
if k==0:
dp[i][j+1][0]=min(dp[i-1][j][k],dp[i][j+1][0])
else:
dp[i][j+1][0]=min(dp[i-1][j][k]+1,dp[i][j+1][0])
else:
if k==0:
dp[i][j][1]=min(dp[i-1][j][k]+1,dp[i][j][1])
else:
dp[i][j][1]=min(dp[i-1][j][k],dp[i][j][1])
else:
if k==0:
dp[i][j+1][0]=min(dp[i-1][j][k],dp[i][j+1][0])
else:
dp[i][j+1][0]=min(dp[i-1][j][k]+1,dp[i][j+1][0])
if k==0:
dp[i][j][1]=min(dp[i-1][j][k]+1,dp[i][j][1])
else:
dp[i][j][1]=min(dp[i-1][j][k],dp[i][j][1])
print(min(dp[-1][n//2]))
D Problem
Dieses Mal gab es viele Probleme mit einer relativ starken Implementierung. Ich denke jedoch nicht, dass die Idee selbst so verdreht ist. Ich denke, es wird stark sein, wenn ich das unschuldig schreiben kann, also werde ich mein Bestes geben.
Im Folgenden werden die Eckpunkte des Teilbaums implizit als $ a \ _j $ beschrieben, mit Ausnahme von $ a \ _i $ im Teilbaum, dessen Eckpunkte $ a \ _i $ und $ a \ _i $ sind. Bitte verzeihen Sie mir zur Vereinfachung der Erklärung.
Konfigurieren Sie $ a \ _i $ so, dass nur $ c \ _i $ für einen Scheitelpunkt $ i $ existiert, der kleiner ist als die Zahl $ a \ _i $, die in sich selbst unter seinen Teilbaumelementen geschrieben ist. Überlegen. Hier ist es selbstverständlich, dass ** mit DFS lösen, da wir Informationen zum Teilbaum benötigen **. Wenn für die Blattspitze $ c \ _i = 0 $ ist, sollte $ a \ _i = 1 $ festgelegt werden, und wenn $ c \ _i> 0 $ ist, ist dies nicht möglich, sodass NO ausgegeben werden sollte. .. ** Wenn der Scheitelpunkt $ i $ kein Blatt ist, müssen mehrere Teilbäume mit seinem Kind als Scheitelpunkt ** zusammengeführt werden. Beim Zusammenführen wurde jedoch $ a \ _j $ in einem Array zusammengefasst. Sortieren Sie weiter. Unter dieser Quelle fügen wir $ a \ _i $ in dieses Array ein, aber da es sortiert wurde, fügen wir es als Wert zwischen dem ** $ c \ _i-1 $ -ten Element und dem $ c \ _i $ -ten Element * ein *wird gebraucht. Wenn zwischen dem $ c \ _i-1 $ -ten Element und dem $ c \ _i $ -ten Element ein Unterschied von mehr als 1 besteht, wird er nur zwischen ihnen eingefügt. Wenn sie jedoch gleich sind, werden das $ c \ _i + 1 $ -te und nachfolgende Elemente eingefügt. Sie müssen dem Element +2 hinzufügen, bevor Sie es einfügen. ** Achten Sie auch darauf, die Größenbeziehung von $ a \ _j $ in dem bereits gefundenen Teilbaum nicht zu unterbrechen **.
Mit den obigen Überlegungen ist die grundlegende Politik perfekt, aber ich werde auch auf die Implementierung eingehen. Da es nicht schwierig ist, einen Baum zu erstellen, indem ein gerichteter benachbarter Graph angenommen wird, und die Ausgabe nicht schwierig ist, werden wir nur die Implementierung von DFS betrachten.
Zuerst müssen wir ein Array von $ a \ _j $ -Werten in einem festen Teilbaum an die übergeordneten Eckpunkte zurückgeben. Da die endgültige Ausgabe ** dem Index jedes Scheitelpunkts ** entsprechen muss, wird der Rückgabewert an das Array von (Wert-, Index-) Paaren zurückgegeben.
Bereiten Sie hier $ ret $ als Array vor, in dem die Informationen von beliebigem $ a \ _j $ gespeichert sind. In diesem $ ret $ können Sie die von dfs zurückgegebenen Elemente des Arrays mit den untergeordneten Eckpunkten als Teilbäume einfügen. Sortieren Sie nach dem Einfügen (in aufsteigender Reihenfolge des Werts).
Als nächstes sollten Sie $ a \ _i $ aus $ ret $ bestimmen. Es sollte auch beachtet werden, dass ** möglicherweise überhaupt nicht wahr ist **.
① Wenn $ c \ _i > (Gesamtzahl von a \ _j $) Da $ a \ _i $, das diese Bedingung erfüllt, nicht vorhanden ist, überprüfen Sie es als ungültig. Der Rückgabewert sollte ein leeres Array sein.
② Wenn $ c \ _i \ = (Gesamtzahl von a \ _j $) ** Fügen Sie das größte Element plus +1 ** ein und geben Sie das Array zurück. Wenn $ c \ _i = 1 $ ist, sollte 1 zurückgegeben werden.
③ Wenn $ c \ _i = 0 $ Ich möchte das kleinste Element mit -1 einfügen und zurückgeben, aber ** das kleinste Element ist 1. Wenn Sie also +1 zum Ganzen hinzufügen und 1 ** einfügen, ändert sich die Größenbeziehung nicht. Sie können es einfügen.
④ Zu anderen Zeiten Sie müssen es in der Mitte einfügen. Wie in der Diskussion erwähnt, sollte das Element größer als das $ c \ _i $ -te Element und kleiner als das $ c \ _i + 1 $ -te Element (✳︎) sein. Wenn also ($ c \ _i $ th Element) +1 <($ c \ _i + 1 $ th Element), dann ist $ a \ _i = $ ($ c \ _i $ th Element) +1. Das ist gut. In anderen Fällen fügen Sie +2 zu den Elementen nach $ c \ _i + 1 $ hinzu und fügen dann das Original ($ c \ _i + 1 $ th Element) +1 zu ** $ a \ _j $ hinzu Sie können $ a \ _i $ einfügen, ohne die Größenbeziehung von ** zu unterbrechen.
Wenn Sie das obige Zurückgeben des aktualisierten Ret wiederholen, erhalten Sie $ a \ _i $, das das Ganze ist, das in der aufrufenden Funktion zusammengeführt wurde, und Sie können dies ausgeben.
(✳︎)… $ c \ _i + 1 $ kann gleich sein, aber es ist besser sicherzustellen, dass ** Elemente, die im selben Teilbaum enthalten sind und eine definierte Größenbeziehung haben, nicht gleich sind ** Treten Sie nicht auf den Koffer.
Was den Berechnungsbetrag betrifft, wird die dfs-Funktion bis zu $ n $ mal aufgerufen, und jeder Berechnungsbetrag beträgt $ O (n) $, sodass der Gesamtbetrag $ O (n ^ 2) $ beträgt, was eine ausreichende Marge darstellt.
D.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 Endungen)、のどちらOder
//Wenn es kein D gibt, wird die Schleifenvariable um 1 erhöht, und wenn es ein D gibt, wird die Schleifenvariable 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
vector<vector<ll>> tree;
vector<ll> cost;
bool check;
//Gibt als Index / Wert-Paar zurück(Wert, Index)
//Mach alles anders!(Die Verarbeitung beim Tragen ist mühsam)
//Aus der Mitte+Damit die Beziehung nicht bricht!
vector<pair<ll,ll>> dfs(ll v){
vector<pair<ll,ll>> ret={};
FORA(i,tree[v]){
FORA(j,dfs(i)){
ret.PB(j);
}
}
sort(ALL(ret));
//cout<<cost[v]<<SIZE(ret)<<endl;
if(cost[v]>SIZE(ret)){
check=true;
return {};
}else if(cost[v]==SIZE(ret)){
if(SIZE(ret)==0){
ret.PB(MP(1,v));
return ret;
}else{
ret.PB(MP(ret[SIZE(ret)-1].F+1,v));
return ret;
}
}else if(cost[v]==0){
FOR(i,cost[v],SIZE(ret)-1){
ret[i].F++;
}
ret.PB(MP(1,v));
return ret;
}else{
ll x=ret[cost[v]].F;
if(ret[cost[v]-1].F+1<ret[cost[v]].F){
ret.PB(MP(x-1,v));
return ret;
}else{
FOR(i,cost[v],SIZE(ret)-1){
ret[i].F++;
ret[i].F++;
}
ret.PB(MP(x+1,v));
return ret;
}
}
}
signed main(){
//Code zur Beschleunigung der Eingabe
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
check=false;
ll n;cin>>n;
tree=vector<vector<ll>>(n);
cost=vector<ll>(n);
ll root;
REP(i,n){
ll p,c;cin>>p>>c;p--;
if(p!=-1){
tree[p].PB(i);
}else{
root=i;
}
cost[i]=c;
}
vector<pair<ll,ll>> d=dfs(root);
vector<ll> ans(n);
FORA(i,d){
ans[i.S]=i.F;
}
if(check){
cout<<"NO"<<endl;
return 0;
}
cout<<"YES"<<endl;
REP(i,n){
if(i!=n-1)cout<<ans[i]<<" ";
else cout<<ans[i]<<endl;
}
}
Nach dem E-Problem
Ich werde diesmal überspringen. Ich konnte nicht genug Zeit zum Nachdenken bekommen, weil mein Computer nicht gut funktionierte.
Recommended Posts