[PYTHON] Codeforces Runde # 486 (Div. 3) Bacha Review (9/23)
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
** Ich habe anderthalb Stunden verschwendet, wenn ich das D-Problem für immer abgehört hätte **. Ich habe das E-Problem vermieden, weil ich es für problematisch hielt, aber als Ergebnis konnte ich es beheben, wenn ich die Fälle richtig klassifizierte, und bin daher enttäuscht. Ich konnte in D- und E-Problemen keine Eckfälle oder Fehler finden, da ich meine Überlegungen bisher nicht nutzen konnte. Daher werde ich meine Gedanken so organisieren, dass ich sie beim nächsten Mal nutzen kann.
Problem A
Da die Bewertungen unterschiedlich sein sollen, zählen wir die Anzahl der Bewertungstypen in der ** Set-Struktur und bestimmen, ob sie ** $ k $ überschreiten. Wenn es $ k $ oder mehr ist, werden entsprechende $ k $ Stücke ausgegeben. Ich habe hier den Index verwendet, um die Implementierung zu vereinfachen, aber eine andere Methode ist hinsichtlich des Rechenaufwands besser (ich werde sie hier nicht anzeigen, aber Sie können sie mit $ O (k) $ ausführen).
A.py
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(set(a))
if len(b)>=k:
print("YES")
ans=[]
for i in range(k):
ans.append(a.index(b[i])+1)
print(" ".join(map(str,ans)))
else:
print("NO")
B-Problem
Wenn es eine Zeichenfolgenreihenfolge gibt, die dem Betreff entspricht, hat jede Zeichenfolge (mit Ausnahme der ersten Zeichenfolge) die vorherige Zeichenfolge als Teilzeichenfolge. ** Diese Zeichenfolgenreihenfolge ist in aufsteigender Reihenfolge der Länge ** (Es kann durch die $ \ weil $ Absurditätsmethode gezeigt werden).
Daher sollte die angegebene Zeichenfolge in aufsteigender Reihenfolge der Länge korrigiert und danach beurteilt werden, ob jede in der unmittelbar vorhergehenden Zeichenfolge enthalten ist. Zu diesem Zeitpunkt beträgt der Berechnungsbetrag $ O (N ^ 2) $.
B.py
n=int(input())
a=[input() for i in range(n)]
a.sort(key=lambda x:len(x))
for i in range(n-1):
if a[i] not in a[i+1]:
print("NO")
break
else:
print("YES")
for i in range(n):
print(a[i])
C-Problem
Wählen Sie zwei Sequenzen aus und extrahieren Sie jeweils ein Element, um das mit der gleichen Summe zu finden. Hier gibt es $ n \ _i $ Summen zum Extrahieren eines Elements aus der Folge der $ i $ -ten Länge $ n \ _i $, abhängig davon, welches Element extrahiert wird. Aus der Einschränkung ergibt sich außerdem $ \ sum \ _ {i = 1} ^ {k} {n \ _i} \ leqq 2 \ times 10 ^ 5 $, sodass ** diese Summe vollständig ** aufgezählt werden kann.
Hier ist die Summe, wenn das $ j $ -te Element der $ i $ -ten Länge $ n \ _i $ -Sequenz extrahiert wird (die Summe der $ i $ -ten Sequenz) - (das $ j $ -te Element). Wert), und wenn die Summe jeder Sequenz im Voraus berechnet wird, kann sie mit $ O (\ sum \ _ {i = 1} ^ {k} {n \ _ i}) $ berechnet werden. Wenn Sie das Wörterbuch $ m $ als Vektor platzieren, in dem der Schlüssel als Summenwert der Sequenz und der Wert als "Wert (Index der Sequenz, Index des extrahierten Elements)" gespeichert sind, kann die Summe der zuvor erhaltenen Sequenzen in der angegebenen Reihenfolge angeordnet werden. Kann aufbewahrt werden. Wenn zu diesem Zeitpunkt zwei oder mehr ** Sequenzen mit demselben Schlüssel, aber unterschiedlichen Indizes ** vorhanden sind, kann dies als Antwort ausgegeben werden. Im Gegenteil, wenn es niemanden mit zwei oder mehr gibt, sollte Nein ausgegeben werden.
(Ich habe es nicht bemerkt, aber ich konnte es in Python schreiben. Warum habe ich es in C ++ geschrieben ...?)
C.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 k;cin>>k;
map<ll,vector<pair<ll,ll>>> m;
REP(i,k){
ll ni;cin>>ni;
vector<ll> a(ni);REP(j,ni)cin>>a[j];
ll s=0;REP(j,ni)s+=a[j];
REP(j,ni){
m[s-a[j]].PB(MP(i+1,j+1));
}
}
FORA(i,m){
if(SIZE(i.S)>1){
map<ll,ll> x;
//Beseitigen Sie die gleiche Anzahl von Zeilen
FORA(j,i.S){
x[j.F]=j.S;
}
if(SIZE(x)>1){
auto y=x.begin();
cout<<"YES"<<endl;
cout<<y->F<<" "<<y->S<<endl;
y++;
cout<<y->F<<" "<<y->S<<endl;
return 0;
}
}
}
cout<<"NO"<<endl;
}
D Problem
(Operationen von Union Find werden als nahezu konstant angesehen und der Rechenaufwand wird angezeigt.)
Wenn Sie dies mit dem Bild tun, eine Teilmenge aus dem Ganzen auszuwählen, sind Sie möglicherweise vom Sumpf abhängig. Beachten Sie, dass der Abstand zwischen den beiden Punkten $ 2 ^ d $ und das Maximum $ 2 \ mal 10 ^ 9 $ beträgt, sodass Sie nur ** $ d = $ 0 ~ 30 ** betrachten müssen.
Zu diesem Zeitpunkt sollten Sie die größte Teilmenge ** für jedes $ d $ finden. Wenn Sie auf einen bestimmten Punkt $ x $ achten, sind die durch $ 2 ^ d $ getrennten Punkte $ x-2 ^ d, x + 2 ^ d $, und wenn alle Punkte durch Mengen verwaltet werden, werden sie ** getrennt. Sie können überprüfen, ob es einen Punkt mit $ O (\ log {n}) $ ** gibt ($ O (n \ log {n}) $, wenn Sie zu irgendeinem Zeitpunkt prüfen). Wenn Sie daher ** UnionFind verwenden, um Punkte zu verbinden, die $ 2 ^ d $ voneinander entfernt sind **, können Sie einige Teilmengen von Punkten erstellen, wie unten gezeigt.
Ich möchte auch sagen, dass alle Punkte, die in der Teilmenge der obigen Abbildung enthalten sind, in der Teilmenge enthalten sind, die das Thema erfüllt, aber ** ich kann nur bis zu 3 Punkte ** einschließen. Dies liegt daran, dass, wenn die Punkte größer als 3 sind, immer eine Reihe von Punkten enthalten ist, deren Abstand nicht die Potenz von 2 ist.
Aus dem Obigen wird die Vereinigungssuche für jedes von $ d = $ 0 bis 30 durchgeführt (wenn die Elemente in der Menge in aufsteigender Reihenfolge angeordnet sind, beträgt der Koordinatenabstand $ 2 ^ d $), und es wird ein Primmengen-System erhalten. Wenn es mindestens einen gibt, ** gibt drei benachbarte Punkte ** aus, wenn die Menge in aufsteigender Reihenfolge angeordnet ist, und wenn es mindestens einen mit 2 Elementen gibt (der die obigen Bedingungen nicht erfüllt), die Menge Es werden zwei Punkte ausgegeben, und in anderen Fällen sollte ein geeigneter Punkt ausgegeben werden.
Da ich den Index beim Zusammenführen von Punkten angeben wollte, habe ich "ind" als Map ** vorbereitet, die dem Wert einen Index gibt, und den Index zum Zeitpunkt der Ausgabe in den Elementwert geändert. Ich habe val als Vektor vorbereitet. Da die von UnionFind erhaltene Menge in aufsteigender Reihenfolge des Index ** vorliegt, ist es außerdem erforderlich, ** val in aufsteigender Reihenfolge zu korrigieren und in ind ** zu speichern, um der aufsteigenden Reihenfolge der Werte zu entsprechen. es gibt. (Ich habe nicht bemerkt, dass ich nicht in aufsteigender Reihenfolge sortiert habe, und das Debuggen hat mehrere Stunden gedauert ... Es war ein Fehler, den ich in der Diskussionsphase bemerkt habe. Wenn ich also ungeduldig bin, möchte ich ihn mit meinen eigenen Gedanken vergleichen. .)
9/25 Nachtrag
Wenn Sie nur auf die Tatsache achten, dass es höchstens drei gibt, können Sie es leicht und mit hoher Geschwindigkeit implementieren, indem Sie nur zur Seite schauen. Ich wünschte, ich hätte das bemerkt. Siehe den zweiten Python-Code.
D.cc
//Debug-Optionen:-fsani
//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,vector<ll>> group;//Assoziatives Array, das für jeden Primsatz verwaltet wird(Schlüssel ist das übergeordnete Element jeder Primzahl, Wert ist ein Array von Elementen dieser Primzahl)
ll n;//Anzahl der Elemente
//Konstrukteur
UnionFind(ll n_):parent(n_),siz(n_,1),n(n_){
//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
//Kleinen Satz zu großem Satz 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
}
//Bestimmen Sie, 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]].PB(i);
}
void clear(){
for(ll i=0;i<n;i++){parent[i]=i;}
siz=vector<ll>(n,1);
group.clear();
}
};
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n;cin>>n;
set<ll> x;
//Ind für Wert
map<ll,ll> ind;
//Wert für ind
vector<ll> val(n);
REP(i,n){
ll y;cin>>y;
x.insert(y);
val[i]=y;
}
sort(ALL(val));
REP(i,n){
ind[val[i]]=i;
}
vector<ll> v(1,0);
pair<ll,vector<ll>> ans=MP(1,v);
UnionFind uf(n);
REP(i,31){
uf.clear();
FORA(j,val){
if(x.find(j+(1LL<<i))!=x.end()){
uf.unite(ind[j],ind[j+(1LL<<i)]);
}
}
uf.grouping();
for(auto j=uf.group.begin();j!=uf.group.end();j++){
if(SIZE(j->S)>ans.F){
//Überschreitet nicht 3
//Nicht sortiert(val ist)huh? ?? ?? ?? ?? ?? ??
if(ans.F==1){
if(SIZE(j->S)==2){
vector<ll> w(2);
w={j->S[0],j->S[1]};
ans=MP(2,w);
}else{
cout<<3<<endl;
cout<<val[j->S[0]]<<" "<<val[j->S[1]]<<" "<<val[j->S[2]]<<endl;
return 0;
}
}
if(ans.F==2){
if(SIZE(j->S)>2){
cout<<3<<endl;
cout<<val[j->S[0]]<<" "<<val[j->S[1]]<<" "<<val[j->S[2]]<<endl;
return 0;
}
}
}
}
}
cout<<ans.F<<endl;
REP(i,ans.F){
if(i==ans.F-1){
cout<<val[ans.S[i]]<<endl;
}else{
cout<<val[ans.S[i]]<<" ";
}
}
}
D.py
n=int(input())
x=list(map(int,input().split()))
y=set(x)
ans=[x[0]]
for d in range(31):
e=2**d
for i in range(n):
if x[i]-e in y and x[i]+e in y:
print(3)
print(x[i]-e,x[i],x[i]+e)
exit()
elif x[i]-e in y:
ans=[x[i],x[i]-e]
elif x[i]+e in y:
ans=[x[i],x[i]+e]
if len(ans)==2:
print(2)
print(ans[0],ans[1])
else:
print(1)
print(ans[0])
E Problem
Es ist nicht schwer darüber nachzudenken, aber ich dachte, es sei ein problematisches Problem, die Implementierung abzuschließen.
Erstens ist die Bedingung für ein Vielfaches von 25, wenn die letzten beiden Ziffern eine von $ 00, 25, 50, 75 $ sind. Es ist auch selbstverständlich, dass Sie ** tauschen und die Zahlen so nah wie möglich bringen ** sollten. Wenn jedoch eine Zahl in der höchstwertigen Ziffer ** angegeben ist, kann 0 in der höchstwertigen Ziffer stehen, sodass die Fälle zu diesem Zeitpunkt getrennt werden müssen. Im Fall von $ 00 $ müssen nur zwei der gleichen Zahl berücksichtigt werden, und der höchstwertigen Ziffer wird keine Zahl zugewiesen. Daher habe ich beschlossen, sie ** getrennt von den anderen drei ** zu betrachten.
Erstens, wenn es nur eine Ziffer gibt, ist es schwierig, Fälle zu unterscheiden, so dass -1 im Voraus ausgegeben wird. Und selbst wenn es aus zwei Ziffern besteht, ** war es schwierig, Fälle zu unterscheiden ** (WA wurde ebenfalls ausgegeben), so dass 0 für 25,75,50 $ und 1 für 52,57 $ ausgegeben wird.
Finden Sie auf dieser Grundlage die Mindestanzahl von Swaps, die erforderlich sind, um 25,50,75 $ auf die letzte Ziffer zu bringen. Hier ist die Funktion zum Ermitteln der Mindestanzahl von Malen $ calc1 $, und die Argumente sind $ x, y $ ($ (x, y) = (2,5), (5,0), (7,5) $). .. Zunächst möchten wir beim Tauschen wissen, wie weit die niedrigstwertige Ziffer entfernt ist. Daher sehen wir die angegebene Zahl als Array von Zahlen und drehen sie um (nennen wir sie $ m $). Wenn $ x und y $ nicht in den Ziffern enthalten sind, ist die Mindestanzahl nicht vorhanden und $ inf $ wird zurückgegeben. Basierend darauf wird der Index von $ x, y $ in $ m $ als $ ix, iy $ berechnet. Wenn sich weder ** $ x, y $ ganz rechts befindet (höchstwertige Ziffer) **, ist es am besten, in der Reihenfolge von derjenige zu tauschen, die der niedrigstwertigen Ziffer am nächsten liegt (die kleinere von $ ix, iy $). , Wenn $ ix <iy $, wird die niedrigstwertige Ziffer so wie sie ist invertiert, sodass ein weiterer Swap erforderlich ist.
Als nächstes betrachten Sie **, wenn sich eines ganz rechts befindet **, aber da sowohl $ x als auch y $ dieselbe Operation sind, mit Ausnahme des Austauschs zwischen den niedrigstwertigen Ziffern, befindet sich $ x $ ganz rechts. Die Zeit von wird unten betrachtet. Wenn sich $ x $ ganz rechts befindet, schauen Sie von der höchstwertigen bis zur letzten Ziffer, wählen Sie das erste Element aus, das nicht ** 0 ist und dessen Index nicht $ iy $ ist, und tauschen Sie mit der höchstwertigen Ziffer. Da ** die optimale Anzahl von Malen ist, tauschen Sie sie aus. Wenn es kein Element gibt, das nicht 0 ist und sein Index nicht $ iy $ ist, gibt es $ inf $ zurück ($ 25,75,50,52,57 $, was ursprünglich als Fall ausgeschlossen wurde, ** erfüllt dies nicht, also zuerst Der Fall wurde in ** unterteilt.). Und wenn diese Ziffer $ i $ ist, kann die Anzahl der Austausche mit der höchstwertigen Ziffer leicht berechnet werden. Wenn ** $ i <iy $, $ iy- = 1 $ durch Tausch hinzugefügt wird, wenn $ i $ auf die obere Ziffer ** übertragen wird, seien Sie also vorsichtig. Wenn Sie also mit der höchstwertigen Ziffer tauschen können, können Sie $ iy $ und dann $ ix $ tauschen und die Gesamtzahl der Swaps zählen.
Wenn Sie die niedrigstwertige Ziffer auf $ 00 $ setzen möchten, können Sie den Index von $ 00 $ finden, der der niedrigstwertigen Ziffer am nächsten liegt, und ihn von der nächstgelegenen Ziffer näher an die niedrigstwertige Ziffer verschieben. Es wird eine Implementierung sein.
Aus dem Obigen kann die minimale Anzahl von Malen für jeden Fall von $ 00, 25, 50, 75 $ berechnet werden, und die minimale Anzahl von Malen kann berechnet werden, aber wenn die minimale Anzahl von Malen $ inf $ ist, wird -1 ausgegeben. müssen es tun.
Überraschenderweise war es ein Problem, das nicht so schwer umzusetzen war. Ich möchte mein Bestes geben, um solche Probleme unfreiwillig umzusetzen.
E.py
n=[int(i) for i in input()]
l=len(n)
#Auch wenn die Länge 2 ist
if len(n)==1:
print(-1)
exit()
#Nur in diesem Fall
if n in [[2,5],[7,5],[5,0]]:
print(0)
exit()
if n in [[5,2],[5,7]]:
print(1)
exit()
inf=10**12
#Wenn es ganz links ist, ist es ärgerlich, also werde ich die Fälle trennen.(Umkehren)
#00 ist ebenfalls in Fälle unterteilt
def calc1(x,y):
global n,l,inf
m=n[::-1]
if x not in n or y not in n:
#print(x,y,0)
return inf
ix,iy=m.index(x),m.index(y)
#Wenn nicht ganz rechts
if max(ix,iy)<l-1:
if iy<ix:
#print(x,y,1)
return iy+(ix-1)
else:
#print(x,y,2)
return iy+(ix-1)+1
else:
ret=0
#print(ix,iy)
if ix==l-1:
#Schauen Sie von rechts und schauen Sie nach links(0 und nicht die andere zu wählen)
for i in range(l-2,-1,-1):
if m[i]!=0 and i!=iy:
break
else:
#print(x,y,3)
return inf
if i<iy:
iy-=1
ret+=(l-1-i)
ix-=1
ret+=(iy+(ix-1))
#print(x,y,4,ret)
return ret
else:
ret+=iy
ret+=(l-1-i)
ix-=1
ret+=(ix-1)
#print(x,y,5,ret)
return ret
else:
#Schauen Sie von rechts und schauen Sie nach links(0 und nicht die andere zu wählen)
#Die einzige Möglichkeit des anderen zu wählen(Zuerst eliminieren)
#Mach es draußen
for i in range(l-2,-1,-1):
if m[i]!=0 and i!=ix:
break
else:
#print(x,y,6)
return inf
if i<ix:
iy-=1
ret+=(l-1-i)
ix-=1
ret+=(iy+(ix-1)+1)
#print(x,y,7,ret)
return ret
else:
ret+=iy
ret+=(l-1-i)
ix-=1
ret+=((ix-1)+1)
#print(x,y,8,ret)
return ret
#Um 00
def calc2(x,y):
#Absolut nicht ganz rechts
global n,l,inf
if n.count(0)<2:
return inf
m=[l-1-i for i in range(l) if n[i]==0][::-1]
return m[0]+m[1]-1
ans=min([calc1(2,5),calc1(7,5),calc1(5,0),calc2(0,0)])
#print([calc1(2,5),calc1(7,5),calc1(5,0),calc2(0,0)])
print(-1 if ans==inf else ans)
F Problem
Ich werde diesmal überspringen
Recommended Posts