[PYTHON] Educational Codeforces Round 89 Bacha Review (9/8)
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Ich war nicht sehr vorsichtig mit dem D-Problem, aber ich bin froh, dass ich es später beheben konnte. Es ist gut, es wieder aufzubauen, aber ich bin weit davon entfernt, eine hochpräzise Richtlinie festzulegen, die mein Ziel ist. Deshalb möchte ich mich ihr widmen.
Problem A
Wenn Sie $ Schaufel $ um $ x $ und $ Schwert $ um $ y $ machen, dann $ 0 \ leqq 2x + y \ leqq a $ und $ 0 \ leqq x + 2y \ leqq b $. Zu diesem Zeitpunkt ergibt die Summe beider Gleichungen $ 0 \ leqq x + y \ leqq \ frac {a + b} {3} $.
Da ich $ x + y $ finden möchte, möchte ich auch annehmen, dass $ [\ frac {a + b} {3}] $ der Maximalwert ist, aber ** $ [\ frac {a + b} {3 }] $ muss kleiner oder gleich $ a $ und kleiner oder gleich $ b $ ** sein (weil $ \ weil x, y $ größer oder gleich 0 ist). Daher finden wir $ min ([\ frac {a + b} {3}], a, b) $.
A.py
for _ in range(int(input())):
a,b=map(int,input().split())
print(min((a+b)//3,a,b))
B-Problem
Es war gefährlich, weil ich es auf halbem Weg falsch verstanden habe. Kodofos Englisch hat manchmal ein Problem, das schwer zu lesen ist ...
Überlegen Sie, wie viele Indizes beim Tauschen endgültig auf 1 gesetzt werden können. Sie können auch im Bereich von $ l \ _i $ bis $ r \ _i $ tauschen. Da wir alle Indizes herausfinden möchten, die 1 sein können, können wir die Lösung finden, indem wir den Indexbereich ermitteln, der zum Zeitpunkt von $ i $ 1 sein kann, und den Bereich schrittweise erweitern.
Mit anderen Worten, beginnen Sie mit $ [x, x] $ und beginnen Sie mit dem kleinsten $ i $. Es ist einfacher zu verstehen, wenn Sie es in ein Diagramm schreiben, daher werde ich es von hier aus in einem Diagramm erläutern.
Infolgedessen werden die Abschnitte, die auf 1 gesetzt werden können, in der oben beschriebenen Reihenfolge erhalten, so dass die Länge des endgültig erhaltenen Abschnitts als Lösung erhalten werden kann.
B.py
for _ in range(int(input())):
n,x,m=map(int,input().split())
ans=[x,x]
for i in range(m):
l,r=map(int,input().split())
if r<ans[0] or l>ans[1]:
continue
else:
ans=[min(ans[0],l),max(ans[1],r)]
print(ans[1]-ans[0]+1)
C-Problem
Codeforces scheint viel BFS und DFS zu haben. Ich bin glücklich, weil ich es nicht gewohnt bin, es persönlich umzusetzen. Wenn Sie darüber nachdenken, können Sie nach diesem Problem fragen, ohne BFS zu verwenden.
(Zur Vereinfachung der Erklärung wird das Quadrat in 0-indiziert geändert.)
** Es wird symmetrisch **, wenn die Zahlen in den Quadraten für einen beliebigen Pfad angeordnet sind. Erstens haben von der Bedingung ** für jeden Pfad ** bei der Verfolgung von $ (0,0) $ bis $ (n-1, m-1) $ ** alle Zellen in derselben Entfernung dieselbe Nummer. Es wird **. Unter der Bedingung der ** Symmetrie ** sind außerdem die Anzahl der Quadrate mit einem Abstand von $ i $ und die Anzahl der Quadrate mit einem Abstand von $ n + m-2-i $ gleich **. Suchen Sie daher für jede der $ n \ times m $ -Zellen ** mit BFS nach Zellen mit demselben Abstand ** und speichern Sie sie für jede Zelle in "cand". Wenn es sich um $ (i, j) $ handelt, beträgt der Abstand $ (i, j) $, sodass er ohne Verwendung von BFS berechnet werden kann.
Nach dem Finden durch BFS werden die Zellen mit einem Abstand von $ i $ und die Zellen mit einem Abstand von $ n + m-2-i $ weiter zu einer in "cand" und der Anzahl von 0s und 1s darin kombiniert. Zähle und passe den kleineren dem größeren an. Wenn $ (n + m) % 2 = 0 $ ist, ist die Zelle mit einem Abstand von $ \ frac {n + m-2} {2} $ ** das Zentrum eines Pfades. Welche Zelle ist es also? Die Nummer ist auch gut **.
Die Implementierung ist nicht schwierig, wenn Sie wissen, dass ** die Implementierung in den Teil unterteilt ist, der die Masse für jede Tiefe teilt, und den Teil, der für jede Tiefe berechnet **.
C.py
from collections import deque
def bfs(dep):
global a,n,m,ans,d,check,cand
while len(d):
cand.append(list(d))
l=len(d)
for i in range(l):
p=d.popleft()
if p[1]<m-1:
if not check[p[0]][p[1]+1]:
d.append([p[0],p[1]+1])
check[p[0]][p[1]+1]=True
if p[0]<n-1:
if not check[p[0]+1][p[1]]:
d.append([p[0]+1,p[1]])
check[p[0]+1][p[1]]=True
for _ in range(int(input())):
n,m=map(int,input().split())
a=[list(map(int,input().split())) for i in range(n)]
d=deque([[0,0]])
check=[[False]*m for i in range(n)]
check[0][0]=True
cand=[]
bfs(0)
ans=0
for i in range((n+m-1)//2):
x=[a[j[0]][j[1]] for j in cand[i]+cand[n+m-1-1-i]]
ans+=min(x.count(0),x.count(1))
print(ans)
D Problem
Es verursachte ein Wunder, TL 2000ms in 1949ms zu passieren. Ich dachte, es würde vergehen, aber es war gefährlich.
Überlegen Sie zunächst, ob es $ d \ _1 $ und $ d \ _2 $ gibt, so dass $ gcd (d \ _1 + d \ _2, a \ _i) = 1 $ ist. Wenn hier in Primfaktoren ** zerlegt, wenn nur eine Primzahl ** vorhanden ist, sind $ d \ _1 $ und $ d \ _2 $ beide Vielfache dieser Primzahl, also $ gcd (d \ _1 + d \ _2, Es wird ein \ _i) \ neq 1 $ sein.
Daher betrachten wir im Folgenden die Bedingungen, wenn es zwei oder mehr Primzahlen gibt, wenn $ a \ _i $ faktorisiert wird. Zu diesem Zeitpunkt dachte ich, dass ~~ ** durch geeignete Auswahl beliebiger Primzahlen ** ~~ hinzugefügt werden sollte, aber es ist ein vollständiger Fehler.
Hier habe ich mir die Fallklassifizierung nach Gerade und Seltsamkeit ausgedacht und dabei auf ** Addition ** geachtet. Erstens kann im Fall einer ungeraden Zahl das kleinste $ a, b $ aus den in der Primfaktorisierung enthaltenen Primzahlen (ungerade) ausgewählt werden, und die Summe ist gerade. Darüber hinaus kann diese gerade Zahl als $ \ frac {a + b} {2} \ mal 2 $ ausgedrückt werden, ist jedoch kleiner als $ \ frac {a + b} {2} $ und ist in der Primfaktorisierung von $ a \ _i $ enthalten. Die einzige Primzahl ist $ a $, aber $ \ frac {a + b} {2} $ und $ a $ sind Primzahlen zueinander, und 2 ist nicht in der Primfaktorisierung von $ a \ _i $ enthalten, also solche $ a, b $ ist die Lösung $ d \ _1, d \ _2 $ (** Achten Sie auf den Extremfall kleiner Zahlen! **).
Wenn Sie im Fall einer geraden Zahl eine ungerade Zahl für $ d \ _1 und d \ _2 $ auswählen, ist die Summe eine gerade Zahl, also ist $ d \ _1 $ 2, $ d \ _2 $ eine bequeme ungerade Zahl. Muss ausgewählt werden. Zu diesem Zeitpunkt können Sie $ d \ _2 $ auswählen (multipliziert mit allen ungeraden Zahlen außer 2) (** Achten Sie auf den Extremfall einer großen Zahl! **). Dies liegt daran, dass zu diesem Zeitpunkt $ d \ _1 + d \ _2 $ nicht durch eine Primzahl geteilt werden kann, die in der Primfaktorisierung von $ a \ _i $ enthalten ist.
(Es war selbstverständlich, wenn es sich um eine ungerade Zahl handelte, aber wenn es sich um eine gerade Zahl handelte, war es möglicherweise schwierig, die Bedingung zu interpretieren, dass sie sich von einer Primzahl ** unterscheiden sollte. Dieser Bereich scheint vertraut zu sein.)
Aus dem Obigen kennen wir die Fälle von gerade und ungerade, damit wir die Lösung finden können. Obwohl oben nicht als selbsterklärend erwähnt, wird die Geschwindigkeit durch das Eratostenes-Sieb erhöht, um den Berechnungsbetrag der Primfaktorisierung logarithmisch zu machen.
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 10000000 //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
//MAXR=10^Beachten Sie, dass es 5 ist
#define PN 1 //Die Primzahl ist 1
vector<ll> PN_chk(MAXR+1,PN);//0-indexed(0~MAXR)
//Stellen Sie diese Option ein, um die in der Primfaktorisierung enthaltenen Primzahlen zu speichern
set<ll> prime;
//O(MAXR)
void init_eratosthenes(){
ll MAXRR=sqrt(MAXR)+1;
//Es zerfällt in Primfaktoren von 2 oder mehr Zahlen, sodass es ignoriert werden kann.
PN_chk[0]=0;PN_chk[1]=0;
FOR(i,2,MAXRR){
//Eine Primzahl, wenn bei Ihrer Ankunft davon ausgegangen wird, dass es sich um eine Primzahl handelt
//Markieren Sie ein Vielfaches einer Primzahl, da diese durch diese Primzahl teilbar ist
if(PN_chk[i]==1) FOR(j,i,ll(MAXR/i)){PN_chk[j*i]=i;}
}
}
//O(logn)
//Da es sich um eine Karte handelt, ist prime bereits ausgerichtet
//Es gibt nur zwei
void prime_factorize(ll n){
if(n<=1) return;
//if(SIZE(prime)==2)return;
//Wenn 1, ist n eine Primzahl
if(PN_chk[n]==1){prime.insert(n);return;}
//Markierte Zahlen sind Primzahlen
prime.insert(PN_chk[n]);
//Betrachten Sie die Anzahl der markierten Zahlen geteilt durch n
prime_factorize(ll(n/PN_chk[n]));
}
signed main(){
//Code zur Beschleunigung der Eingabe
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
init_eratosthenes();
ll n;cin>>n;
vector<ll> a(n);REP(i,n)cin>>a[i];
vector<ll> ans0(n,-1);
vector<ll> ans1(n,-1);
REP(i,n){
if(a[i]%2==1){
prime_factorize(a[i]);
if(SIZE(prime)>1){
ans0[i]=*prime.begin();
ans1[i]=*++(prime.begin());
}
prime.clear();
}else{
prime_factorize(a[i]);
if(SIZE(prime)>1){
ans0[i]=2;ans1[i]=1;
for(auto j=++prime.begin();j!=prime.end();j++){
ans1[i]*=(*j);
}
}
prime.clear();
}
}
REP(i,n){
if(i==n-1)cout<<ans0[i]<<"\n";
else cout<<ans0[i]<<" ";
}
REP(i,n){
if(i==n-1)cout<<ans1[i]<<"\n";
else cout<<ans1[i]<<" ";
}
}
E Problem
Ich konnte es im Wettbewerb nicht lösen, also habe ich nach dem Wettbewerb darüber nachgedacht. Es war nicht so schwierig wie ich erwartet hatte, deshalb möchte ich viel Zeit vor dem E-Problem lassen können.
Während des Experiments habe ich festgestellt, dass ** die Grenze des Bereichs, den das Ende des geteilten Abschnitts einnehmen kann, ziemlich streng ist . Da es schwierig ist zu überlegen, wo $ min $ erscheinen wird, wenn man das kleinere $ j $ von $ b \ _j $ betrachtet, werden wir ** von dem größeren $ j $ von ** $ b \ _ j $ ** betrachten. ( Von der anderen Seite scannen! **).
Zu diesem Zeitpunkt kann der mögliche Bereich des Werts am linken Ende des Intervalls ** unabhängig und eindeutig ** bestimmt werden.
(1) Was ist ganz rechts? ** $ a \ _i = b \ _j $ gilt, und das größte $ i $ ** befindet sich ganz rechts. Wenn $ a \ _i <b \ _j $ an einer Stelle größer als $ i $ ist, ist die Bedingung von $ min $ nicht erfüllt, sodass es 0 Möglichkeiten gibt.
(2) Was ist ganz links? (Unter der Bedingung, dass es das gleiche wie oder links vom äußersten rechten ist) ** $ a \ _i <b \ _j $ ist das erste, das $ i $ plus +1 hält ** ist das am weitesten links stehende .. Wenn dies mit $ j = 0 $ gilt, ist die Bedingung von $ min $ nicht erfüllt, sodass es 0 Möglichkeiten gibt.
Beachten Sie außerdem, dass bei ** $ j = 0 $ nur noch ein Ende übrig ist ($ a \ _0 $) **. Darüber hinaus wird sowohl für (1) als auch für (2) die while-Anweisung verwendet, um $ i $ von $ a \ _i $ zu reduzieren und den Bereich ganz links des Abschnitts zu scannen, aber ** während des Scans $ j \ neq Wenn Sie alle $ a \ _i $ mit 0 $ scannen, gibt es 0 Möglichkeiten, da ** das Thema nicht erfüllt.
Wenn Sie die obigen Eckfälle beachten und das Intervall des am weitesten links liegenden Werts in jedem $ j $ finden, können Sie die Lösung finden, indem Sie es multiplizieren.
E.py
mod=998244353
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ans=1
i=n-1
for j in range(m-1,-1,-1):
l,r=-1,-1
while i!=-1:
if a[i]<b[j]:
print(0)
exit()
if a[i]==b[j]:
r=i
break
i-=1
else:
print(0)
exit()
while i!=-1:
if a[i]<b[j]:
l=i+1
if j==0:
print(0)
exit()
break
i-=1
else:
if j!=0:
print(0)
exit()
if j!=0:
ans*=(r-l+1)
ans%=mod
#print(l,r)
print(ans)
Nach F Problem
Ich werde diesmal überspringen
Recommended Posts