[PYTHON] Codeforces Runde # 662 (Div. 2) Bacha Review (8/8)
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Ich war ungeduldig mit Problem A und machte einen Fehler im Experiment und nahm mir Zeit. ** Wenn das Experiment falsch ist ** Ich konnte mich bisher nicht darum kümmern, deshalb möchte ich vorsichtig sein. Ich habe ungefähr eine Stunde mit A verbracht, aber solch ein ** Einfallsreichtum, der nicht in den Sumpf passt ** (** weg vom Problem **, ** kann eine grundlegend falsche oder falsche Implementierung sein Ich würde gerne ** berücksichtigen, etc.). Ich denke, dass solche Muster in der Vergangenheit von Bachacon und Wettbewerben gesammelt werden können, deshalb würde ich es gerne tun, wenn ich eine ** Zusammenfassung aller Fehler machen kann, die ich bisher gemacht habe **.
(Auch die Überprüfung hat sich verzögert. Ich würde gerne vorsichtig sein, aber wenn sich andere Aufgaben überschneiden ...)
Problem A
Betrachten Sie zunächst das Experimentieren mit solchen rätselhaften Problemen. Allerdings habe ich im Puzzle-Experiment einen Fehler gemacht. Solange es peinlich ist.
Wenn Sie das Experiment genau durchführen, wird es wie in der folgenden Abbildung gezeigt.
Wenn Sie dieses Experiment korrekt durchführen können, wissen Sie, dass $ [\ frac {n} {2}] $ wahrscheinlich die Antwort ist, aber Sie sollten auf die rekursive Struktur achten. Mit anderen Worten, der äußere Rahmen sollte separat betrachtet werden und wird wie folgt.
A.py
def f(x):return x//2+1
for i in range(int(input())):
n=int(input())
print(f(n))
B-Problem
Ich habe das Gefühl, dass in ABC ein Problem mit der Abwärtskompatibilität aufgetreten ist.
Das Problem besteht darin, die Bretter zu kombinieren, um ein Quadrat und ein Rechteck zu erstellen. Die Platinen können jedoch nicht angeschlossen oder geschnitten werden.
Hier kann ein Quadrat mit ** 4 Brettern gleicher Länge ** und ein Rechteck mit ** 2 Sätzen mit 2 Brettern gleicher Länge ** hergestellt werden. Daher ist es ausreichend, vier oder mehr Karten bzw. zwei oder mehr Karten aufzunehmen und eine oder mehrere Karten mit vier oder mehr Karten und zwei oder mehr Karten mit zwei oder mehr Karten zu haben. Wenn es jedoch ** 8 oder mehr Bretter gleicher Länge ** gibt, können Sie mit nur diesen Brettern ein Quadrat und ein Rechteck erstellen, und wenn es ** 6 oder mehr Bretter gleicher Länge ** gibt, Sie können zwei Seiten erstellen, quadratisch und rechteckig. Sie müssen also auch über diese Fälle nachdenken.
Daher werden von oben 2 oder mehr Karten, 4 oder mehr Karten, 6 oder mehr Karten und 8 oder mehr Karten als Sätze gespeichert ("d2", "d4", "d6", "d8"). Auf diese Weise können Sie beurteilen, ob Sie ein Quadrat und ein Rechteck erstellen können. Außerdem denke ich, dass es zu diesem Zeitpunkt einfacher wäre, ** zu implementieren, wenn das Array als Element festgelegt worden wäre **, daher möchte ich versuchen, bisher vorsichtig zu sein **.
B.py
n=int(input())
a=list(map(int,input().split()))
q=int(input())
d=dict()
for i in range(n):
if a[i] in d:
d[a[i]]+=1
else:
d[a[i]]=1
d2,d4,d6,d8=set(),set(),set(),set()
for i in d:
if d[i]>=8:
d8.add(i)
elif d[i]>=6:
d6.add(i)
elif d[i]>=4:
d4.add(i)
elif d[i]>=2:
d2.add(i)
for i in range(q):
s,x=input().split()
x=int(x)
if s=="+":
if x in d:
d[x]+=1
if d[x]==2:
d2.add(x)
elif d[x]==4:
d2.remove(x)
d4.add(x)
elif d[x]==6:
d4.remove(x)
d6.add(x)
elif d[x]==8:
d6.remove(x)
d8.add(x)
else:
d[x]=1
else:
d[x]-=1
if d[x]==1:
d2.remove(x)
elif d[x]==3:
d4.remove(x)
d2.add(x)
elif d[x]==5:
d6.remove(x)
d4.add(x)
elif d[x]==7:
d8.remove(x)
d6.add(x)
if len(d8)>0:
print("YES")
elif len(d6)>=2:
print("YES")
elif len(d6)==1 and len(d4)+len(d2)>0:
print("YES")
elif len(d4)>=2:
print("YES")
elif len(d4)==1 and len(d2)>=2:
print("YES")
else:
print("NO")
C-Problem
(Experimente und Illustrationen waren in diesem Problem ziemlich lebendig.)
Wenn Sie Kuchen nacheinander essen, sollten Sie so viel Zeit wie möglich lassen, um denselben Kuchen zu essen.
Hier ** hat eine große Anzahl von Kuchen ein enges Zeitintervall **, daher regelt diese große Anzahl von Kuchen ** die maximale Entfernung, die Sie finden möchten **. Daher dachte ich, dass es besser wäre, die Position in der Reihenfolge aus dem Kuchen mit der größten Anzahl zu bestimmen. Basierend auf dieser Annahme habe ich die erste Stichprobe unten betrachtet.
7
1 7 1 6 4 4 6
In der obigen Stichprobe sind die drei Zahlen 1,4,6 jeweils zweimal und 7 nur einmal. Überlegen Sie sich daher, wo 1,4,6 liegt. Zu diesem Zeitpunkt kann der maximale Abstand von 3 erreicht werden, indem wie in der folgenden Abbildung gezeigt angeordnet wird.
Die Punkte hier sind "1-4-6 als ** Klumpen ** zu platzieren, ohne die Reihenfolge zu verschieben" und "jeden Klumpen an beiden Enden zu platzieren". Dadurch kann jede Nummer so weit wie möglich voneinander entfernt platziert werden. Ich habe auch versucht zu sehen, ob das Gleiche für das zweite Beispiel unten gilt.
8
1 1 4 6 4 6 4 7
In dieser Stichprobe erscheinen die meisten Kuchen in 3 von 4 Kuchen. Zu diesem Zeitpunkt kann der maximale Abstand von 2 erreicht werden, indem wie in der folgenden Abbildung gezeigt angeordnet wird.
Hier wird 4 an beiden Enden und so gleichmäßig wie möglich zwischen ihnen platziert. Durch Anpassen der Reihenfolge der verbleibenden Kuchen (1 → 6 in der obigen Abbildung) wird der maximale Abstand nicht beeinflusst. Daher sollten Sie ** nur den Kuchen mit der größten Anzahl ** berücksichtigen, und die Art des Kuchens mit der größten Anzahl ist $ m $ und die Anzahl ist $ k $, wie in der folgenden Abbildung gezeigt.
Da wir also die Entfernung in diesem Problem finden wollen, lautet die Antwort (Massenlänge-1) = $ [\ frac {n-m} {k-1}] -1 $.
C.py
from collections import Counter
for _ in range(int(input())):
n=int(input())
s=list(map(int,input().split()))
d=Counter(s)
d=list(d.items())
d.sort(reverse=True,key=lambda x:x[1])
l=len(d)
now=[1,d[0][1]]
for i in range(1,l):
if now[1]==d[i][1]:
now[0]+=1
else:
break
k=now[1]
m=now[0]
print((n-m)//(k-1)-1)
D Problem
Ich konnte es während des Wettbewerbs nicht bestehen, aber ich bin froh, dass ich es bald danach lösen konnte. ** Ich rase vorne und kann keine Zeit mit den Problemen hinten verbringen.
Zuerst habe ich die gleiche Abbildung ** wie die Problemstellung geschrieben. In der Abbildung oben sehen Sie, dass vier Kleidungsmuster generiert wurden, die zum Thema passen, wobei die Mitte ein rotes Gitter ist. Darüber hinaus kann die Anzahl der auf einem bestimmten Raster zentrierten Kleidungsmuster in vier Richtungen der Reihe nach gezählt und in Form von BFS gesucht werden.
Da Kleider nur das gleiche Alphabet (untere Buchstaben) enthalten, ist es auch möglich, die Anzahl der auf jedem Gitter zentrierten Kleidermuster für jedes Alphabet in etwa $ O ((n \ times m) ^ 2) $ zu suchen. ist. Wenn jedoch nichts unternommen wird, wird die Suche nicht innerhalb des Zeitlimits abgeschlossen, und der Suchbereich wird beim Zählen offensichtlich abgedeckt. Reduzieren Sie daher den Rechenaufwand auf etwa ** $ O (n \ mal m) $ **. Nachdenken über. Außerdem wollte ich es ermöglichen, ** nach jedem Alphabet gleichzeitig ** nach ungefähr $ O (n \ times m) $ zu suchen.
Oben wird bei der Suche berücksichtigt, dass die Anzahl der auf jedem Raster zentrierten Kleidungsmuster ** auf dem Raster ** aufgezeichnet ist. Wenn also die Aufzeichnung im folgenden Beispiel von Hand erfolgt, erfolgt die Aufzeichnung für a Es wird wie folgt sein.
6 6
zbaagd
baaacd
aaaaae
eaaadc
cdafed
aecdae
| 0 | 0 | 1 | 1 | 0 | 0 |
|---|---|---|---|---|---|
| 0 | 1 | 2 | 1 | 0 | 0 |
| 1 | 2 | 3 | 2 | 1 | 0 |
| 0 | 1 | 2 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 |
Erstens sind alle a ** 1 oder mehr **. Wenn es in einer der vier Richtungen ** eine 0 gibt (oder ein a ganz am Ende steht), kann es als 1 bestimmt werden. Es scheint auch schwierig zu sein, 2 oder 3 sofort zu entscheiden, aber mir wurde klar, dass ich anscheinend in der Reihenfolge ** 1 → 2 → 3 →… ** entscheiden kann.
Mit anderen Worten, wenn alle vier Richtungen ** 1 sind, dann 2 und wenn alle vier Richtungen 2 sind, dann 3 ... Mit anderen Worten, nachdem Sie den Startpunkt auf 1 festgelegt haben, können Sie mit dem Berechnungsbetrag von $ O (N \ mal M) $ mithilfe von BFS suchen.
Da die Zeitbeschränkungen sehr streng sind, ist es auch erforderlich, Methoden wie (1) Verwenden von C ++, (2) Wiederverwenden von ** Vektor ** und (3) Weitergeben von Gitterinformationen in ** Paaren an die in BFS verwendete Deque zu entwickeln.
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
//Paar statt Vektor
//Generieren Sie nicht jedes Mal einen Vektor
signed main(){
//Code zur Beschleunigung der Eingabe
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll ans=0;
ll n,m;cin>>n>>m;
vector<string> x(n);REP(i,n)cin>>x[i];
vector<char> alph(26);alph[0]='a';
for(ll i=1;i<26;i++){
alph[i]=alph[i-1];
alph[i]++;
}
vector<vector<ll>> y(n,vector<ll>(m,0));
vector<vector<bool>> check(n,vector<bool>(m,true));
FORA(i,alph){
REP(j,n)REP(k,m)y[j][k]=(x[j][k]==i);
REP(j,n)REP(k,m)check[j][k]=(x[j][k]!=i);
ll d=2;
deque<pair<ll,ll>> b;
REP(j,n){
REP(k,m){
if(j==0 or j==n-1 or k==0 or k==m-1){
if(y[j][k]){
check[j][k]=true;
b.PB(MP(j,k));
}
}else if(!(y[j-1][k] and y[j+1][k] and y[j][k-1] and y[j][k+1])){
if(y[j][k]){
check[j][k]=true;
b.PB(MP(j,k));
}
}
}
}
while(SIZE(b)){
ll l=SIZE(b);
REP(_,l){
pair<ll,ll> c=*(b.begin());b.pop_front();
if(c.F>0){
if(! check[c.F-1][c.S]){
check[c.F-1][c.S]=true;
y[c.F-1][c.S]=d;
b.PB(MP(c.F-1,c.S));
}
}
if(c.F<n-1){
if(! check[c.F+1][c.S]){
check[c.F+1][c.S]=true;
y[c.F+1][c.S]=d;
b.PB(MP(c.F+1,c.S));
}
}
if(c.S>0){
if(! check[c.F][c.S-1]){
check[c.F][c.S-1]=true;
y[c.F][c.S-1]=d;
b.PB(MP(c.F,c.S-1));
}
}
if(c.S<m-1){
if(! check[c.F][c.S+1]){
check[c.F][c.S+1]=true;
y[c.F][c.S+1]=d;
b.PB(MP(c.F,c.S+1));
}
}
}
d+=1;
}
REP(j,n)REP(k,m)ans+=y[j][k];
}
cout<<ans<<endl;
}
Nach dem E-Problem
Ich werde diesmal überspringen
Recommended Posts