[PYTHON] Codeforces Round # 597 (Div. 2) Bacha Review (27.10.)
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Ich konnte D überhaupt nicht lösen. Es scheint ein typisches Problem zu sein, daher möchte ich darüber nachdenken und es beim nächsten Mal nutzen.
Problem A
Sie müssen lediglich feststellen, dass $ a und b $ elementar zueinander sind. ** Alles was Sie tun müssen, ist sich an den chinesischen Restsatz zu erinnern **.
A.py
from math import gcd
for _ in range(int(input())):
a,b=map(int,input().split())
if gcd(a,b)==1:
print("Finite")
else:
print("Infinite")
B-Problem
Wenn die folgenden Variablen $ r, p, s $ 0 oder mehr sind, füllen wir zuerst nur die Züge aus, die den Gegner schlagen können **. Wenn Sie beim Ausfüllen der Gewinnzüge mit mehr als der Hälfte gewinnen können, können Sie nach entsprechender Entscheidung über die verbleibenden Züge eine Ausgabe durchführen. Selbst wenn Sie nicht mehr als die Hälfte gewinnen können, wird NEIN ausgegeben, da die aktuelle Auswahl die beste Wahl ist.
Sie können es unschuldig implementieren.
B.py
from collections import deque
for _ in range(int(input())):
n=int(input())
r,p,s=map(int,input().split())
t=input()
ans=["" for i in range(n)]
w=0
for i in range(n):
if t[i]=="R":
if p>0:
ans[i]="P"
p-=1
w+=1
elif t[i]=="P":
if s>0:
ans[i]="S"
s-=1
w+=1
else:
if r>0:
ans[i]="R"
r-=1
w+=1
if w<-(-n//2):
print("NO")
else:
ansp=deque()
for i in range(r):
ansp.append("R")
for i in range(p):
ansp.append("P")
for i in range(s):
ansp.append("S")
for i in range(n):
if ans[i]=="":
ans[i]=ansp.popleft()
print("YES")
print("".join(ans))
C-Problem
Ich habe vergessen, durch ** $ 10 ^ 9 + 7 $ ** zu teilen ...
Das Problem beim Zählen solcher Zeichenfolgen ist ** es ist besser, in einer festen Reihenfolge zu zählen **. Zu diesem Zeitpunkt können Sie es auch zu einem DP machen, indem Sie den Status ** gut einstellen. Mit anderen Worten wird der folgende DP eingestellt.
$ dp [i]: = $ (Gesamtzahl der möglichen Zeichenfolgen bis zum $ i $ -ten Zeichen (1-indiziert))
Die Initialisierung sollte $ dp [0] = 1, dp [1] = 1 $ sein, und zu diesem Zeitpunkt wird sie unter Berücksichtigung des Übergangs zum $ i $ -ten Zeichen wie folgt aussehen.
(1) Wenn das $ i $ -te Zeichen kein konvertiertes Zeichen ist
Wenn Sie unter Berücksichtigung der beiden oben genannten Übergänge nicht vergessen, durch $ 10 ^ 9 + 7 $ zu teilen, wird die Antwort herauskommen. Da sich $ w und m $ immer in ** $ uu bzw. nn $ ändern, muss 0 ausgegeben werden, wenn $ w $ oder $ m $ enthalten sind.
C.py
mod=10**9+7
s=input()
n=len(s)
dp=[0]*(n+1)
dp[0]=1
dp[1]=1
for i in range(2,n+1):
dp[i]+=dp[i-1]
dp[i]%=mod
#print(s[i-2:i])
if s[i-2:i]=="uu" or s[i-2:i]=="nn":
dp[i]+=dp[i-2]
dp[i]%=mod
#print(dp)
if ("w" in s)or("m" in s):
print(0)
else:
print(dp[n])
D Problem
Ich denke, es ist unmöglich zu lösen, ohne den Baum mit der minimalen Fläche zu sehen. Ich habe es vor ungefähr 9 Monaten nur einmal gelöst, also habe ich überhaupt nicht daran gedacht. Diesmal wurde es jedoch viel organisiert, daher denke ich, dass es gelöst sein wird, wenn es das nächste Mal herauskommt.
** Um die Kosten so niedrig wie möglich zu halten ** Wir werden die Gebiete zwischen Städten verbinden oder ein Kraftwerk bauen. Derzeit kann dies als Problem des minimalen Gesamtflächenbaums ** angesehen werden, da damit die Kosten beim Verbinden der Kanten zwischen Städten minimiert werden sollen. Auch in Bezug auf die Kosten für den Bau eines Kraftwerks kann durch die Einführung eines neuen Scheitelpunkts (** Super-Scheitelpunkt **) und die Berücksichtigung der gewichteten Seite zwischen dem ursprünglichen Scheitelpunkt das Problem der Lösung des minimalen Gesamtflächenbaums reduziert werden. Ich kann.
Mit anderen Worten, ** Sie können die Oberseite des Kraftwerks erstellen und die Kosten für die $ i $ -te Stadt als $ c \ _i $ ** festlegen. Auf diese Weise kann die Lösung einfach gefunden werden, indem der minimale globale Baum an den Eckpunkten von $ n + 1 $ berücksichtigt wird. Es werden auch Informationen über die Stadt ausgegeben, in der sich das Kraftwerk befindet, und über das Gebiet zwischen den verbundenen Städten. Dies kann jedoch leicht implementiert werden, indem der Fall beim Hinzufügen von Kanten mithilfe der Clascal-Methode aufgeteilt wird.
Die obige Diskussion und Implementierung ist gut, aber ich möchte auch erwähnen, dass ich ** Tupel zum ersten Mal ** verwendet habe, weil ich mit der Clascal-Methode mehrere verschiedene Arten von Werten zurückgeben wollte. Es ist sehr komfortabel zu verwenden, daher werde ich es weiterhin verwenden (Dokument ist hier).
(✳︎)… Für den Mindestflächenbaum habe ich die Bibliothek in [diesem Artikel] veröffentlicht (https://qiita.com/DaikiSuyama/items/bac256aef114b7ade3d6).
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
//Unten repräsentieren die Primzahl und der Baum dasselbe.
class UnionFind{
public:
vector<ll> parent; //parent[i]Ist der Elternteil von i
vector<ll> siz; //Ein Array, das die Größe der Primzahl darstellt(Initialisieren Sie mit 1)
map<ll,vector<ll>> group; //Nach Set verwalten(key:Repräsentant der Menge, Wert:Ein Array von Elementen der Menge)
ll n; //Elementanzahl
//Konstrukteur
UnionFind(ll n_):n(n_),parent(n_),siz(n_,1){
//Initialisieren, da die Wurzel aller Elemente selbst ist
for(ll i=0;i<n;i++){parent[i]=i;}
}
//Holen Sie sich die Wurzel des Baums, zu dem Daten x gehören(Führen Sie auch eine Routenkomprimierung durch)
ll root(ll x){
if(parent[x]==x) return x;
return parent[x]=root(parent[x]);//Da der Wert des Zuweisungsausdrucks der Wert der zugewiesenen Variablen ist, kann die Route komprimiert werden.
}
//X- und y-Bäume zusammenführen
void unite(ll x,ll y){
ll rx=root(x);//x root
ll ry=root(y);//Wurzel von y
if(rx==ry) return;//Wenn im selben Baum
//Kleine Menge zu großer Menge zusammenführen(Zusammengeführt von ry zu rx)
if(siz[rx]<siz[ry]) swap(rx,ry);
siz[rx]+=siz[ry];
parent[ry]=rx;//Wenn sich x und y nicht im selben Baum befinden, hängen Sie y root ry an x root rx an
}
//Bestimmen Sie, ob der Baum, zu dem x und y gehören, identisch ist
bool same(ll x,ll y){
ll rx=root(x);
ll ry=root(y);
return rx==ry;
}
//Ermitteln Sie die Größe der Primzahl von x
ll size(ll x){
return siz[root(x)];
}
//Gruppieren Sie jeden Primsatz
void grouping(){
//Führen Sie zuerst die Routenkomprimierung durch
REP(i,n)root(i);
//Mit Karte verwalten(Standard-Build verwenden)
REP(i,n)group[parent[i]].PB(i);
}
//Löschen Sie das Prim-Set-System und initialisieren Sie es
void clear(){
REP(i,n){parent[i]=i;}
siz=vector<ll>(n,1);
group.clear();
}
};
//Seitenstruktur
struct Edge{
ll u,v,cost;
//Legen Sie const auf den Rücken!
bool operator<(const Edge& e) const {return this->cost<e.cost;}
};
//Clascal-Methode
//ret:=Summe der Gewichte des minimalen Gesamtflächenbaums
//n:=Gesamtzahl der Eckpunkte
//Berechnungsbetrag:=O(|E|log|V|)
tuple<ll,vector<ll>,vector<pair<ll,ll>>> Kruskal(vector<Edge> &edges,ll n){
vector<ll> f1;vector<pair<ll,ll>> f2;
sort(ALL(edges));//Aufsteigende Reihenfolge der Seitengewichte
UnionFind uf=UnionFind(n);
ll ret=0;
FORA(e,edges){
//Müssen Sie diese Seite hinzufügen?(Kraftwerk oder Seite)
if (!uf.same(e.u,e.v)){
uf.unite(e.u,e.v);
ret+=e.cost;
if(e.v==n-1){
f1.PB(e.u+1);
}else{
f2.PB(MP(e.u+1,e.v+1));
}
}
}
return {ret,f1,f2};
}
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 n;cin>>n;
vector<pair<ll,ll>> xy(n);REP(i,n)cin>>xy[i].F>>xy[i].S;
vector<ll> c(n);REP(i,n)cin>>c[i];
vector<ll> k(n);REP(i,n)cin>>k[i];
vector<Edge> edges;
REP(i,n){
FOR(j,i+1,n-1){
edges.PB({i,j,(abs(xy[i].F-xy[j].F)+abs(xy[i].S-xy[j].S))*(k[i]+k[j])});
}
}
REP(i,n)edges.PB({i,n,c[i]});
tuple<ll,vector<ll>,vector<pair<ll,ll>>> t=Kruskal(edges,n+1);
cout<<get<0>(t)<<endl;
cout<<SIZE(get<1>(t))<<endl;
REP(i,SIZE(get<1>(t))){
if(i==SIZE(get<1>(t))-1)cout<<get<1>(t)[i]<<endl;
else cout<<get<1>(t)[i]<<" ";
}
cout<<SIZE(get<2>(t))<<endl;
REP(i,SIZE(get<2>(t))){
cout<<get<2>(t)[i].F<<" "<<get<2>(t)[i].S<<endl;
}
}
E Problem
Ich werde diesmal überspringen.
F Problem
Betrachten Sie die Ziffer DP gleichzeitig für $ a und b $, und wenn Sie die $ i $ -Ziffer von oben betrachten, ist sie gleich $ l $ (①), größer als $ l $ und kleiner als $ r $ (②). Als ich versuchte, über drei Möglichkeiten der Gleichheit mit $ r $ (③) nachzudenken, wurde die Implementierung ruiniert (da es 27 Arten von Übergängen von $ 3 \ mal 3 \ mal 3 $ gibt).
Die Richtlinie war korrekt, aber außer wenn $ a = b = 0 $ ist, ist es $ a \ neq b $. Wenn Sie also in der Reihenfolge von MSB von $ r $ denken, ist $ a $ ① und ②, $ b $ ist ② Sie können sehen, dass nur ③ erfüllt ist. Daher beträgt der Übergang $ 2 \ mal 2 \ mal 3 $, was auf einen ausreichenden Betrag zum Aufschreiben reduziert werden kann.
Ich werde diesmal nicht auflösen, aber ich hoffe, dass es gelöst wird, wenn ich es das nächste Mal sehe. Wenn Sie darüber nachdenken, müssen Sie sich nur mehr darauf konzentrieren, es während des Wettbewerbs zu lösen. Ich bedauere es also.
Recommended Posts