[PYTHON] Codeforces Runde # 648 (Div. 2) Bacha Review (9/5)
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Dieses Mal habe ich meine üblichen Überlegungen genutzt und ** ruhig gearbeitet **, aber ich konnte relativ gute Ergebnisse erzielen. Ich habe jedoch die Angewohnheit, vorübergehend meine Konzentration zu verlieren, wenn ich auf ein Problem stoße, das berücksichtigt werden muss **, daher möchte ich mich dort übermäßig konzentrieren können.
Ich habe auch das Gefühl, dass ich ein bisschen mehr Ergebnisse erzielen konnte, aber da dies wahrscheinlich das erste Mal für Gokan ist, möchte ich es in Zukunft als Motivationsquelle nutzen.
(Mit Ausnahme dieses Artikels habe ich 3 Bewertungen gesammelt, daher möchte ich ihn schnell verarbeiten.)
Problem A
Sie können die Zeilen und Spalten, die die Craiming-Zelle enthalten, nicht auswählen. Hier kann die Anzahl der Zeilen und Spalten, die keine Craiming-Zelle aus der ersten Eingabe enthalten, als "mr, mc" ($ O (m \ times n) $) berechnet werden.
Zu diesem Zeitpunkt kann jede Person ** eine aus den nicht enthaltenen Zeilen und Spalten auswählen und die Zelle an der Kreuzung auswählen **, und die Person, die durch Abwechseln dieser Operation nicht auswählen kann, verliert. Ich werde. Außerdem ist die Anzahl der Operationen "min (mr, mc)", und der Gewinner wird durch die Seltsamkeit der Anzahl der Operationen bestimmt.
A.py
for _ in range(int(input())):
n,m=map(int,input().split())
r,c=[False]*n,[False]*m
for i in range(n):
x=list(map(int,input().split()))
if not all(k==0 for k in x):
r[i]=True
for j in range(m):
if x[j]==1:
c[j]=True
z=min(r.count(False),c.count(False))
print(["Vivek","Ashish"][z%2])
B-Problem
Beachten Sie, dass es sich um einen Austausch ** zwischen verschiedenen Typen handelt, nicht nur zwischen demselben Typ.
Wenn die $ i $ -te Zahl nach dem Sortieren die $ j $ -te sein sollte und $ i $ und $ j $ unterschiedliche Typen sind, wird dies durch Ausführen eines Austauschs zwischen $ i $ und $ j $ realisiert. Ist möglich. Wenn andererseits $ i $ und $ j $ vom gleichen Typ sind, ** über den Tausch zwischen verschiedenen $ k $ -ten Zahlen verschiedener Typen ** (Tausch bei $ j $ und $ k $ → $ Dies kann durch den Swap in der Reihenfolge i $ und $ k $ erreicht werden. Daher ist es möglich, nach dem Thema ** zu sortieren, wenn mindestens einer von jedem Typ vorhanden ist. Auch wenn es nur einen Typ in der Zahlenspalte gibt, kann gesagt werden, dass eine Sortierung durchgeführt werden kann, wenn die ** Zahlenspalte bereits sortiert ist **. Daher werden diese Fälle wie folgt beschrieben.
B.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
c=sorted(a)
b=list(map(int,input().split()))
if a==c:
print("Yes")
continue
if b.count(1)==n or b.count(0)==n:
print("No")
else:
print("Yes")
C-Problem
Es ist klar, dass die Zyklusverschiebung ** höchstens einmal ** sein sollte. Es ist auch klar, dass eine vollständige Suche in $ n $ Straßen mit Zyklusverschiebungen zu $ O (N ^ 2) $ ** führt und nicht rechtzeitig erfolgt. Anstatt uns auf Verschiebungen zu konzentrieren, haben wir uns daher darauf konzentriert, wie viele Schichten jedes Element benötigt. Außerdem ist die Gesamtzahl der Elemente, die verschoben und abgeglichen werden können, auf ** $ n $ in $ n $ Verschiebungen begrenzt, sodass ich auf die Idee kam, auf die Elemente zu achten.
Sobald Sie eine Idee haben, auf die Elemente zu achten, ist der Rest nicht schwierig. Sie können leicht herausfinden, um wie viel jedes Element aus dem Array $ a $ und dem Array $ b $ verschoben werden muss. Außerdem kann zu diesem Zeitpunkt (Index bei $ b $) - (Index bei $ a $) ** negativ ** sein, also fügen Sie in diesem Fall $ n $ hinzu. Auf diese Weise konnten wir die erforderlichen Verschiebungen für jedes Element speichern. Daher haben wir die Counter-Klasse verwendet, um die Anzahl der Elemente für jede Verschiebung zu speichern und die maximale Anzahl der Elemente zu berechnen.
C.py
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
#Position jedes Elements
ind=[0 for i in range(n)]
for i in range(n):
ind[a[i]-1]+=i
for i in range(n):
ind[b[i]-1]-=i
for i in range(n):
if ind[i]<0:
ind[i]+=n
from collections import Counter
c=Counter(ind)
ans=1
for i in c:
ans=max(ans,c[i])
print(ans)
D Problem
** Ich habe einen Fehler im Variablennamen gemacht ** oder ihn auf -1 gesetzt, wobei ich +1 hinzugefügt habe und ungeduldig war, ohne das Beispiel zu durchlaufen. Die Richtlinie wurde schnell perfektioniert, daher möchte ich hart daran arbeiten, eine stabile Implementierung sicherzustellen. Außerdem ** habe ich beim Nachverfolgen mit BFS Polster verwendet ** Ich konnte den Beurteilungsteil (im Vergleich zu unserer Firma) ordentlich schreiben, daher möchte ich ihn von nun an verwenden.
Da es sich um einen Wechsel zu einem Teil handelt, der eine Seite gemeinsam nutzt, sollten Sie ihn in BFS oder DFS implementieren. Außerdem entweicht G und B entkommt nicht, aber ** B ist restriktiver **. Erwägen Sie daher, diese Bedingung zuerst zu erfüllen. Wenn B entweicht, soll das Muster entweder erreichen, wo G ist, oder $ (n, m) $ direkt erreichen. In beiden Fällen ist es daher erforderlich, eine Wand in die Mitte zu stellen. Sie können auch sehen, dass die Wahrscheinlichkeit, $ (n, m) $ in ** G zu erreichen, umso höher ist, je kleiner der Bereich ist, in dem die Wand platziert ist. Mit anderen Worten, wenn es B gibt, können Sie ** Wände von allen Seiten ** anbringen. Wenn $ G $ auf allen Seiten enthalten ist und die Wand nicht platziert werden kann, kann das Motiv an diesem Punkt nicht erfüllt werden, und in anderen Fällen kann die Wand auf allen Seiten umgeben sein. Für die Bedingung, dass B nicht entkommen kann, ist es daher notwendig und ausreichend, Wände an allen vier Seiten anzubringen.
Basierend darauf werden wir ** G-Escape-Bedingungen ** berücksichtigen, aber die Bedingung, dass jedes G durch BFS oder DFS $ (n, m) $ erreichen kann (verwenden Sie das BFS, das Sie hier mögen). Es ist nicht schwer zu paraphrasieren. Wenn Sie jedoch BFS für jedes G ausführen, müssen Sie bis zu $ (50 \ mal 50) ^ 2 $ mal suchen, und es gibt bis zu 100 Testfälle, sodass dies offensichtlich nicht rechtzeitig ist. Können wir hier unter Ausnutzung der Tatsache, dass das endgültige Ziel das gleiche wie $ (n, m) $ ist, ** jedes $ G $ von $ (n, m) $ aus erreichen? Überlegen. Zu diesem Zeitpunkt ist ** ein BFS erforderlich **, sodass die Suche $ 50 \ mal 50 $ mal beträgt und in einer relativ langsamen Sprache wie Python implementiert werden kann.
Bei der Implementierung können Sie dies in zwei Schritten tun: (1) Füllen Sie den Bereich um B aus → (2) Führen Sie BFS durch. Bitte beachten Sie jedoch, dass es folgende Fälle gibt.
(1) Wenn $ G $ auf allen Seiten in ① → Ausgabe Nr (2) Wenn $ (n, m) $ eine Wand oder $ B $ ist und kein ** $ G $ ** vorhanden ist → Ja wird ausgegeben. (3) Wenn $ (n, m) $ eine Wand ist oder $ B $ und $ G $ existieren → Ausgabe Nr (4) Wenn $ G $ vorhanden ist, das bei ② → No nicht gesucht werden kann, wird ausgegeben (5) Wenn $ G $, das nicht durchsucht werden kann, in ② → Ausgabe Ja nicht vorhanden ist
D.py
from collections import deque
def bfs():
global n,m,s,d,check
#print(d)
while len(d):
l=len(d)
for i in range(l):
p=d.popleft()
for j in [[p[0],p[1]+1],[p[0],p[1]-1],[p[0]+1,p[1]],[p[0]-1,p[1]]]:
#print([[p[0],p[1]+1],[p[0],p[1]-1],[p[0]+1,p[1]],[p[0]-1,p[1]]])
#print(check[j[0]][j[1]])
if not check[j[0]][j[1]]:
check[j[0]][j[1]]=True
d.append(j)
#print(d)
for _ in range(int(input())):
n,m=map(int,input().split())
s=[["#" for i in range(m+2)]]+[list("#"+input()+"#") for i in range(n)]+[["#" for i in range(m+2)]]
f=False
#Füllen Sie um B.
for i in range(1,n+1):
for j in range(1,m+1):
if s[i][j]=="B":
for k in [[i,j+1],[i,j-1],[i-1,j],[i+1,j]]:
if s[k[0]][k[1]]=="G":
f=True
elif s[k[0]][k[1]]==".":
s[k[0]][k[1]]="#"
#print(s)
if f:
print("No")
continue
#Suche mit bfs
if s[n][m]=="B" or s[n][m]=="#":
for i in range(1,n+1):
for j in range(1,m+1):
if s[i][j]=="G":
f=True
if not f:
print("Yes")
else:
print("No")
continue
d=deque()
d.append([n,m])
check=[[(s[i][j]=="B") or (s[i][j]=="#") for j in range(m+2)] for i in range(n+2)]
check[n][m]=True
#print(check)
bfs()
for i in range(1,n+1):
for j in range(1,m+1):
if s[i][j]=="G" and check[i][j]==False:
f=True
#if f:
#print(s)
#print(check)
#print(3)
if f:
print("No")
continue
print("Yes")
E Problem
Die Implementierung musste nicht C ++ sein, aber ich habe mich für C ++ entschieden, weil ich insgesamt $ 10 ^ 7 $ durchlaufen musste.
Zunächst war die Problemstellung schwer zu lesen, aber zusammenfassend ist das Problem wie folgt (obwohl meine Zusammenfassung auch schwer zu lesen ist ...).
"Wenn $ k $ number aus der Zahlenfolge $ a $ der Länge $ n $ ausgewählt wird, steht $ max (1, k-2) $ oder mehr in der ausgewählten Zahl für jedes Bit. Hier erfahren Sie, wie Sie die Zahl auswählen, die die Antwort maximiert, einschließlich des Bits in der Antwort. "
Zuallererst bewegt sich ** jedes Bit unabhängig **, so dass es schwierig erscheint, eine solche Zahl gierig zu wählen **. Also habe ich vorerst mit $ k = 1,2 $ ein bisschen passend gesetzt und darüber nachgedacht. Dann bemerkte ich, dass $ k = 1,2,3 $ ausgewählt werden sollte, damit so viele Bits wie möglich gesetzt werden können ** ($ \ weil max (1, k-2) = 1 $). Wenn jedoch $ k = 4 $, $ max (1, k-2) = 2 $ ist und selbst wenn eine Zahl hinzugefügt wird, erhöht sich die Anzahl jedes Bits um höchstens eins, also $ k = Die Antwort enthält kein neues Bit, indem von 3 $ auf $ k = 4 $ erhöht wird. Das Gleiche gilt für $ k \ geqq 5 $, daher sollte ** $ k $ als bis zu 3 ** betrachtet werden.
Aus dem Obigen können Sie überlegen, wie Sie 3 Zahlen auswählen, aber höchstens $ _ {500} C_3 = 2.07085 \ mal 10 ^ 7 $, und Sie können ** alle ** suchen. Da es nur erforderlich ist, dass eine Anzahl von Bits steht, wenn drei Zahlen ausgewählt werden, ist es auch nur erforderlich, bitweise zu berechnen oder den Maximalwert zu finden. Wenn jedoch $ n = 1,2 $ ist, ist die Lösung das bitweise oder aller Elemente.
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 Endungen)、のどちらOder
//Wenn es kein D gibt, wird die Schleifenvariable um 1 erhöht, und wenn es ein D gibt, wird die Schleifenvariable 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 n;cin>>n;
vector<ll> a(n);REP(i,n)cin>>a[i];
ll ans=0;
REP(i,n){
FOR(j,i+1,n-1){
FOR(k,j+1,n-1){
ans=max(ans,a[i]|a[j]|a[k]);
}
}
}
if(n==1)cout<<a[0]<<endl;
else if(n==2)cout<<(a[0]|a[1])<<endl;
else cout<<ans<<endl;
}
Nach F Problem
Ich werde diesmal überspringen
Recommended Posts