[PYTHON] Codeforces Runde # 639 (Div. 2) Bacha Review (9/4)
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Problem A
Wenn der kleinere Wert von $ n $ und $ m $ 1 ist, können Sie ihn erstellen, indem Sie die konkaven und konvexen Teile der Reihe nach verbinden. In anderen Fällen gilt dies nur, wenn $ n = m = 2 $. (Ich habe richtig darüber nachgedacht und 1WA gemacht.)
Ich habe experimentell darüber nachgedacht, aber wenn ich es genau betrachte, wird es wie folgt sein. ** Da es nur wenige konkave Teile gibt, möchte ich sie so oft wie möglich an der Grenze verwenden **. Daher kann es gemacht werden, wenn die Anzahl der Grenzen kleiner als die Anzahl der konkaven Teile ist. Hier ist der Grenzteil nur $ n \ mal (m-1) + (n-1) \ mal m $, aber die Anzahl der Rätsel (die Anzahl der konkaven Teile) ist $ n \ mal m $. Daher muss $ n \ times (m-1) + (n-1) \ times m \ leqq n \ times m $ gelten. Zu diesem Zeitpunkt ist es $ (n -1) (m-1) \ leqq 1
A.py
for _ in range(int(input())):
x=list(map(int,input().split()))
if min(x)==1 or max(x)==2:
print("YES")
else:
print("NO")
B-Problem
Als ich zuerst darüber nachdachte, wie viele Karten ich für jede Pyramide benötigte, stellte ich fest, dass sie mit zunehmender Höhe in der Größenordnung von $ 2 \ rightarrow 7 \ rightarrow 15 \ rightarrow 26 \ rightarrow $ zunahm. Es ist auch klar, dass es rekursiv zunimmt ** und die Anzahl der Karten entsprechend der Differenzzahlenspalte zunimmt ($ a \ _ {i + 1} = a \ _ i + 3i + 5 $).
Da Sie in der Abfrage wiederholt gefragt werden, ** fragen Sie nach der Anzahl der Karten, die erforderlich sind, um jede Pyramide zuerst zu erstellen **. Da die Anzahl der Karten jedoch höchstens $ 10 ^ 9 $ beträgt, benötigen Sie mehr. Sie müssen nicht an die Pyramide denken. Experimente haben auch gezeigt, dass die Höhe einer Pyramide, die mit ** $ 10 ^ 9 $ hergestellt werden kann, höchstens $ 25820 $ ** beträgt. Daher ist es notwendig, eine Pyramide mit einer Höhe von $ 1 $ ~ $ 25820 $ herzustellen. Listen Sie die gesamte Anzahl der Karten auf (check).
Ziehen Sie dann in Betracht, die Abfrage zu verarbeiten. Hier müssen wir die höchste Pyramide erstellen, die mit den angegebenen $ n $ -Karten erstellt werden kann, damit wir aus dem "Scheck", nach dem wir mit "bisect_right" gesucht haben, eine niedrigere Pyramide erstellen können. ist. ** Sie können über die überschüssigen Karten mit einer rekursiven Funktion nachdenken ** und die Summe ausgeben.
B.py
check=[2]
i=0
while check[-1]<=10**9:
check.append(check[-1]+3*i+5)
i+=1
print(len(check))
from bisect import bisect_right
def dfs(x):
if x<2:
return 0
return dfs(x-check[bisect_right(check,x)-1])+1
for _ in range(int(input())):
n=int(input())
print(dfs(n))
C-Problem
Ich fand dieses Problem interessant.
Überlegen Sie, ob aufgrund des Mischens eine Übereinstimmung vorliegt. Erstens lautet die Verallgemeinerung dieses Shuffle $ k \ rightarrow k + a_ {k \ mod \ n} $. Wenn man bedenkt, ob es zu diesem Zeitpunkt im Shuffle dupliziert wird, wird es nicht dupliziert, wenn ** $ mod \ n $ gleich ** sind. Zum Beispiel sind $ k $ und $ k + n $ mod \ n $ gleich, aber $ k + n \ rechter Pfeil k + n + a_ {k \ mod \ n} $, also selbst wenn Sie mischen Es überlappt sich nicht.
Berücksichtigen Sie daher beim Mischen **, welche $ mod \ n $ Raumnummer von jeder $ mod \ n $ Raumnummer ** verschoben werden soll, und ** $ mod \ n $ kann übereinstimmen. Stellen Sie einfach sicher, dass Sie dies tun **. Suchen Sie daher für $ i = 0 $ ~ $ n-1 $ $ (i + a_ {i \ mod \ n}) \ mod \ n $, um eine Übereinstimmung zu finden. Wenn Sie den erhaltenen Wert der Mengenstruktur zuweisen, müssen Sie nur bestimmen, ob die Größe der Mengenstruktur $ n $ ist.
C.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
s=set()
for i in range(n):
s.add((i+a[i%n])%n)
#print(s)
print("YES" if len(s)==n else "NO")
D Problem
** Ich habe das Thema falsch verstanden und viele Fehler gemacht **. Es war bedauerlich. Unmittelbar nach dem Wettbewerb bestand die Lösung darin, die Fehler nach und nach auszufüllen, aber ich denke, dass ** ich sie ohne Fehler lösen konnte und die Implementierung leicht war, wenn ich die Überlegung beenden konnte, also bereue ich es.
Erstens kann der Süden nach Belieben platziert werden. Hier ** befindet sich jede Bewegung in derselben Zeile oder Spalte **. Konzentrieren wir uns also auf jede Zeile (oder Spalte). Zu diesem Zeitpunkt ** Wenn sich am linken und rechten Ende des schwarzen Teils einer Linie kein Süden befindet, kann diese Linie nicht vom Norden verfolgt werden **. Wenn der Süden am linken und rechten Rand platziert ist, kann der Norden zwischen ihnen hindurchgehen, sodass ** er vom linken bis zum rechten Rand schwarz gestrichen werden muss **.
Darüber hinaus verlangt Regel 1, dass in jeder Zeile und Spalte mindestens ein Südmagnet vorhanden ist. Zu diesem Zeitpunkt ist es ausreichend, wenn in einer Zeile und Spalte eine schwarze Zelle vorhanden ist. ** Wenn sie nicht vorhanden ist, aber eine Zeile und Spalte nicht mit einer anderen schwarzen Zelle teilt, platzieren Sie sie nach Süden. Ich kann**. Wenn Sie sich ** Zellen als Schnittpunkt von Zeilen und Spalten ** vorstellen, können Sie sie auch als ** umschreiben, wenn mindestens eine Zeile und eine Spalte ohne schwarze Zellen ** vorhanden sind.
Wenn das obige Urteil in einer Zeile und Spalte richtig ist, kann das Thema erfüllt werden. Zu diesem Zeitpunkt entspricht die erforderliche Anzahl von ** Nord der Anzahl der verbundenen Komponenten **, wenn das schwarze Quadrat als Scheitelpunkt betrachtet wird. Die Anzahl der verknüpften Komponenten wird in Union Find immer gezählt. Da sie sich jedoch im Raster ** befinden, wird die Anzahl mit BFS ** gezählt. Geben Sie dann einfach diesen Wert aus.
Der erste Code befindet sich nach dem Wettbewerb und der zweite Code dient zur Überprüfung.
D_worse.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
deque<pair<ll,ll>> d;
vector<vector<bool>> bfs_chk;
ll n,m;
void bfs(){
while(SIZE(d)){
ll l=SIZE(d);
REP(i,l){
ll c0,c1;c0=d.front().F;c1=d.front().S;
//cout<<c0<<" "<<c1<<endl;
vector<pair<ll,ll>> nex={MP(c0-1,c1),MP(c0+1,c1),MP(c0,c1-1),MP(c0,c1+1)};
FORA(j,nex){
//cout<<1<<endl;
if(0<=j.F and j.F<n and 0<=j.S and j.S<m){
//cout<<j.F<<" "<<j.S<<endl;
if(!bfs_chk[j.F][j.S]){
bfs_chk[j.F][j.S]=true;
d.PB(j);
//cout<<1<<endl;
}
}
}
d.pop_front();
}
}
}
signed main(){
//Code zur Beschleunigung der Eingabe
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
cin>>n>>m;
vector<string> s(n);REP(i,n)cin>>s[i];
bfs_chk=vector<vector<bool>>(n,vector<bool>(m,true));
REP(i,n)REP(j,m)bfs_chk[i][j]=(s[i][j]=='.');
ll ans=0;
//cout<<1<<endl;
REP(i,n){
REP(j,m){
if(bfs_chk[i][j]==false){
bfs_chk[i][j]=true;
d.PB(MP(i,j));
bfs();
ans++;
}
}
}
//cout<<1<<endl;
vector<bool> r(n,false);
vector<bool> c(m,false);
REP(i,n){
REP(j,m){
if(s[i][j]=='#'){
FOR(k,j,m-1){
if(s[i][k]=='.'){
FOR(l,k,m-1){
if(s[i][l]=='#'){
//cout<<2<<endl;
cout<<-1<<endl;
return 0;
}
}
break;
}else{
c[j]=true;
r[i]=true;
}
}
break;
}
}
}
REP(i,m){
REP(j,n){
if(s[j][i]=='#'){
FOR(k,j,n-1){
if(s[k][i]=='.'){
FOR(l,k,n-1){
if(s[l][i]=='#'){
//cout<<3<<endl;
cout<<-1<<endl;
return 0;
}
}
break;
}else{
r[j]=true;
c[i]=true;
}
}
break;
}
}
}
//Wenn Sie hinzufügen können
pair<vector<ll>,vector<ll>> addition;
REP(i,n){
ll co=0;
REP(j,m){
co+=ll(s[i][j]=='#');
}
if(co==0)addition.F.PB(i);
}
REP(j,m){
ll co=0;
REP(i,n){
co+=ll(s[i][j]=='#');
}
if(co==0)addition.S.PB(j);
}
FORA(i,addition.F){
FORA(j,addition.S){
r[i]=true;
c[j]=true;
}
}
//REP(i,n)cout<<r[i]<<endl;
//REP(i,m)cout<<c[i]<<endl;
if(all_of(ALL(r),[](boolx){returnx;})andall_of(ALL(c),[](boolx){returnx;})){
cout<<ans<<endl;
}else if(all_of(ALL(r),[](boolx){return!x;})andall_of(ALL(c),[](boolx){return!x;})){
cout<<ans<<endl;
}else{
//cout<<4<<endl;
cout<<-1<<endl;
}
}
D_better.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
deque<pair<ll,ll>> d;
vector<vector<bool>> bfs_chk;
ll n,m;
void bfs(){
while(SIZE(d)){
ll l=SIZE(d);
REP(i,l){
ll c0,c1;c0=d.front().F;c1=d.front().S;
//cout<<c0<<" "<<c1<<endl;
vector<pair<ll,ll>> nex={MP(c0-1,c1),MP(c0+1,c1),MP(c0,c1-1),MP(c0,c1+1)};
FORA(j,nex){
//cout<<1<<endl;
if(0<=j.F and j.F<n and 0<=j.S and j.S<m){
//cout<<j.F<<" "<<j.S<<endl;
if(!bfs_chk[j.F][j.S]){
bfs_chk[j.F][j.S]=true;
d.PB(j);
//cout<<1<<endl;
}
}
}
d.pop_front();
}
}
}
signed main(){
//Code zur Beschleunigung der Eingabe
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
cin>>n>>m;
vector<string> s(n);REP(i,n)cin>>s[i];
//cout<<1<<endl;
ll f=0;ll g=0;
REP(i,n){
ll li=-1;ll ri=-1;
//Linkes Ende
REP(j,m){
if(s[i][j]=='#'){
li=j;
break;
}
}
//Rechtes Ende
REPD(j,m){
if(s[i][j]=='#'){
ri=j;
break;
}
}
if(li==-1 and ri==-1){
f++;
continue;
}
FOR(j,li,ri){
if(s[i][j]!='#'){
cout<<-1<<endl;
return 0;
}
}
}
REP(j,m){
ll ui=-1;ll di=-1;
//Oberkante
REP(i,n){
if(s[i][j]=='#'){
ui=i;
break;
}
}
//unteres Ende
REPD(i,n){
if(s[i][j]=='#'){
di=i;
break;
}
}
if(ui==-1 and di==-1){
g++;
continue;
}
FOR(i,ui,di){
if(s[i][j]!='#'){
cout<<-1<<endl;
return 0;
}
}
}
//Wenn man nicht gut nach Süden fahren kann
if((f==0 and g!=0)or(f!=0 and g==0)){
cout<<-1<<endl;
return 0;
}
bfs_chk=vector<vector<bool>>(n,vector<bool>(m,true));
REP(i,n)REP(j,m)bfs_chk[i][j]=(s[i][j]=='.');
ll ans=0;
//cout<<1<<endl;
REP(i,n){
REP(j,m){
if(bfs_chk[i][j]==false){
bfs_chk[i][j]=true;
d.PB(MP(i,j));
bfs();
ans++;
}
}
}
cout<<ans<<endl;
}
Nach dem E-Problem
Ich werde diesmal überspringen
Recommended Posts