[PYTHON] Codeforces Runde # 606 (Div. 3) Bacha Review (10/13)
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Dieses Mal musste ich das Problem bis E lösen, aber ich konnte es nicht lösen, weil ich meine Konzentration verlor. ** Sie sollten in der Lage sein, das E-Problem zu lösen, indem Sie es einzeln umschreiben **, aber ich bin sehr enttäuscht, weil ich es im Rahmen des Wettbewerbs nicht lösen konnte.
Problem A
Da es sich um eine positive Zahl handelt, die dieselbe Zahl wiederholt, sollten Sie berücksichtigen, wie viele Möglichkeiten es in den neun Fällen von 11… 11,22… 22,…, 99… 99 $ gibt. Selbst wenn $ n = 10 ^ 9 $ ist, gibt es hier jeweils nur 9 Möglichkeiten, sodass Sie die unter $ n $ zählen können.
A.py
for _ in range(int(input())):
n=int(input())
ans=0
for i in range(1,10):
cand=[]
while True:
cand.append(str(i))
x=int("".join(cand))
if x<=n:
ans+=1
else:
break
print(ans)
B-Problem
Alle geraden und gleichen Elemente werden durch 2 geteilt. Wenn Sie also nur den Elementtyp ** beibehalten, können Sie die Anzahl der Simulationen ermitteln. Bereiten Sie daher $ a $ als $ set $ -Struktur vor, die die Elemente (gerade) enthält, die manipuliert werden müssen.
Wenn Sie an den Elementen in $ a $ arbeiten, reduziert jede Operation nur die Anzahl der einzelnen Elemente. Wenn Sie also die Operation ** ausführen, die durch 2 geteilt wird, in der Reihenfolge der größten in ** $ a $ enthaltenen Zahl, ist dies die Mindestanzahl von Operationen. Wenn das Ergebnis der Division durch 2 ungerade ist, muss es nicht erneut in $ a $ eingefügt werden. Daher ist die Mindestanzahl von Operationen in dem Betreff die Anzahl von Operationen, bis $ a $ leer wird, nachdem diese Operationen der Reihe nach ausgeführt wurden.
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 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
signed main(){
//Code zur Beschleunigung der Eingabe
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll t;cin>>t;
REP(i,t){
ll n;cin>>n;
set<ll> a;
REP(j,n){
ll x;cin>>x;
if(x%2==0)a.insert(x);
}
ll ans=0;
//cout<<SIZE(a)<<endl;
while(SIZE(a)>0){
ll y=*--a.end();a.erase(y);
y/=2;
if(y%2==0)a.insert(y);
ans++;
//cout<<SIZE(a)<<endl;
}
cout<<ans<<endl;
}
}
C-Problem
Stellen Sie sich eine Zeichenfolge vor, die bis auf wenige Zeichen nicht eins und zwei enthält. Wenn hier ** eins und zwei ohne Überlappung ** existieren, können Sie das mittlere n bzw. w entfernen, sodass die Zeichenfolge nach dem Herausziehen diese eins und zwei nicht enthält. Ich werde. Zu diesem Zeitpunkt sind eins und zwei ** nichts Neues **.
Das Problem ist, wenn sich ** eins und zwei überlappen und zwei werden **. Zu diesem Zeitpunkt wird durch Entfernen von o die Zeichenfolge twone zu twne, und weder eine noch zwei in dieser Zeichenfolge enthaltene Zeichenfolge wird nach dem Entfernen in die Zeichenfolge aufgenommen. Es gibt auch nichts Neues, was eins und zwei nach wie vor tun können.
Außerdem sollten die Anzahl der auszuschließenden Zeichen und der Index der auszuschließenden Zeichen ausgegeben werden. Hier ** weicht der Index vom Ausgangszustand ab, wenn das Zeichen tatsächlich entfernt wird **. Überprüfen Sie ihn daher als zu entfernendes Zeichen, anstatt ihn zu entfernen. Um bei zwei und zwei Eins eine doppelte Zählung zu vermeiden, scannen Sie zuerst die erste und prüfen Sie im Voraus, und zählen Sie dann die erste, die zwei, eins wird. Hat.
C.py
import sys
input=sys.stdin.readline
for _ in range(int(input())):
s=input()
n=len(s)
check=[0]*n
ans=[]
for i in range(n):
if s[i:i+5]=="twone":
ans.append(str(i+3))
for j in range(i,i+5):
check[j]=1
for i in range(n):
if check[i]:
continue
if s[i:i+3]=="one":
ans.append(str(i+2))
if s[i:i+3]=="two":
ans.append(str(i+2))
print(s.count("one")+s.count("two")-s.count("twone"))
print(" ".join(ans))
D Problem
Trotz der Tatsache, dass die Überlegungen und die Implementierung unterschiedlich sind **, war ich ungeduldig, weil es aus irgendeinem Grund eine Stichprobe gab, weil ich an zwei Stellen einen Fehler gemacht habe. Es ist gut, die Fehler danach finden zu können, aber ich möchte solche Fehler reduzieren, damit ich nicht ungeduldig werde.
Einfach ausgedrückt, es geht darum, binäre Zeichenfolgen auszutauschen. Betrachten Sie auch den Fall, in dem die Zeichenfolgen möglicherweise invertiert werden, damit sie nicht übereinstimmen, und die Anzahl der Inversionen so gering wie möglich ist, während die Zeichen gequetscht werden können. Da es hier nicht sinnvoll ist, die Umkehroperation für dieselbe Zeichenfolge mehr als einmal auszuführen, ist zu berücksichtigen, dass die Umkehroperation für jede Zeichenfolge höchstens einmal ausgeführt wird.
Da nur die umgekehrte Operation ausgeführt werden kann, werden die dazwischen liegenden Zeichen als Muster von ** $ 00,01,10,11 $ betrachtet, unabhängig davon, ob sie entfernt werden können **. Hier wirkt sich die Flip-Operation für $ 00,11 $ nicht auf den Squeeze aus, sodass die Flip-Operation ** nur zwischen ** $ 01 $ und $ 10 $ ausgeführt wird. Wenn hier nur einer von $ 00 und 11 $ enthalten ist, kann der Squeeze nicht selbsterklärend sein, sodass -1 ausgegeben wird.
Angenommen, $ 01 $ ist $ a $ und $ 10 $ ist $ b $ und $ a > b $ (dasselbe gilt für $ a \ <b $, und $ a = b $ ist selbstverständlich. Es hält). In Anbetracht der Bedingungen, die gequetscht werden können, ist dies der Fall, wenn es mit $ 01 → 10 → 01 →… $ oder $ 10 → 01 → 01 →… $ aufgereiht ist und ** $ ab \ leqq 1 $ ** sein sollte ist. Um dies zu erreichen, müssen Sie nur $ [\ frac {a-b} {2}] $ von ** $ 01 $ ** invertieren, aber Sie können keine Zeichenfolgen auswählen, die beim Invertieren gleich sind. Außerdem beträgt die Anzahl der Zeichenketten, die durch die Inversionsoperation zwischen dem $ 01 $ -Muster und dem $ 10 $ -Muster übereinstimmen, jeweils $ l $ ($ , weil $ ** Inversion eine reversible Operation ** ist, sodass $ l $ ausreicht. Ich werde das machen). Wenn man bedenkt, dass die Differenz um $ 2m $ verringert wird, wenn das Muster von $ m $ invertiert wird, wird sie daher invertiert, wenn $ al \ <[\ frac {ab} {2}] \ mal 2 $. Du kannst tun.
Daher ist es möglich zu beurteilen, ob es möglich ist, zu invertieren und zu entfernen, und zu diesem Zeitpunkt kann auch die Anzahl der Elemente ermittelt werden, für die eine Inversionsoperation erforderlich ist, sodass Sie für diese Anzahl von Elementen aus $ 01 $ auswählen können. Bitte beachten Sie zu diesem Zeitpunkt, dass nur diejenigen ausgewählt werden, die nicht mit dem übereinstimmen, was in ** $ 10 $ enthalten ist **.
D.py
for _ in range(int(input())):
n=int(input())
s=[input() for i in range(n)]
t=set(s)
a,b,c,d=set(),set(),set(),set()
for i in range(n):
if s[i][0]=="0":
if s[i][-1]=="0":
c.add(i)
else:
a.add(i)
else:
if s[i][-1]=="0":
b.add(i)
else:
d.add(i)
l=set()
for i in range(n):
if (i in a or i in b) and (s[i][::-1] in t):
l.add(i)
la,lb,lc,ld,ll=len(a),len(b),len(c),len(d),len(l)
#print(la,lb,lc,ld,ll)
if la==0 and lb==0:
if lc==0 or ld==0:
print(0)
else:
print(-1)
continue
if lb>la:
if lb-ll//2<(lb-la)//2*2:
print(-1)
continue
x=(lb-la)//2
print(x)
if x==0:
continue
ans=[]
for i in b:
if i not in l:
ans.append(str(i+1))
x-=1
if x==0:
break
print(" ".join(ans))
elif la>lb:
if la-ll//2<(la-lb)//2*2:
print(-1)
continue
x=(la-lb)//2
print(x)
if x==0:
continue
ans=[]
for i in a:
if i not in l:
ans.append(str(i+1))
x-=1
if x==0:
break
print(" ".join(ans))
else:
print(0)
E Problem
Ich bin sehr enttäuscht, weil es bald gelöst zu sein schien. Ich habe unter Bezugnahme auf Hamayanhamayans Artikel aktualisiert.
Ein solches Problem ** führt dazu, dass der Rechenaufwand bei der Suche von jedem Scheitelpunkt ** explodiert. Daher ist es ein typisches Muster, die Merkmale des Diagramms zu paraphrasieren.
Mit anderen Worten, hier müssen Sie sowohl $ A als auch B $ passieren, mit anderen Worten, wenn Sie erreichen können, ohne entweder $ A oder B $ zu passieren, oder wenn Sie nur mit $ A oder B $ * erreichen können * Ausgeschlossen ** für den Fall (** Betrachten Sie die Verweigerung der Bedingung! **). Im ersteren Fall werden die Scheitelpunkte in der Verbindungskomponente gelöscht, wenn alle mit ** $ A und B $ verbundenen Seiten ** gelöscht sind. Um den ersteren Fall auszuschließen, sind ** Eckpunkte in verschiedenen Verbindungskomponenten enthalten ** Denken Sie nur darüber nach.
Im letzteren Fall hat es nicht funktioniert, weil ich über die Verbindungskomponente nachgedacht habe, als ich die Seite verwendet habe, die nur eine Verbindung zu $ A $ (oder $ B $) herstellt, aber ** ich werde die Verbindungskomponente früher verwenden ** Ist gut (** Konsistenz der Betrachtung! **). Hier ist das Diagramm, wenn alle mit $ A und B $ verbundenen Seiten gelöscht sind, nicht verbunden, aber jede verbundene Komponente ist gemäß ihrer Definition ** entweder direkt mit ** $ A oder B $ verbunden. Nutzen Sie das. Zu diesem Zeitpunkt gibt es nur drei Muster, in denen jede Verbindungskomponente sowohl mit $ A als auch mit B $ (①) verbunden ist, nur mit $ A $ (②) verbunden ist und nur mit $ B $ (③) verbunden ist. Da ist gar nichts. Von diesen durchlaufen nur die Muster (2) und (3) für beide Pfade, die die beiden Punkte verbinden, immer $ A und B $ (Sie können dies leicht herausfinden, indem Sie alle sechs Wege ausprobieren).
Daher gibt (\ die Anzahl der in der verketteten Komponente des Musters ② enthaltenen Scheitelpunkte) $ \ times $ (die Anzahl der in der verketteten Komponente des Musters ③ enthaltenen Scheitelpunkte) dies als Antwort aus.
E.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 Primmenge darstellt(Initialisieren Sie mit 1)
map<ll,set<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
}
//Stellen Sie fest, 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]].insert(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();
}
};
signed main(){
//Code zur Beschleunigung der Eingabe
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll t;cin>>t;
REP(_,t){
ll n,m,a,b;cin>>n>>m>>a>>b;a--;b--;
UnionFind uf(n);
set<ll> otheredgesA,otheredgesB;
REP(i,m){
ll u,v;cin>>u>>v;u--;v--;
if(u!=a and u!=b and v!=a and v!=b){
uf.unite(u,v);
}
if(u==a){
otheredgesA.insert(v);
}
if(v==a){
otheredgesA.insert(u);
}
if(u==b){
otheredgesB.insert(v);
}
if(v==b){
otheredgesB.insert(u);
}
}
uf.grouping();
ll countA=0;ll countB=0;
FORA(i,uf.group){
bool checkA=false;bool checkB=false;
if(i.F==a or i.F==b)continue;
FORA(j,i.S){
if(otheredgesA.find(j)!=otheredgesA.end()){
checkA=true;
}
if(otheredgesB.find(j)!=otheredgesB.end()){
checkB=true;
}
}
if(!checkB){
countA+=SIZE(i.S);
}
if(!checkA){
countB+=SIZE(i.S);
}
}
cout<<countA*countB<<endl;
}
}
F Problem
Ich werde diesmal überspringen.
Recommended Posts