[PYTHON] Wettbewerbsfähiges professionelles Andachtstagebuch 18. bis 19. Tag (7/12 bis 7/13)
<! - Wettbewerbsfähige Vorlage für professionelle Hingabe->
Impressionen
Ich werde mein Bestes geben mit dem Bedauern des ABC-Klassenwettbewerbs am Samstag. Ich hoffe auch, diese Woche einige Bibliotheken zu organisieren.
Tag 18
Zeit genommen
Diskussion 10 Minuten, Implementierung 10 Minuten
Erwägung
Da die Überlegung übersichtlich zusammengefasst wurde, wurde die Implementierung reibungslos abgeschlossen. Im Folgenden wird das $ i $ -Zeichen von $ t $ als $ t_i $ und das $ i $ -Zeichen von $ s $ als $ s_i $ bezeichnet.
Erstens können Sie $ t $ erstellen, wenn es nur aus den in $ s $ enthaltenen Zeichen besteht, sodass jedes Zeichen von $ t $ so schnell wie möglich in $ s \ ^ {'} $ erscheint ** Ich werde gierig wählen **. Überlegen Sie nun, welches $ s_k $ $ t_ {i + 1} $ entspricht, da ** $ s_j $ als ** $ t_i $ ausgewählt wird.
Wenn $ t_ {i + 1} = s_k (k> j) $ gilt, können Sie $ s_k $ ** (✳︎), das Minimum von $ k $, als $ t_ {i + 1} $ auswählen. Wenn jedoch $ t_ {i + 1} = s_k (k> j) $ nicht gilt, ist ** $ s_k $, das kleinste $ k $ unter den $ s $, das als nächstes erscheint, $ t_ {i Sie können es als +1} $ auswählen. Sie können die richtige Antwort erhalten, indem Sie dies für jedes $ t_i $ wiederholen.
Oben müssen wir in der Lage sein, den Index des Alphabets, der in $ s $ angezeigt wird, schnell zu finden. Speichern Sie also, welcher Index für jedes Alphabet in einem (aufsteigenden) Array vorhanden ist. Wenn Sie es in aufsteigender Reihenfolge speichern, finden Sie das Minimum $ k (> j) $ in (✳︎) mit bisect_right. Wenn Sie sich das letzte Zeichen ansehen, ist der Fall etwas anders, sodass Sie bei der Implementierung etwas vorsichtig sein müssen (Einzelheiten finden Sie im Code).
Python-Code
abc138E.py
from bisect import bisect_right
s=input()
t=input()
ns=len(s)
nt=len(t)
alp=[[] for i in range(26)]
for i in range(ns):
alp[ord(s[i])-97].append(i)
alpl=[len(alp[i]) for i in range(26)]
ans=0
now=-1
for i in range(nt):
if alpl[ord(t[i])-97]==0:
exit(print(-1))
b=bisect_right(alp[ord(t[i])-97],now)
if b==alpl[ord(t[i])-97]:
now=alp[ord(t[i])-97][0]
ans+=ns
if i==nt-1:
ans+=(now+1)
else:
now=alp[ord(t[i])-97][b]
if i==nt-1:
ans+=(now+1)
print(ans)
abc138E.py
from bisect import bisect_right
s=input()
t=input()
ns=len(s)
nt=len(t)
alp=[[] for i in range(26)]
for i in range(ns):
alp[ord(s[i])-97].append(i)
alpl=[len(alp[i]) for i in range(26)]
ans=0
now=-1
for i in range(nt):
if alpl[ord(t[i])-97]==0:
exit(print(-1))
b=bisect_right(alp[ord(t[i])-97],now)
if b==alpl[ord(t[i])-97]:
now=alp[ord(t[i])-97][0]
ans+=ns
if i==nt-1:
ans+=(now+1)
else:
now=alp[ord(t[i])-97][b]
if i==nt-1:
ans+=(now+1)
print(ans)
Zeit genommen
Nur eine TLE über 30 Minuten → 1 Stunde oder länger debuggen, um konstante Zeiten zu beschleunigen
Fehlerursache
Die Ursache war, dass ich falsch verstanden habe, dass $ O (n ^ 3) $ unter dem Maximum von $ n = 1000 $ passieren würde. → Vergessen Sie nicht, den Rechenaufwand zu überprüfen
Erwägung
Da die Ursache ist, habe ich es versäumt, den Rechenaufwand zu überprüfen und die Zeit auf unbestimmte Zeit geschmolzen ... Infolgedessen bedauere ich, dass ich die unnötige Berechnung nur mit der einfachen Antwort von $ O (N ^ 3) $ entfernen musste.
Erstens, da es ** Beschränkungen für die Reihenfolge ** gibt, denke ich, dass es möglich sein kann, ehrlich zu entscheiden (spielen in der Reihenfolge von der Person, die spielen kann), und es gibt einen besseren Fall als ** ehrlich zu entscheiden. Nein **, daher denke ich, dass diese Richtlinie korrekt ist.
Wenn Sie die Personen, die gegeneinander spielen können, als Paar speichern, wie unten gezeigt, können Sie die Personen, die gegeneinander spielen, in der angegebenen Reihenfolge bestimmen.
Wenn Sie hier die kämpfbaren Kombinationen am $ i $ -Tag im Wörterbuch d speichern, ist die Kombination mit dem ** Wert 2 schlachtbar **, also neben jeder Person, die in dieser kampfbaren Kombination enthalten ist Wenn Sie das Speichern der Gegner (die, an denen Sie gerade in "b" teilnehmen) wiederholen, in einem neuen Wörterbuch als Paar wiederholen, ist das Mindestdatum erforderlich, wenn Sie alle Spiele beendet haben Es wird die Anzahl der Tage sein.
Wenn an einem bestimmten Tag keine Kombination mit einem Wert von 2 vorhanden ist, wird -1 ausgegeben, da dies der gleiche Wert ist wie keine Kombination von Übereinstimmungen, die die Bedingungen erfüllen.
Wenn Sie außerdem die Kombination mit dem Wert 2 aus "d" löschen und das nächste Gegnerpaar zu "d" hinzufügen, während Sie die Kombination mit dem Wert 2 in der Anweisung ** für überprüfen Da der Iterator durch Löschen und Hinzufügen von Elementen mit beschädigt wird, ** tun Sie dies, nachdem alle Überprüfungen abgeschlossen sind **.
Übrigens ist es bei dieser Richtlinie $ O (N ^ 3) $, aber die Kombination, bei der der Wert am ** $ i + 1 $ Tag 2 ist, kann nur der aktualisierte Wert am $ i $ Tag sein. Hmm **. Wenn Sie sich also nur die Person changeable1 ansehen, die am $ i $ -Tag aktualisiert wurde, ohne alle im d am $ i + 1 $ -Tag enthaltenen Kombinationen zu betrachten, stimmen alle $ \ frac {N (N-) überein. Alles, was Sie tun müssen, ist 1)} {2} $ Straßen zu überprüfen, und Sie können den Rechenaufwand auf $ O (N ^ 2) $ reduzieren und schnell genug berechnen.
Eine andere Lösung
Dieses Mal werde ich es nur leicht berühren, aber wenn Sie die Tatsache ausnutzen, dass die Reihenfolge für jedes Spiel festgelegt ist, ist die Reihe der Spiele eine halb geordnete Menge **. ** Da eine halbgeordnete Menge immer durch eine DAG (Directed Acyclic Graph) ohne geschlossenen Pfad dargestellt werden kann **, kann dieses Problem mithilfe einer Suche mit Tiefenpriorität gelöst werden.
Weitere Informationen zu alternativen Lösungen finden Sie in diesem Artikel (https://algo-logic.info/abc139e/).
C ++ - Code (nicht angenommen)
abc139e.cc
//Zur Compileroptimierung
#pragma GCC optimize("Ofast")
//Einschließen(Alphabetischer Reihenfolge)
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
#define REP(i,n) for(ll i=0;i<n;i++)
//x ist ein Container wie ein Vektor
#define SIZE(x) ll(x.size())
#define PB push_back //In Vektor einfügen
#define MP make_pair //Paarkonstruktor
#define F first //Das erste Element des Paares
#define S second //Das zweite Element des Paares
#define Umap unordered_map
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n;cin>>n;
vector<vector<ll>> a(n,vector<ll>(n-1));
REP(i,n){
REP(j,n-1){
ll c;cin>>c;
if(c-1<i)a[i][j]=c-1+n*i;
else a[i][j]=i+n*(c-1);
}
}
Umap<ll,ll> d;
REP(i,n)d[a[i][0]]++;
vector<ll> b(n,0);
ll ans=0;
deque<ll> nextd;
deque<ll> cleard;
while(!d.empty()){
ans++;
bool g=true;
for(const auto& i : d){
if(i.S==2){
g=false;
ll e=(i.F)/n;ll f=(i.F)%n;
cleard.insert(cleard.begin(),i.F);
b[e]++;b[f]++;
if(b[e]<n-1)nextd.insert(nextd.begin(),a[e][b[e]]);
if(b[f]<n-1)nextd.insert(nextd.begin(),a[f][b[f]]);
}
}
if(g){
cout<<-1<<endl;
return 0;
}
ll ln,lc;ln=SIZE(nextd);lc=SIZE(cleard);
REP(i,ln){
d[*--nextd.end()]++;
nextd.pop_back();
}
REP(i,lc){
d.erase(*--cleard.end());
cleard.pop_back();
}
}
cout<<ans<<endl;
return 0;
}
abc139e.cc
//Zur Compileroptimierung
#pragma GCC optimize("Ofast")
//Einschließen(Alphabetischer Reihenfolge)
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
#define REP(i,n) for(ll i=0;i<n;i++)
//x ist ein Container wie ein Vektor
#define SIZE(x) ll(x.size())
#define PB push_back //In Vektor einfügen
#define MP make_pair //Paarkonstruktor
#define F first //Das erste Element des Paares
#define S second //Das zweite Element des Paares
#define Umap unordered_map
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n;cin>>n;
vector<vector<ll>> a(n,vector<ll>(n-1));
REP(i,n){
REP(j,n-1){
ll c;cin>>c;
if(c-1<i)a[i][j]=c-1+n*i;
else a[i][j]=i+n*(c-1);
}
}
Umap<ll,ll> d;
REP(i,n)d[a[i][0]]++;
vector<ll> b(n,0);
ll ans=0;
deque<ll> nextd;
deque<ll> cleard;
while(!d.empty()){
ans++;
bool g=true;
for(const auto& i : d){
if(i.S==2){
g=false;
ll e=(i.F)/n;ll f=(i.F)%n;
cleard.insert(cleard.begin(),i.F);
b[e]++;b[f]++;
if(b[e]<n-1)nextd.insert(nextd.begin(),a[e][b[e]]);
if(b[f]<n-1)nextd.insert(nextd.begin(),a[f][b[f]]);
}
}
if(g){
cout<<-1<<endl;
return 0;
}
ll ln,lc;ln=SIZE(nextd);lc=SIZE(cleard);
REP(i,ln){
d[*--nextd.end()]++;
nextd.pop_back();
}
REP(i,lc){
d.erase(*--cleard.end());
cleard.pop_back();
}
}
cout<<ans<<endl;
return 0;
}
Python-Code (angenommen)
abc139e.py
from collections import deque
n=int(input())
#Jede Länge ist n-1
a=[[j-1+n*i if j-1<i else i+n*(j-1) for j in list(map(int,input().split()))] for i in range(n)]
#Geben Sie Kandidaten für das Spiel ein
d=dict()
for i in range(n):
if a[i][0] in d:
d[a[i][0]]+=1
else:
d[a[i][0]]=1
#Wie weit hast du gesehen?
b=[0]*n
#Maximum n(n-1)/Zweimal
ans=0
nextd=deque()
cleard=deque()
changeable1=deque(set([a[i][0] for i in range(n)]))
while len(d):
ans+=1
#Wenn keiner von ihnen gleich ist
g=True
changeable2=deque()
for i in changeable1:
if d[i]==2:
g=False
e,f=i//n,i%n
cleard.append(i)
b[e]+=1
b[f]+=1
if b[e]<n-1:
nextd.append(a[e][b[e]])
changeable2.append(a[e][b[e]])
if b[f]<n-1:
nextd.append(a[f][b[f]])
changeable2.append(a[f][b[f]])
if g:
exit(print(-1))
ln,lc=len(nextd),len(cleard)
for _ in range(ln):
i=nextd.popleft()
if i in d:
d[i]+=1
else:
d[i]=1
for _ in range(lc):
i=cleard.popleft()
d.pop(i)
changeable1=set(changeable2)
print(ans)
abc139e.py
from collections import deque
n=int(input())
#Jede Länge ist n-1
a=[[j-1+n*i if j-1<i else i+n*(j-1) for j in list(map(int,input().split()))] for i in range(n)]
#Geben Sie Kandidaten für das Spiel ein
d=dict()
for i in range(n):
if a[i][0] in d:
d[a[i][0]]+=1
else:
d[a[i][0]]=1
#Wie weit hast du gesehen?
b=[0]*n
#Maximum n(n-1)/Zweimal
ans=0
nextd=deque()
cleard=deque()
changeable1=deque(set([a[i][0] for i in range(n)]))
while len(d):
ans+=1
#Wenn keiner von ihnen gleich ist
g=True
changeable2=deque()
for i in changeable1:
if d[i]==2:
g=False
e,f=i//n,i%n
cleard.append(i)
b[e]+=1
b[f]+=1
if b[e]<n-1:
nextd.append(a[e][b[e]])
changeable2.append(a[e][b[e]])
if b[f]<n-1:
nextd.append(a[f][b[f]])
changeable2.append(a[f][b[f]])
if g:
exit(print(-1))
ln,lc=len(nextd),len(cleard)
for _ in range(ln):
i=nextd.popleft()
if i in d:
d[i]+=1
else:
d[i]=1
for _ in range(lc):
i=cleard.popleft()
d.pop(i)
changeable1=set(changeable2)
print(ans)
Tag 19
Zeit genommen
Ich weiß es nicht, nachdem ich es ungefähr 30 Minuten lang benutzt habe → Erklärung AC
Fehlerursache
Ich war nicht zuversichtlich in meine Lösung. Die Lösung konnte nicht vereinfacht werden.
Erwägung
Erstens, wenn es ** nicht rechtzeitig ist, alle Kandidaten in einer solchen Summenberechnung ** und ** innerhalb des Bereichs zu zählen, in dem die Wertkandidaten gezählt werden können **, dann sind die Wertkandidaten in der Summenberechnung. Sie können beschleunigen, indem Sie darüber nachdenken, wie oft es angezeigt wird **.
In diesem Problem können wir sehen, dass es nur $ 1 \ leqq X_ {L, R} \ leqq N-1 $ $ N-1 $ gibt, also scheinen wir nach Wertkandidaten zählen zu können.
Betrachten Sie als nächstes die Bedingungen der Problemstellung, wenn $ L, R (1 \ leqq L <R \ leqq N) $, die zweite Zahl in $ P_L, P_ {L + 1},…, P_R $ Ist $ X_ {L, R} $. Wenn also $ P_i $ zu $ X_ {L, R} $ wird, gibt es in $ P_L, P_ {L + 1},…, P_R $ nur eine Zahl, die größer als ** $ P_i $ * ist *Machen. Um herauszufinden, ob es eine Möglichkeit gibt, $ L, R $ auf diese Weise auszuwählen, sollten Sie daher auf Zahlen achten, die größer als ** $ P_i $ ** sind. Daher sollten solche Zahlen rote Kreise und $ P_i $ blaue Kreise sein. Es wird durch und wie in der folgenden Abbildung dargestellt dargestellt. (Es bedeutet, dass Sie ** binarisieren **, ob es größer als $ P_i $ ist.)
$ L und R $ können so ausgewählt werden, dass sie rote und blaue Kreise zwischen ① und ② in der obigen Abbildung (✳︎) enthalten, sodass das nächste Element auf der linken Seite der Zahlen größer als ** $ P_i $ 2 ist Es kann gesagt werden, dass es nur notwendig ist, die zwei nächsten Elemente auf der rechten Seite zu kennen **.
Wenn Sie hier versuchen, jedes Mal nach einem größeren Element aus $ P_1, P_2,…, P_N $ für jedes $ P_i $ zu suchen, suchen Sie insgesamt nur $ O (N ^ 2) $, was nicht rechtzeitig ist. Es ist jedoch besser, den ** verschwenderischen Suchbereich ** zu betrachten, und der ** muss nur die Anzahl der Indizes kennen, die größer als ** $ P_i $ ** sind. Mit anderen Worten, wenn Sie einen Container "s" vorbereiten, in dem nur Zahlen gespeichert sind, die größer als diese Zahl sind, können Sie mit hoher Geschwindigkeit berechnen, indem Sie den Index ** in der Reihenfolge der größten Zahl überprüfen und in "s" speichern. .. Außerdem muss ** s bestellt werden **, damit Sie die beiden Indizes nachschlagen können, die links und rechts am nächsten an $ i $ liegen **, daher habe ich mich für set hier entschieden.
Die obige Richtlinie kann wie folgt zusammengefasst werden.
Fügen Sie den Index in absteigender Reihenfolge in s ein. Wenn Sie in diesem Kind den Index $ i $ der Zahl $ P_i $ einfügen, die Sie in s betrachten, befinden sich die kleinsten zwei Indizes ( r1 <r2) auf der rechten Seite und das Minimum auf der linken Seite Suchen Sie den Index (l1> l2) der beiden Zahlen in und suchen Sie die Zahl, wenn $ X_ {L, R} = P_i $. Es besteht auch die Möglichkeit, dass "r1", "r2", "l1", "l2" nicht existieren, also "-2", "-1", "n" als Index für den Wächter ** Speichern Sie , n + 1zuerst ins`. Darunter kann die Zahl, wenn $ X_ {L, R} = P_i $ erfüllt ist, durch (✳︎) berechnet werden, wie in der folgenden Abbildung gezeigt.
Auch wenn "l1 <0" ist, gibt es keinen Fall, der satisf erfüllt, und wenn "r1> n-1" ist, gibt es keinen Fall, der ② erfüllt, so dass es notwendig ist, diese Muster in der Berechnung auszuschließen. Ja, Sie können ein $ O (N \ log {N}) $ -Programm schreiben, indem Sie die obige Berechnung für jedes $ P_i $ durchführen.
C ++ - Code
abc141e.cc
//Zur Compileroptimierung
#pragma GCC optimize("O3")
//Einschließen(Alphabetischer Reihenfolge)
#include<algorithm>//sort,Halbierungssuche,Eine solche
#include<bitset>//Bit mit fester Länge gesetzt
#include<cmath>//pow,Protokoll usw.
#include<complex>//Komplexe Zahl
#include<deque>//Double-Ended-Zugriffswarteschlange
#include<functional>//größer sortieren
#include<iomanip>//setprecision(Gleitkomma-Ausgabefehler)
#include<iostream>//Input-Output
#include<iterator>//Betrieb einstellen(Produktset,Summensatz,Differenzsatz etc.)
#include<map>//map(Wörterbuch)
#include<numeric>//iota(Generierung einer Ganzzahlzeichenfolge),gcd und lcm(c++17)
#include<queue>//Warteschlange
#include<set>//einstellen
#include<stack>//Stapel
#include<string>//String
#include<unordered_map>//Karte mit Iterator, aber ohne Ordnung
#include<unordered_set>//Es gibt einen Iterator, aber die Reihenfolge wird nicht festgelegt
#include<utility>//pair
#include<vector>//Array mit variabler Länge
using namespace std;
typedef long long ll;
//Makro
//für Schleifenbeziehung
//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.
#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--)
//x ist ein Container wie ein Vektor
#define ALL(x) x.begin(),x.end() //Ich möchte Argumente wie sort weglassen
#define SIZE(x) ll(x.size()) //Größe zu Größe_Wechseln Sie von t nach ll
//Konstante
#define INF 1000000000000 //10^12:Extrem großer Wert,∞
#define MOD 1000000007 //10^9+7:Gemeinsames Recht
#define MAXR 100000 //10^5:Maximale Reichweite des Arrays(Wird für die Aufzählung von Primzahlen usw. verwendet.)
//Abkürzung
#define PB push_back //In Vektor einfügen
#define MP make_pair //Paarkonstruktor
#define F first //Das erste Element des Paares
#define S second //Das zweite Element des Paares
#define Umap unordered_map
#define Uset unordered_set
//.lower_gebunden ist O.(√n)
signed main(){
//Code zur Beschleunigung der Eingabe
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n;cin>>n;
vector<ll> p(n);vector<ll> p_num(n);
REP(i,n){cin>>p[i];p[i]--;p_num[p[i]]=i;}
//Es ist eine gute Idee, eine Wache zu haben
//p[i]Speichern Sie eine größere Anzahl von Indizes
set<ll> s;
s.insert(-2);s.insert(-1);
s.insert(n);s.insert(n+1);
ll ans=0;
//Prozess aus großer Anzahl
REPD(i,n){
//Index auf S.
ll j=p_num[i];
ll l1,l2,r1,r2;
r1=*(s.upper_bound(j));
r2=*(++s.upper_bound(j));
l1=*(--s.lower_bound(j));
l2=*(--(--s.lower_bound(j)));
//cout<<l2<<" "<<l1<<" "<<r1<<" "<<r2<<endl;
if(l1>-1)ans+=((i+1)*(l1-l2)*(r1-j));
if(r1<n)ans+=((i+1)*(r2-r1)*(j-l1));
s.insert(j);
}
cout<<ans<<endl;
}
abc141e.cc
//Zur Compileroptimierung
#pragma GCC optimize("O3")
//Einschließen(Alphabetischer Reihenfolge)
#include<algorithm>//sort,Halbierungssuche,Eine solche
#include<bitset>//Bit mit fester Länge gesetzt
#include<cmath>//pow,Protokoll usw.
#include<complex>//Komplexe Zahl
#include<deque>//Double-Ended-Zugriffswarteschlange
#include<functional>//größer sortieren
#include<iomanip>//setprecision(Gleitkomma-Ausgabefehler)
#include<iostream>//Input-Output
#include<iterator>//Betrieb einstellen(Produktset,Summensatz,Differenzsatz etc.)
#include<map>//map(Wörterbuch)
#include<numeric>//iota(Generierung einer Ganzzahlzeichenfolge),gcd und lcm(c++17)
#include<queue>//Warteschlange
#include<set>//einstellen
#include<stack>//Stapel
#include<string>//String
#include<unordered_map>//Karte mit Iterator, aber ohne Ordnung
#include<unordered_set>//Es gibt einen Iterator, aber die Reihenfolge wird nicht festgelegt
#include<utility>//pair
#include<vector>//Array mit variabler Länge
using namespace std;
typedef long long ll;
//Makro
//für Schleifenbeziehung
//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.
#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--)
//x ist ein Container wie ein Vektor
#define ALL(x) x.begin(),x.end() //Ich möchte Argumente wie sort weglassen
#define SIZE(x) ll(x.size()) //Größe zu Größe_Wechseln Sie von t nach ll
//Konstante
#define INF 1000000000000 //10^12:Extrem großer Wert,∞
#define MOD 1000000007 //10^9+7:Gemeinsames Recht
#define MAXR 100000 //10^5:Maximale Reichweite des Arrays(Wird für die Aufzählung von Primzahlen usw. verwendet.)
//Abkürzung
#define PB push_back //In Vektor einfügen
#define MP make_pair //Paarkonstruktor
#define F first //Das erste Element des Paares
#define S second //Das zweite Element des Paares
#define Umap unordered_map
#define Uset unordered_set
//.lower_gebunden ist O.(√n)
signed main(){
//Code zur Beschleunigung der Eingabe
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n;cin>>n;
vector<ll> p(n);vector<ll> p_num(n);
REP(i,n){cin>>p[i];p[i]--;p_num[p[i]]=i;}
//Es ist eine gute Idee, eine Wache zu haben
//p[i]Speichern Sie eine größere Anzahl von Indizes
set<ll> s;
s.insert(-2);s.insert(-1);
s.insert(n);s.insert(n+1);
ll ans=0;
//Prozess aus großer Anzahl
REPD(i,n){
//Index auf S.
ll j=p_num[i];
ll l1,l2,r1,r2;
r1=*(s.upper_bound(j));
r2=*(++s.upper_bound(j));
l1=*(--s.lower_bound(j));
l2=*(--(--s.lower_bound(j)));
//cout<<l2<<" "<<l1<<" "<<r1<<" "<<r2<<endl;
if(l1>-1)ans+=((i+1)*(l1-l2)*(r1-j));
if(r1<n)ans+=((i+1)*(r2-r1)*(j-l1));
s.insert(j);
}
cout<<ans<<endl;
}
ABC146-D Coloring Edges on Tree
Zeit genommen
Etwa 25 Minuten
Erwägung
Es wäre großartig, wenn die Probleme in der ersten Hälfte von Grün und Hellblau in etwa 10 Minuten gelöst werden könnten, ohne einen Fehler in der Richtlinie zu machen ...
Für jeden Scheitelpunkt können Sie alle Seiten mit diesem Scheitelpunkt als unterschiedliche Farben malen. Wenn Sie also das Malen mit allen Farben außer der Seite wiederholen, die unmittelbar zuvor mit BFS oder DFS passiert wurde, malen Sie alle Seiten. Ich kann. Ich habe mich jedoch für eine andere Lösung entschieden, weil ich dachte, es wäre mühsam, das unmittelbar zuvor ergangene Urteil umzusetzen (obwohl es sich doch nicht von DFS oder BFS unterscheidet).
Speichern Sie jede Seite, die sich von jedem Scheitelpunkt aus erstreckt, und malen Sie in der Reihenfolge von der Seite, die mit dem Punkt mit der kleinsten Zahl verbunden ist. Wenn zu diesem Zeitpunkt jede Seite bereits gestrichen ist, kann diese Farbe nicht gemalt werden. Speichern Sie daher die Nummer dieser Farbe in "cand1". Im Gegenteil, ich möchte die Seite malen, die noch nicht gemalt wurde, also speichere sie in cand2. Darunter können Sie auf alle Elemente von cand2 zugreifen und jede Seite in der Reihenfolge von der Farbe mit der kleinsten Zahl nur die Farben malen, die nicht in cand1 enthalten sind.
Python-Code
abc146d.py
n=int(input())
paths=[[] for i in range(n)]
colors=[0]*(n-1)
for i in range(n-1):
a,b=map(int,input().split())
paths[a-1].append(i)
paths[b-1].append(i)
m=0
for i in range(n):
m=max(m,len(paths[i]))
print(m)
for i in range(n):
cand1,cand2=set(),[]
for j in paths[i]:
if colors[j]!=0:
cand1.add(colors[j])
else:
cand2.append(j)
now=1
for j in cand2:
while now in cand1:
now+=1
colors[j]=now
now+=1
for i in range(n-1):
print(colors[i])
abc146d.py
n=int(input())
paths=[[] for i in range(n)]
colors=[0]*(n-1)
for i in range(n-1):
a,b=map(int,input().split())
paths[a-1].append(i)
paths[b-1].append(i)
m=0
for i in range(n):
m=max(m,len(paths[i]))
print(m)
for i in range(n):
cand1,cand2=set(),[]
for j in paths[i]:
if colors[j]!=0:
cand1.add(colors[j])
else:
cand2.append(j)
now=1
for j in cand2:
while now in cand1:
now+=1
colors[j]=now
now+=1
for i in range(n-1):
print(colors[i])
Recommended Posts