[PYTHON] Codeforces Runde # 668 (Div. 2) Bacha Review (9/7)
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Dieses Mal, glaube ich, stand ich Bachacon mit einer guten Konzentration gegenüber. Das D-Problem fragte mich jedoch, was ich nicht hatte, aber ich bedauere es, weil es ** Wissen war, das ich wissen sollte **. Es ist auch ein Problem, das Sie gewusst hätten, wenn Sie während des Bachacon gesucht hätten. Daher kann es manchmal sinnvoll sein, die Suche zu verwenden.
Problem A
Es war ein Knebel. Wenn Sie es nicht bemerken, werden Sie verrückt. ** Es ist gut, als ** $ p \ _1, p \ _2,…, p \ _n $ zu denken, ohne seltsam zu experimentieren.
$ p \ _1 + p \ _2, p \ _2 + p \ _3,…, p \ _ {n-1} + p \ _n $. Wenn Sie es also umkehren, $ p \ _n + p \ _ {n-1 },…, P \ _3 + p \ _2, p \ _2 + p \ _1 $ und die angezeigten Zahlen sind genau gleich.
Daher können Sie die in umgekehrter Reihenfolge ausgeben.
A.py
for _ in range(int(input())):
n=int(input())
p=list(map(int,input().split()))
print(" ".join(map(str,p[::-1])))
B-Problem
Als der Rechenaufwand an seine Grenzen stieß, war ich ungeduldig, ohne zu bestehen, aber es war gut, mich erholen zu können.
Wählen Sie $ i, j $ und ändern Sie es in $ a \ _i-1, a \ _j + 1 $. Zu diesem Zeitpunkt, wenn $ i \ <j $, werden keine Münzen benötigt, wenn $ i > j $, wird eine Münze benötigt, und berücksichtigen Sie die Mindestanzahl von Münzen, die erforderlich sind, um alles zu 0 zu machen. Ich werde.
Wenn Sie im Experiment mit der Stichprobe $ i, j $ auswählen, wobei ** $ a \ _i> 0, a \ _j <0 $, können Sie eine Änderung ** vornehmen, die sich 0 nähert, ohne Münzen zu verwenden. Ich werde. Wenn Sie diese Änderung vornehmen, bleiben -und + auf der rechten Seite schließlich auf der linken Seite, und zu diesem Zeitpunkt bleibt keine andere Wahl, als Operationen mit Münzen durchzuführen. Zum Beispiel werden im ersten Beispiel alle Elemente auf 0 gesetzt, indem eine Operation ausgeführt wird, bei der keine Münzen von "-3 2 -3 4" bis "-3 0 -1 4" verwendet werden und 4 Münzen aus diesem Zustand verwendet werden. Kann sein
Schauen Sie sich für die erste Operation, bei der keine Münzen verwendet werden, die Elemente an, die $ a [i]> 0 $ in der Reihenfolge des kleinsten $ i $ erfüllen, und verwenden Sie $ j (> i) $, das $ a [j] <0 $ erfüllt. Sie können es auf gierige Weise tun, beginnend mit dem kleinsten $ j $ (das Bild ist das $ , weil $ ** weniger Auswahlmöglichkeiten hat **!). Außerdem habe ich versucht, ein kleines $ j $ mit $ j (> i) $ zu verwalten, das $ a [j] <0 $ mit einer Mengenstruktur erfüllt. In diesem Fall dauert das Einfügen, Löschen und Verweisen auf die Menge logarithmische Stunden. Es wird TLE sein.
Hier ist $ j $ der kleinste Index, der $ i <j, a [j] <0 $ erfüllt, und wenn $ i $ um 1 erhöht wird, steigt $ j $ monoton ** an. Sie können also $ j $ als einzelnen Index haben und sich eine Implementierung wie die ** Skalierungsmethode ** vorstellen. Daher kann es mit dem Berechnungsbetrag von $ O (N) $ implementiert werden.
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)
C-Problem
Beachten Sie, dass die Unterspalten ** fortlaufend ** sind. Ich war scharf, ohne es zu merken.
Es ist eine fortlaufende Teilzeichenfolge mit einer Länge von $ k $, und ich möchte den Unterschied ** sehen, also habe ich die folgende Abbildung geschrieben.
Dann bemerkte ich, dass die Elemente mit den Indizes $ 0 $ und $ k $ gleich sind. Wenn dies verallgemeinert ist, sind die Elemente der Indizes $ i $ und $ i + k $ gleich. Wenn also die Reste der Indizes geteilt durch $ k $ gleich sind, sind diese Elemente gleich . Ich werde. Überprüfen Sie daher zunächst, ob die Elemente gleich sind ( 0 und 1 sind nicht gleichzeitig enthalten **), indem Sie jeden Indexrest teilen. Wenn zu diesem Zeitpunkt ungleiche Elemente vorhanden sind, wird NO ausgegeben.
Außerdem ist es eine ** Anforderung **, dass alle Elemente für jeden Restindex gleich sind, und die Anzahl der Nullen und Einsen, die im fortlaufenden Teil der Länge $ k $ als ** ausreichende Bedingung ** erscheinen, muss gleich sein. Muss sein. Suchen Sie daher das Element, wenn der Rest für jedes $ l $ $ l $ beträgt. Beachten Sie auch, dass nicht nur $ 0 $ und $ 1 $, sondern auch **? **, die Anzahl der 0s $ ans0 $, die Anzahl der 1s $ ans1 $ und die Anzahl der? Is $ ex $ ist. Ich werde.
Berücksichtigen Sie die Bedingungen unter diesen Bedingungen ausreichend, aber wenn $ ex = 0 $ ist und $ ans0 = ans1 $, ist die Bedingung erfüllt, sodass JA ausgegeben wird, andernfalls wird NEIN ausgegeben. Als nächstes kann $ ex \ neq 0 $ durch die Anzahl von? Angepasst werden. Also $ ans0 + ex \ geq [\ frac {k} {2}] $ und $ ans1 + ex \ geq [\ frac {k } {2}] Wenn es $ ist, ist die Bedingung erfüllt, also wird JA ausgegeben. Wenn nicht, wird NEIN ausgegeben.
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])
#Wenn es etwas anderes gibt, nein zu diesem Zeitpunkt
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")
D Problem
Im Folgenden wird Alice als A und Bob als B abgekürzt. A sei auch die einmal von $ da $ zurückgelegte Strecke, und die von B zurückgelegte Strecke sei einmal $ db $.
B rennt von A weg. Da A der erste Spieler ist, ** gewinnt A **, wenn Sie B zum ersten Mal erreichen können. Betrachten Sie daher ** die optimale Bewegung für jede **, während A B beim ersten Mal nicht erreichen kann. Betrachten Sie zunächst die optimale Bewegung von B. ** B muss sich nicht bewegen, bis A sich dem Limit nähert **. Wenn sich A dem Grenzwert nähert und sich ein Scheitelpunkt in Richtung von A entfernt befindet, ist es besser, sich dorthin zu bewegen. Wenn es jedoch keinen solchen Scheitelpunkt gibt, muss über A zu einem entfernten Scheitelpunkt bewegt werden. Andererseits besteht die optimale Bewegung von A nicht darin, sich so nahe wie möglich an B zu bewegen, sondern sich ** auf eine Entfernung von $ da $ zu bewegen. Dies liegt daran, dass B leichter entkommen kann, wenn es näher kommt, wenn es A überspannt und entkommt.
Aufgrund der obigen Überlegungen wird angenommen, dass A in $ db \ leqq 2 \ mal da $ gefangen ist und B weiterhin in $ db> 2 \ mal da $ entkommt. ** B kann jedoch möglicherweise nicht so weit entkommen **. Weil $ db $ bis zu $ n-1 $ betragen kann, der Abstand zwischen den Scheitelpunkten im Baum jedoch kleiner als $ n-1 $ sein kann (z. B. Sterngraph). Das heißt, $ db $ muss durch $ min ** ersetzt werden (db, $ der maximale Abstand zwischen zwei Eckpunkten auf dem Baum). Hier wusste ich nicht, wie ich den maximalen Abstand zwischen zwei Eckpunkten auf dem Baum ** im Bachacon finden sollte, aber als ich ihn untersuchte, schien es, dass der ** Baumdurchmesser ** diesem entspricht. Daher sollte $ db = min (db, $ Baumdurchmesser) eingestellt werden.
Der Durchmesser des Baums kann mithilfe des folgenden Algorithmus unter Bezugnahme auf diesen Artikel berechnet werden.
Ich werde es nicht in eine Bibliothek schaffen, weil es einfach ist, BFS (oder DFS) zweimal zu machen, aber ich würde es gerne lösen können, wenn ich es in Zukunft sehe. Auch für den Beweis wurde im vorherigen Artikel ein einfacher geschrieben.
Daher war es aus dem Obigen möglich zu bestimmen, welcher von A und B in jedem Fall gewinnt.
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 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
ll n,a,b,da,db;
vector<vector<ll>> tree;
vector<ll> check;
vector<ll> check2;
signed main(){
//Code zur Beschleunigung der Eingabe
//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;
}
}
}
Nach dem E-Problem
Ich werde diesmal überspringen
Recommended Posts