[PYTHON] Codeforces Round # 660 (Div. 2) Bacha Review (8/4)
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Diesmal habe ich drei Fragen gelöst. Die Implementierung des C-Problems war schwer, aber ich konnte es durch die Organisation der Richtlinie richtig beantworten.
Ich hatte das D-Problem bereits durch die Organisation der Implementierung gelöst und möchte mich dessen weiterhin bewusst sein.
Problem A
$ x $ wird durch die Summe von vier verschiedenen positiven ganzen Zahlen dargestellt (von denen mindestens drei $ fast \ primer $ sind), aber ** das Minimum $ fast \ primer $, um so viel $ x $ wie möglich darzustellen. Ich entschied mich für ** zu suchen. $ fast \ primer $ ist eine Zahl, die durch Multiplikation zweier Primzahlen ausgedrückt werden kann, und $ 6,10,14 $ sind die kleinsten drei $ fast \ primer $. Wenn also $ x $ kleiner als $ 30 (= 6 + 10 + 14) $ ist, können Sie die vier Ganzzahlen des Subjekts nicht konstruieren.
Wenn Sie $ 6,10,14 $ wählen, wenn $ x> 30 $, können Sie $ 6,10,14 $ nicht als andere Zahl auswählen, sondern diese Methode, wenn $ x = 36,40,44 $ Im Fall von können die vier Ganzzahlen des Subjekts nicht konstruiert werden, aber durch Auswahl von $ 15 $ anstelle von $ 14 $ können die vier ganzen Zahlen des Subjekts auch im Fall von $ x = 36,40,44 $ konstruiert werden.
A.py
for i in range(int(input())):
n=int(input())
if n<=30:
print("NO")
elif n==36:
print("YES")
print("6 10 15 5")
elif n==40:
print("YES")
print("6 10 15 9")
elif n==44:
print("YES")
print("6 10 15 13")
else:
print("YES")
print("6 10 14"+f" {n-30}")
B-Problem
Um das Problem bei $ n $ zusammenzufassen, betrachten Sie ein binäres $ k $, in dem jede Ziffer der $ n $ -Ziffernzahl $ x $ in binärer Notation verkettet ist, und das $ k $ Es ist das kleinste $ x $ bei der Maximierung der Zahl $ r $, wobei die unteren $ n $ -Ziffern ignoriert werden. Bei der Konvertierung in die Binärnotation wird diese nicht mit Nullen aufgefüllt.
Zuallererst ist es selbstverständlich, dass $ x $ $ 99… 99 $ ** sein sollte, um ** $ r $ zu maximieren. Zu diesem Zeitpunkt wird jedoch $ x $ zum Maximum. Daher sollten Sie ** die unteren $ n $ -Ziffern von $ k $ so klein wie möglich halten, um sie zu ignorieren **. Da $ 9 $ in Binärform in der $ 4 $ -Ziffer liegt, besteht die einzige Möglichkeit, $ x $ zu reduzieren, während $ r $ maximal bleibt, darin, $ 9 $ durch $ 8 $ zu ersetzen. Daher sollte die Ziffer von $ x $, die der unteren $ n $ -Ziffer des ignorierten $ k $ entspricht, in $ 8 $ geändert werden, und der Wert von $ n % 4 $ gibt an, wie viele Ziffern durch $ 8 $ ersetzt werden können. Ich werde es separat betrachten.
Wenn $ n % 4 = 0 $ ist, wird die untere $ [\ frac {n} {4}] $ -Ziffer von $ x $ in $ 8 $ geändert, und wenn $ n % 4 \ neq 0 $, $ Die untere $ [\ frac {n} {4}] + 1 $ -Ziffer von x $ kann $ 8 $ sein, und der Code sieht folgendermaßen aus:
B.py
for _ in range(int(input())):
n=int(input())
l=n//4 if n%4==0 else n//4+1
ans="9"*(n-l)+"8"*(l)
print(ans)
C-Problem
Betrachten Sie zunächst ** einen verwurzelten Baum mit Wurzeln in der Hauptstadt (oben 1) **. Auf dieser Grundlage wird die Anzahl der Menschen, die sich gut fühlen, und derjenigen, die sich schlecht fühlen, so festgelegt, dass $ h_i, p_i $ auf jedem Höhepunkt gilt, aber es stellt sich heraus, dass es schwierig ist, ** in den dunklen Wolken ** zu entscheiden. Es ist auch schwierig, mit ** wechselnden Stimmungen in der Mitte des Randes ** umzugehen (der Beitrag zu $ h_i $ steigt von +1 auf -1). Folgen Sie daher in einem solchen Fall ** dem Baum aus der Wurzelrichtung oder der Blattrichtung **. ** BFS wird im ersteren Fall häufig verwendet, und DFS ** wird im letzteren Fall häufig verwendet. Außerdem schien es in dieser Ausgabe so, dass ** die Anzahl der Menschen, die sich gut fühlen, und die Anzahl der Menschen, die sich in den Blättern schlecht fühlen, eindeutig bestimmt werden kann **, also entschied ich mich für DFS.
Unter der Annahme, dass der ** $ i $ -te Apex ein Blatt ** ist und die Anzahl der guten und schlechten Personen, die durch diesen Apex gehen, $ c bzw. d $ ist, beträgt die Anzahl der Personen, die durch diesen Apex gehen Da nur diejenigen, die in dieser Stadt leben, $ cd = h \ _i, c + d = p \ _i $ gilt. Wenn dies in einen Ausdruck umgewandelt wird, wird es zu $ c = \ frac {p_i + h_i} {2}, d = \ frac {p_i-h_i} {2} $, und wenn $ c und d $ beide 0 und eine ganze Zahl sind, ist das Subjekt Treffen.
Unter der Annahme, dass der ** $ i $ -te Scheitelpunkt kein Blatt ** ist, sucht ** DFS in der Reihenfolge nach dem Scheitelpunkt, der dem Blatt am nächsten liegt **, sodass jeder Scheitelpunkt im Teilbaum an diesem Scheitelpunkt verwurzelt ist Wir wissen bereits, wie viele Menschen sich gut und schlecht fühlen. Wenn Sie hier ein Paar guter und schlechter Personen zurückgeben, die jeden Scheitelpunkt mit der rekursiven Funktion ** DFS ** durchlaufen, wird er den $ i $ -ten Scheitelpunkt durchlaufen, jedoch den $ i $ -ten Scheitelpunkt. Sie können die Anzahl der guten und schlechten Menschen ermitteln, die nicht zuerst leben, und sie als $ x bzw. y $ festlegen.
Wenn zu diesem Zeitpunkt die Anzahl der guten und schlechten Personen, die den $ i $ -ten Peak durchlaufen, $ c bzw. d $ beträgt, dann ist $ cd = h \ _i, c + d = p \ _i + x + y $ Ist festgelegt. Wenn dies in einen Ausdruck umgewandelt wird, wird es zu $ c = \ frac {p_i + x + y + h_i} {2}, d = \ frac {p_i + x + y-h_i} {2} $. Außerdem sind $ c und d $ sowohl 0 als auch ganze Zahlen, und ** eine Person, die sich einmal krank fühlt, fühlt sich nicht besser **, sodass $ c <x $ zufrieden sein kann. Auf keinen Fall.
Sie können eine Hebelantwort finden, die alle Eckpunkte überprüft, indem Sie DFS ausführen und dabei auf den Fall von Blättern und Nichtblättern achten. Wenn es Scheitelpunkte gibt, die nicht gelten, gibt die rekursive Funktion ein Paar von (-1, -1) zurück.
Diesmal ist es wichtig
・ BFS, wenn Sie dem Baum aus der Stammrichtung folgen möchten → Informationen zur Route von der Wurzel bis zur Spitze erhalten Sie zuerst ・ Wenn Sie dem Baum aus Richtung der Blätter folgen möchten, DFS → Informationen zu den Eckpunkten in dem Teilbaum, der an diesem Eckpunkt verwurzelt ist, können abgerufen werden.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
#define CANT MP(ll(-1),ll(-1))
pair<ll,ll> dfs(vector<ll> &p,vector<ll> &h,vector<bool> &seen,vector<vector<ll>> &graph,ll v) {
seen[v] = true;
bool f=false;
//Ein Paar gut und schlecht
pair<ll,ll> x(0,0);
for (auto ne:graph[v]) {
if(seen[ne])continue;
f=true;
pair<ll,ll> y=dfs(p,h,seen,graph,ne);
if(y==CANT)return CANT;
x.F+=y.F;x.S+=y.S;
}
//cout<< x.F << " " << x.S << " " << v << endl;
if(f){
if(abs(p[v]+x.F+x.S)%2!=abs(h[v])%2){
//cout<<-1<<endl;
return CANT;
}else{
ll c=(p[v]+x.F+x.S+h[v])/2;ll d=(p[v]+x.F+x.S-h[v])/2;
if(c<0 or d<0 or c<x.F){
//cout<<-2<<endl;
return CANT;
}else{
return MP(c,d);
}
}
}else{
if(abs(p[v]%2)!=abs(h[v]%2)){
//cout<<-3<<endl;
return CANT;
}else{
ll c=(p[v]+h[v])/2;ll d=(p[v]-h[v])/2;
if(c<0 or d<0){
//cout<<-4<<endl;
return CANT;
}else{
return MP(c,d);
}
}
}
}
signed main(){
//Code zur Beschleunigung der Eingabe
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll t;cin>>t;
REP(_,t){
ll n,m;cin>>n>>m;
vector<bool> seen(n,false);
vector<vector<ll>> graph(n);
vector<ll> p(n);REP(i,n)cin>>p[i];
vector<ll> h(n);REP(i,n)cin>>h[i];
REP(i,n-1){
ll x,y;cin>>x>>y;
graph[x-1].PB(y-1);
graph[y-1].PB(x-1);
}
pair<ll,ll> z=dfs(p,h,seen,graph,0);
if(z==CANT){
cout<<"NO"<<endl;
}else{
cout<<"YES"<<endl;
}
}
}
D Problem
Weil ich nur noch wenig Zeit hatte, war ich ungeduldig und hatte eine grobe Politik. Ich möchte mir nicht zu viele Sorgen um die verbleibende Zeit machen.
Während des Wettbewerbs dachte ich, ich würde gierig eine große Anzahl auswählen, aber ** wenn die Reihenfolge relevant ist, erwäge ein gerichtetes Diagramm **, um die Aussichten zu verbessern.
In diesem Problem wird bei Auswahl von $ i $ und Ausführen einer Operation $ a [i] $ zu $ a [b [i]] $ sowie zu $ ans $ hinzugefügt, aber zu $ a [i] $ Wenn es negativ ist, können Sie in der Reihenfolge $ b [i] \ rightarrow i $ und nicht in der Reihenfolge $ i \ rightarrow b [i] $ arbeiten. Wenn umgekehrt $ a [i] $ positiv ist, können Sie mit $ i \ rightarrow b [i] $ arbeiten.
Ich habe darüber nachgedacht und gierig versucht, aus einer großen Anzahl von Positiven auszuwählen, aber ** jedes $ a [i] $ ist nicht optimal, da sich der Wert ändern kann **. Umgekehrt können Sie jedoch $ a [i] $ auswählen, dessen Wert sich nicht ändert **. Wenn wir einen gerichteten Graphen mit jeder Zahl als gewichteten Scheitelpunkt betrachten, ändert sich der Wert daher nicht für ** Scheitelpunkte mit 0 Seiten, die von anderen Scheitelpunkten stammen ** (Scheitelpunkte mit 0 Ausgabe, Quellpunkt). Hmm.
Betrachten Sie daher einen gerichteten Graphen unter der Annahme, dass $ b [i] f ein und verbinden Sie sich mit dem $ i $ -ten Scheitelpunkt. Addiere $ a [i] $ zum Gewicht. Wenn $ a [i] <0 $ ist, ** können die Gewichte anderer Eckpunkte nicht erhöht werden **, also fügen Sie einfach ein [i] in s ein. Außerdem wird ** die Reihenfolge der Eckpunkte, zu denen das Urteil gefällt wird, um eins reduziert **, und die mit der Reihenfolge 0 wird als Kandidat für einen neuen Eckpunkt verwendet. Da es sich um einen gerichteten, nicht geschlossenen Schaltkreis handelt, können Sie jeden Scheitelpunkt mit den obigen Angaben überprüfen. Außerdem ist die Summe der aktualisierten Werte von a [i] der Maximalwert von $ ans $, und die Reihenfolge der Operationen ist in aufsteigender Reihenfolge vor "s", da die in "f" eingefügten Eckpunkte das Gewicht erhöhen. Die in s` eingefügten Eckpunkte reduzieren das Gewicht, sodass Sie dies in umgekehrter Reihenfolge tun können.
D.py
from collections import deque
ans=0
n=int(input())
a=list(map(int,input().split()))
b=[i-1 if i!=-1 else -1 for i in list(map(int,input().split()))]
flow=[0]*n
graph=[[] for i in range(n)]
for i in range(n):
if b[i]!=-1:
flow[b[i]]+=1
graph[i].append(b[i])
check=[a[i] for i in range(n)]
ver=deque()
lv=0
for i in range(n):
if flow[i]==0:
ver.append(i)
lv+=1
f,s=[],[]
while lv:
#print(ver)
for i in range(lv):
x=ver.popleft()
lv-=1
if check[x]>=0:
f.append(x)
for j in graph[x]:
flow[j]-=1
check[j]+=check[x]
if flow[j]==0:
ver.append(j)
lv+=1
else:
s.append(x)
for j in graph[x]:
flow[j]-=1
if flow[j]==0:
ver.append(j)
lv+=1
#print(check)
print(sum(check))
print(" ".join(map(lambda x:str(x+1),f+s[::-1])))
Nach dem E-Problem
Ich werde diesmal überspringen
Recommended Posts