[PYTHON] Codeforces Round # 665 (Div. 2) Bacha Review (8/23)
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Obwohl ich einen Fehler gemacht habe, konnte ich das C-Problem mit einer angemessenen Geschwindigkeit durchlaufen, aber ich konnte das D-Problem mit ** halb aufgeben ** lösen. Infolgedessen konnte ich es nach dem Wettbewerb bestehen, also bereue ich es. Wie ich im vorherigen Artikel erwähnt habe, denke ich, dass sich die Ergebnisse verbessern werden, da die Probleme, die gelöst werden können, bald stabil werden, also werde ich mein Bestes geben. Ich denke, dass es sich ändern wird, wenn ich ungefähr 100 Fragen löse, also werde ich es für ungefähr einen Monat ertragen ** und versuchen, jeden Tag Bacha zu machen.
Problem A
Ich habe die Problemstellung falsch verstanden, bin aber froh, dass ich mich erholen konnte.
Zunächst wird veranschaulicht, die Positionsbeziehung zwischen ** A und B ** zu verstehen. Es gibt die folgenden zwei Muster.
** Wenn $ n <k $ **, erfordert Muster ②, dass die Koordinaten von $ A $ $ k $ oder mehr betragen, sodass die Anzahl der erforderlichen Schritte mindestens $ k-n $ beträgt. In Muster ① sind die Koordinaten von $ A $ $ k $, sodass die Anzahl der erforderlichen Schritte $ k-n $ beträgt. Daher ist zu diesem Zeitpunkt mindestens $ k-n $ erforderlich.
A.py
for _ in range(int(input())):
n,k=map(int,input().split())
if n==k:
print(0)
elif n>k:
if (n+k)%2==0:
print(0)
else:
print(1)
else:
print(k-n)
B-Problem
Sie sollten über die optimale Kombination in der richtigen Reihenfolge nachdenken. Da es nur drei Arten von $ a \ _i $ gibt, sollten Sie die optimale Kombination für jeden Wert berücksichtigen.
(1) Wenn $ a \ _i = 2 $ ** $ c \ _i $ nimmt einen Maximalwert von 2 an, indem es mit $ b \ _i = 1 $ ** kombiniert wird. Kombiniere so viele wie möglich, aber wenn es einen Überschuss gibt ($ z \ _1> y \ _2 $) **, kann der Rest mit $ b \ _i = 2 $ ** kombiniert werden. Dies liegt daran, dass sich $ a \ _i = 1 $ in Kombination mit $ b \ _i = 2 $ negativ auf den Gesamtwert auswirkt. Wenn es mehr Überschuss gibt ($ z \ _1> z \ _2 $), können Sie den Überschuss vom verbleibenden $ x \ _2 $ abziehen.
(2) Wenn $ a \ _i = 1 $ Da $ c \ _i $ nicht positiv ist, sollte es ** mit $ b \ _i \ neq 2 $ gepaart werden, damit es nicht negativ ist **. Mit anderen Worten, wenn es mit $ x \ _2 + y \ _2 $ gepaart werden kann, außer der Kombination in (1), ist der Änderungsbetrag 0. Wenn es einen Überschuss gibt ($ y \ _1> x \ _2 + y \ _2 $), selbst wenn er mit diesen gepaart ist, ist es ausreichend, $ \ mal 2 $ (die Anzahl der Paare) zu subtrahieren, da dies einen negativen Effekt hat.
(3) Wenn $ a \ _i = 0 $ Das Ergebnis ist 0, wenn es mit einem beliebigen $ b \ _i $ kombiniert wird, sodass der Gesamtwert nicht beeinflusst wird und ignoriert werden kann.
Wenn Sie den obigen Eckfall sorgfältig implementieren, ist dies wie folgt. Achten Sie auch darauf, keinen Fehler in der Reihenfolge der Subtraktion zu machen **.
B.py
for _ in range(int(input())):
x1,y1,z1=map(int,input().split())
x2,y2,z2=map(int,input().split())
ans=0
#Zuerst von z1
if z1<=y2:
ans+=(2*z1)
y2-=z1
z1=0
else:
ans+=(2*y2)
z1-=y2
y2=0
if z1<=z2:
z2-=z1
z1=0
else:
z1-=z2
z2=0
x2-=z1
#Als nächstes kommt y1(x1 spielt keine Rolle, es ist sowieso Null)
if y1<=x2+y2:
print(ans)
else:
print(ans-(y1-x2-y2)*2)
C-Problem
(Meine Gedanken während des Wettbewerbs waren ziemlich angemessen und nahe an einer Lügenlösung. ** Gedanken mit geringer Reproduzierbarkeit und Genauigkeit **, daher werde ich eine verbesserte Überlegung schreiben.)
Überlegen Sie zunächst, ob es möglich ist, Elemente an verschiedenen Positionen ** an die richtige Position im Vergleich zum sortierten Array ** zu ändern. Wenn Sie zu diesem Zeitpunkt auf die Elemente mit unterschiedlichen Positionen achten und einige von ihnen keine Vielfachen von ** $ a \ _ {min} $ ** sind, ist gcd $ a \ _ zwischen diesem Element und anderen Elementen. Es kann niemals {min} $ sein. Wenn es also etwas gibt, das kein Vielfaches von $ a \ _ {min} $ ist, können Sie "NO" ausgeben.
Betrachten Sie als nächstes den Fall, in dem alle Elemente an verschiedenen Positionen Vielfache von $ a \ _ {min} $ sind. Zu diesem Zeitpunkt können alle Elemente an die richtige Position verschoben werden, indem Sie ** $ a \ _ {min} $ ** durchlaufen. Angenommen, $ a \ _ {min} $ befindet sich in $ i $ und Sie möchten $ a \ _j $ nach $ k $ verschieben. Zu diesem Zeitpunkt wählen Sie $ a \ _ {min} $ und $ a \ _ k $ und tauschen Sie. $ A \ _ k (= a \ _ {min}) $ und $ a \ _ j $ aus, um zu tauschen Und gcd kann als $ a \ _ {min} $ verschoben werden. Daher ist es möglich, ein anderes Element an einer beliebigen Position an die richtige Position zu verschieben, indem es über $ a \ _ {min} $ verschoben wird.
C.py
from math import gcd
def gcditer(x):
ret=x[0]
for i in range(1,len(x)):
ret=gcd(ret,x[i])
return ret
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
b=sorted(a)
#Sie sollten das gleiche verwenden
#Sie können es verwenden, wenn es ein Bruchteil ist
m=min(a)
c=[a[i] for i in range(n) if a[i]!=b[i] or a[i]%m==0]
if len(c)==0:
print("YES")
elif gcditer(c)==m:
print("YES")
else:
print("NO")
D Problem
Es ist ein ähnliches Problem, aber ich war es nicht gewohnt, dieses Problem zu beheben **, also habe ich zu viel Zeit verbracht. Als Ergebnis habe ich die richtige Lösung gefunden, aber ** ich hatte nicht genug Zeit, um den Indexfehler zu bemerken **.
Betrachten Sie zunächst $ \ sum_ {i = 1} ^ {n-1} \ sum_ {j = i + 1} ^ {n} f (i, j) $, aber denken Sie ehrlich so ** Für eine schwierige Summe ** ist es besser, ** den Beitrag jedes Elements ** zu berücksichtigen. Mit anderen Worten, Sie sollten überlegen, wie oft jede Seite als einfacher Pfad (offener Pfad) zwischen beliebigen Scheitelpunkten (✳︎) enthalten ist, und den Pfadwert multiplizieren.
Hier ist es am besten anzunehmen, dass ** (✳︎) auf jeder Seite gefunden wird ** und ** um die Anzahl der Seiten zu erhöhen, die häufiger erscheinen **. Da die Anzahl der Einsen, die auf der ** Seite erscheinen, so gering wie möglich sein muss **, können die Fälle wie folgt klassifiziert werden.
① Wenn $ m <n-1 $ Wenn Sie die Seiten in absteigender Reihenfolge der Anzahl der Auftritte anordnen, sollte $ p $ auch in absteigender Reihenfolge angeordnet und kombiniert werden. Zu diesem Zeitpunkt wird 1 kombiniert, da es kein $ p $ gibt, das den weniger häufig auftretenden $ n-1-m $ -Kanten entspricht.
② Wenn $ m \ geqq n-1 $ Wenn die Seiten in absteigender Reihenfolge der Anzahl der Erscheinungen angeordnet sind und $ p $ in absteigender Reihenfolge angeordnet und kombiniert sind, verbleibt nur $ m-n + 1 $ in $ p $, sodass die Seite mit der größten Anzahl von Erscheinungen größer als $ p $ ist. Kombiniere es mit dem Produkt von $ m-n + 2 $. Kombinieren Sie für die verbleibenden Seiten die verbleibenden $ n-2 $ Stücke von $ p $ in absteigender Reihenfolge.
Betrachten Sie auf dieser Grundlage (✳︎). Daher habe ich mich entschlossen, ** auf eine Seite zu achten **, wie in der folgenden Abbildung gezeigt.
Durch Auswahl des Start- und Endpunkts des einfachen Pfads aus jedem der oben genannten ** Kreise ** können Sie einen einfachen Pfad erstellen, der diese Seite enthält. Wenn Sie hier auf den unteren Kreis achten, können Sie auch sehen, dass er ** einen Teilbaum ** darstellt. Mit anderen Worten, es ist nur erforderlich, die Anzahl der Eckpunkte des Teilbaums zu kennen, die von DFS ** berechnet werden können, da sie aus der Richtung der Blätter gezählt werden können. Zusätzlich kann die Anzahl der Eckpunkte im oberen Kreis berechnet werden durch (Gesamtzahl der Eckpunkte) - (Anzahl der Eckpunkte im unteren Kreis). Der untere Kreis ist der Teilbaum, der nicht die Wurzel $ \ leftrightarrow $ enthält. Der Teilbaum, dessen Wurzel der Scheitelpunkt ist, der weit von der Wurzel $ \ leftrightarrow $ entfernt ist. ** Die Anzahl der im Teilbaum enthaltenen Scheitelpunkte aus den beiden Scheitelpunkten Es kann als Teilbaum ** mit der kleineren Zahl umformuliert werden.
Daher finden Sie (1) die Anzahl der Teilbaumwurzeln mit jedem Scheitelpunkt als Wurzel, (2) ermitteln Sie, wie oft jede Seite mit (1) eingeschlossen ist, und (3) sortieren und geben Sie in absteigender Reihenfolge an, wie oft jede Seite eingeschlossen ist. Sortieren Sie die $ p $ in absteigender Reihenfolge, ④ finden Sie den Maximalwert durch Kombinieren von Seiten und Zahlen (denken Sie daran, dass es sich um $ mod \ 10 ^ 9 + 7 $ handelt) und implementieren Sie ihn in der folgenden Reihenfolge. Es wird so sein.
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,m;
vector<vector<ll>> edges;
vector<ll> dpc;
vector<vector<ll>> tree;
vector<ll> p;
vector<bool> check;
//Anzahl der Eckpunkte des Teilbaums
ll dfs(ll i){
//cout<<1<<endl;
ll ret=1;
check[i]=true;
FORA(j,tree[i]){
if(!check[j]){
ret+=dfs(j);
}
}
dpc[i]=ret;
return ret;
}
signed main(){
//Code zur Beschleunigung der Eingabe
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
//Überlauf trotzdem
ll t;cin>>t;
REP(_,t){
cin>>n;
dpc=vector<ll>(n,0);
tree=vector<vector<ll>>(n);
edges=vector<vector<ll>>(n-1);
check=vector<bool>(n,false);
REP(i,n-1){
ll u,v;cin>>u>>v;u--;v--;
tree[u].PB(v);
tree[v].PB(u);
edges[i]={u,v};
}
dfs(0);
vector<ll> dp(n-1,0);
REP(i,n-1){
ll l,r;l=edges[i][0];r=edges[i][1];
dp[i]=min(dpc[l],dpc[r])*(n-min(dpc[l],dpc[r]));
}
//FORA(i,dpc)cout<<i<<" ";
sort(ALL(dp),greater<ll>());
//Berechnungsprozess
cin>>m;
p=vector<ll>(m);
REP(i,m){
cin>>p[i];
}
sort(ALL(p),greater<ll>());
vector<ll> calc(n-1,1);
if(m<n-1){
REP(i,m){
calc[i]=p[i];
}
}else{
//Vielleicht ist diese Seite anders
//Ich werde es später beheben
REP(i,m-n+2){
calc[0]*=p[i];
calc[0]%=MOD;
}
FOR(i,m-n+2,m-1){
calc[i-m+n-1]=p[i];
}
}
ll ans=0;
REP(i,n-1){
ans+=(calc[i]*dp[i]);
ans%=MOD;
}
cout<<ans<<endl;
}
}
Nach dem E-Problem
Ich werde diesmal überspringen
Recommended Posts