Angesichts der jüngsten Ergebnisse der unglücklichen Wettkampfprofis habe ich beschlossen, die Hingabe wieder zu erhöhen. Ich möchte mich der zeitlichen Lösung von Problemen widmen, die über das Wasser hinausgehen.
Zur Zeit plane ich, das Problem der Wasserdifferenzierung jeden Tag um 1AC oder mehr zu lösen, bis alle S-Semesterklassen beendet sind. Ich werde mein Bestes geben.
Etwa anderthalb Stunden (ich werde die Zeit von jetzt an messen)
Es ist $ O (NQ) $, wenn jede Person entscheidet, welcher Straßenbau einmal geschlossen wird. ** Es scheint, dass dies effizient durchgeführt werden kann, wenn Sie darüber nachdenken, welche Person jeder Straßenbau schließen wird ** ..
Hier schließt der i-te Straßenbau Personen, die durch die Koordinate $ X_i $ zwischen $ \ [S_i, T_i-1 ] $ gehen, aber die Koordinaten können zeitlich zusammengefasst werden. Mit anderen Worten, das Gehen mit Geschwindigkeit 1 kann als schließende Personen umformuliert werden, die zwischen $ \ [S_i-X_i, T_i-X_i-1 ] $ wechseln.
Die Person, die zum vorherigen Zeitpunkt abreist, kann nach der Dichotomie durchsucht werden. Daher werden wir in Betracht ziehen, den durch die Dichotomie $ N $ erhaltenen Abschnitt zu aktualisieren. Es ist jedoch erforderlich, den Abschnitt effizient zu aktualisieren. Es gibt einen Verzögerungssegmentbaum als Datenstruktur, der den Abschnitt effizient aktualisiert. Um diejenige mit den engsten Koordinaten in der für den Verkehr gesperrten Straßenkonstruktion zu finden, ** sollte die Aktualisierung in der Reihenfolge derjenigen mit den am weitesten entfernten Koordinaten ** erfolgen. Ich dachte. Ich habe diese Lösung jedoch vermieden, da ich noch nie einen verzögerten Segmentbaum verwendet hatte und Angst hatte, ihn fehlerhaft zu machen.
Hier ** ist es wichtig, bei der Abschnittsaktualisierung nur beide Enden zu speichern und am Ende kumulativ zu denken ** (dasselbe gilt für die imos-Methode und den verzögerten Segmentbaum). Daher ** ans_sectl [i]: deque **, das den Index des Abschnitts speichert, in dem sich die i-te Person am linken Ende befindet, und ** ans_sectr [i]: der Index des Abschnitts, in dem sich die i-te Person am rechten Ende befindet. Bereiten Sie eine Deque ** zum Speichern vor. (Ich habe $ \ gewählt, weil $ deque, weil es mit $ O (1) $ abgerufen werden kann.)
Obwohl es nachgedruckt wird, wird ** diejenige mit den engsten Koordinaten im zu schließenden Straßenbau tatsächlich geschlossen **. Wenn Sie also zum ersten Mal $ S_i, T_i, X_i $ erhalten, wird der Wert von $ X_i $ in aufsteigender Reihenfolge verwendet. Sortieren Sie es (xst). … ①
Darunter ein Container (ans), der ** den Index des Abschnitts speichert, der die Abfahrtszeit jeder Person enthält ** (= Index des Straßenbaus, bei dem jede Person für den Verkehr gesperrt sein kann) Wenn Sie "Einfügen" vorbereiten und wiederholen, wenn es in "ans_sectl" enthalten ist, und "Löschen", wenn es in "ans_sectr" enthalten ist, in der Reihenfolge der Person mit der kleinsten Nummer, verhält sich "ans" so schnell, wie Sie möchten. Zu
Darüber hinaus wird der Index des in ans enthaltenen Abschnitts in aufsteigender Reihenfolge gespeichert, wenn es sich um eine ** C ++ - Karte oder -Satz ** handelt, und sollte erhalten werden, da der Straßenbau die engsten in ans enthaltenen Koordinaten aufweist, also der Beginn des Containers. Sie müssen lediglich den Abstand des geschlossenen Punkts ausgeben, der dem Element von ($ \ weil $ ①) entspricht.
Wenn Sie in einem geschlossenen Abschnitt eine Person finden, deren Abfahrtszeit in $ \ [S_i-X_i, T_i-X_i-1 ] $ enthalten ist, lautet das linke Ende L = (lower_bound (ALL (d), sx) - Sie müssen das richtige Ende mit R = (Upper_bound (ALL (d), tx-1) -d.begin ()) - 1 mit d.begin () finden, aber $ \ [S_i-X_i, T_i Wenn es niemanden gibt, dessen Abfahrtszeit in -X_i-1 ] $ enthalten ist, dann ist $ L> R $, daher müssen Sie diesen Fall ausschließen.
abc128e.cc
#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
//Die Verarbeitung am Ende war schlampig, diese Art der losen Implementierung ist nutzlos
signed main(){
//Code zur Beschleunigung der Eingabe
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n,q;cin>>n>>q;
vector<vector<ll>> xst(n);
REP(i,n){
ll s,t,x;cin>>s>>t>>x;
xst[i]={x,s,t};
}
sort(ALL(xst));
vector<ll> d(q);
REP(i,q)cin>>d[i];
vector<deque<ll>> ans_sectl(q);
vector<deque<ll>> ans_sectr(q);
REP(i,n){
ll s,t,x;x=xst[i][0];s=xst[i][1];t=xst[i][2];
ll L=(lower_bound(ALL(d),s-x)-d.begin());
ll R=(upper_bound(ALL(d),t-x-1)-d.begin())-1;
//lower,Sei vorsichtig oben
//2RE
if(L<=R){ans_sectl[L].PB(i);ans_sectr[R].PB(i);}
//cout << L << " " << R << endl;
}
map<ll,ll> ans;
REP(i,q){
ll sl=SIZE(ans_sectl[i]);
ll sr=SIZE(ans_sectr[i]);
REP(_,sl){
ans[*(ans_sectl[i].begin())]+=1;
ans_sectl[i].pop_front();
}
if(ans.empty()){
cout<<-1<<"\n";
}else{
cout<<xst[ans.begin()->F][0]<<"\n";
}
REP(_,sr){
ans[*(ans_sectr[i].begin())]-=1;
if(ans[*(ans_sectr[i].begin())]==0)ans.erase(*(ans_sectr[i].begin()));
ans_sectr[i].pop_front();
}
}
}
abc128e_set.cc
#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
//Die Verarbeitung am Ende war schlampig, diese Art der losen Implementierung ist nutzlos
signed main(){
//Code zur Beschleunigung der Eingabe
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n,q;cin>>n>>q;
vector<vector<ll>> xst(n);
REP(i,n){
ll s,t,x;cin>>s>>t>>x;
xst[i]={x,s,t};
}
sort(ALL(xst));
vector<ll> d(q);
REP(i,q)cin>>d[i];
vector<deque<ll>> ans_sectl(q);
vector<deque<ll>> ans_sectr(q);
REP(i,n){
ll s,t,x;x=xst[i][0];s=xst[i][1];t=xst[i][2];
ll L=(lower_bound(ALL(d),s-x)-d.begin());
ll R=(upper_bound(ALL(d),t-x-1)-d.begin())-1;
//lower,Sei vorsichtig oben
//2RE
if(L<=R){ans_sectl[L].PB(i);ans_sectr[R].PB(i);}
//cout << L << " " << R << endl;
}
set<ll> ans;
REP(i,q){
ll sl=SIZE(ans_sectl[i]);
ll sr=SIZE(ans_sectr[i]);
REP(_,sl){
ans.insert(*(ans_sectl[i].begin()));
ans_sectl[i].pop_front();
}
if(ans.empty()){
cout<<-1<<"\n";
}else{
cout<<xst[*ans.begin()][0]<<"\n";
}
REP(_,sr){
ans.erase(*(ans_sectr[i].begin()));
ans_sectr[i].pop_front();
}
}
}
Etwa 1 Stunde (ich werde die Zeit von jetzt an messen)
Ich löste ein Problem, das schwieriger wurde, indem ich "bis zu K-mal" ** falsch interpretierte ** als "nur K-mal". Es ist nicht gut ...
Erstens sind $ N $ und $ K $ nicht sehr groß, daher müssen Sie verstehen, dass der Rechenaufwand einen gewissen Spielraum zu haben scheint.
Hier versuchen wir zuerst die Methode, gierig von den äußeren hochwertigen Juwelen zu nehmen, lehnen sie jedoch ab, weil ** möglicherweise hochwertige Juwelen darin sind **. Wenn Sie den Vorgang zum Herausnehmen auf derselben Seite nach dem ** Verpackungsvorgang ausführen, sind die beiden Vorgänge nutzlos , sodass Sie sehen können, dass Sie den Verpackungsvorgang nach dem Ausführen des Entnahmevorgangs ausführen sollten ( Vorgang) Tauschen Sie aus, um das Denken zu erleichtern! **).
Wenn Sie hier festlegen, wie oft Sie herausnehmen möchten, wird auch festgelegt, wie oft verpackt werden soll. Daher habe ich mich entschieden, wie oft $ i $ herausgenommen werden soll (die Richtlinie begann hier aufgrund der ersten ** Fehlinterpretation ** zu verirren, aber ** Ich musste mich beruhigen und die Problemstellung lesen **.). Wenn $ i $ 0 ist, kann die Packoperation nicht ausgeführt werden und der maximale Gesamtwert der Juwelen nach der Operation ist 0, sodass $ i $ von 1 bis $ min (k, n) $ berücksichtigt wird. Auch wenn die Anzahl der Operationen, die ausgeführt werden müssen, $ i $ beträgt, dachte ich, ich würde die Juwelen mit hohem Wert von außen gierig in Ordnung bringen, aber ** es kann Juwelen mit hohem Wert von innen geben **, also diese Richtlinie Wird abgelehnt.
Daher habe ich zusätzlich zu der Tatsache, dass noch Raum für Berechnungen vorhanden ist, alle $ m $ ausprobiert, wenn ich $ m $ von links und $ im $ von rechts extrahiert habe ($ m = 0 $ ~ $ i). Schneiden Sie die mit $ herausgenommene und speichern Sie sie im Array $ s $). Da es nur erforderlich ist, die extrahierten Elemente in der Reihenfolge mit dem niedrigsten Wert ** zu verpacken (der Wert ist jedoch 0 oder weniger), sortieren Sie $ s $ und packen Sie bis zu $ min (ki, i) $ mal. Das ist gut. Es ist auch ein Kandidat für den Maximalwert, dass die Summe von $ s $ berechnet werden kann, vorausgesetzt, der verpackte Artikel ist 0.
Mit dem oben Gesagten beträgt der Rechenaufwand $ O (X ^ 3 \ log {X}) $ mit $ X = min (N, K) $, und es besteht keine Notwendigkeit mehr zu beschleunigen. Implementieren Sie ihn daher wie folgt. ..
abc128d.py
import math
from collections import deque
n,k=map(int,input().split())
v=list(map(int,input().split()))
#Es war bis zu k mal falsch verstanden
ans=0
for i in range(1,min(k,n)+1):
#Wohin soll ich gehen?(Ist es nicht immer der größere?)
for m in range(i+1):
s=v[:m]+v[n-(i-m):]
s.sort()
#Versuchen Sie nicht, mehr zu packen, als Sie genommen haben!
#Verbleibende k-ich mal
for j in range(i,min(k,2*i)):#Wenn Sie nicht mehr packen können
#Umschreiben, wenn weniger als 0
if s[j-i]<0:s[j-i]=0
#Maximum des herausgenommenen(0, um zurückzukehren)
ans=max(ans,sum(s))
#Verbleibende k-j mal(Ich habe zum Zeitpunkt der Pause nicht j gemacht)
#Wiederholen Sie von hier aus das Ein- und Aussteigen(Wenn es gerade ist, ist es so wie es ist?)
#Sie brauchen es nicht einmal, Sie müssen nicht k-mal verbrauchen
#print(sum(s))
print(ans)
Diesmal hatte ich nicht viel Zeit, aber ich habe es in ungefähr einer Stunde gelöst.
Von den beiden Bedingungen habe ich $ a + b = a \ oplus b $ betrachtet, was leicht zu überlegen ist. Dies kann mit ein wenig Nachdenken verstanden werden, aber $ XOR $ ist ** $ \ leftrightarrow $ **, wobei jedes Bit unabhängig berechnet werden kann ** Es gibt keinen Übertrag in der binären Berechnung **, daher sind a und b optional Sie können sehen, dass es nur drei Sätze von (0,1), (1,0), (0,0) für das Bit von gibt. … ①
Unter dieser Bedingung wird die erste Bedingung, $ a + b \ leqq L $, verarbeitet, aber hier müssen wir denken, dass "wenn die erste Ziffer 0 oder 1 ist, wenn die zweite Ziffer 0 oder 1 ist, ..." Ich dachte schlampig: "Wenn es unter eine Ziffer fällt, ist jede Ziffer danach in Ordnung", aber es ist lange her, dass die Idee der ** Ziffer DP ** auf Probleme mit solchen Mustern zutrifft. Ich erinnerte mich danach ...
ARMERIAs Artikel und [Kenchons Artikel](https://drken1215.hatenablog.com/entry/2019/ Wenn Sie sich auf 02/04/013700 beziehen, kann verallgemeinert werden, dass die Ziffer DP verwendet werden kann, wenn die folgenden zwei Eigenschaften vorhanden sind.
1: ** Ich möchte die Anzahl der Werte (Maximal- und Minimalwerte von XX) finden, die XX unterhalb der Obergrenze $ L $ ** erfüllen (und $ L $ ist groß). 2: Es gibt eine Bedingung bezüglich der Ziffern
Darunter kann der Zustand von DP wie folgt bestimmt werden. $ DP [i] [kleiner]: = $ Ein Wert bei der Bestimmung von oben bis zur Ziffer $ i $ (Wenn jedoch ** $ kleiner = 0 $ ist, gibt es Ziffern, die kleiner als $ L $ bis zur Ziffer $ i $ sind, und wenn $ kleiner = 1 $ ist, sind alle Ziffern bis zur i-ten Ziffer $ L $. Es kann gesagt werden, dass es dasselbe ist wie **.)
Außerdem sind ** DP-Übergänge jedes Mal wie folgt **. ・ Von $ DP [i] [0] $ kann nur $ DP [i + 1] [0] $ überführt und eine beliebige $ i $ -Ziffer ausgewählt werden. ・ Beim Übergang von $ DP [i] [1] $ zu $ DP [i + 1] [0] $ kann die Ziffer $ i $ aus allen Zahlen ausgewählt werden, die kleiner als die Ziffer $ i $ von $ L $ sind. es kann.
Wenn Sie die Bewegung der Ziffer DP mit den obigen Angaben bestätigen, ist dieses Problem einfach und Sie können den Status der DP wie folgt bestimmen.
$ DP [i] [kleiner]: = $ Anzahl der Paare von $ (a, b) $ bei der Bestimmung von oben nach $ i $ (Wenn jedoch $ kleiner $ 0 ist, existieren Bits kleiner als $ L $ in $ a + b $ von oben bis $ i $ Bit, und wenn $ kleiner $ 1 ist, sind $ i $ Bits von oben Alle Bits bis zum Auge sind gleich $ L $)
Darüber hinaus gibt es drei Arten von DP-Übergängen (\ weil $ ① $).
・ $ DP [i + 1] [0] = 3 × DP [i] [0] \ ($ i $ Bit von , da a + b $ 0 oder 1 $ sein kann) $ ・ Wenn die $ i + 1 $ -Ziffer von $ L $ 0 ist $ DP [i + 1] [1] = DP [i] [1] \ (\ weil das $ i $ -Bit von a + b $ nur 0 $ hat) $ ・ Wenn die $ i + 1 $ -Ziffer von $ L $ 1 ist. $ DP [i + 1] [0] = DP [i] [1] \ (\ weil a + b $ i-te Bit $, wenn das $ i $ Bit th 0 ist (a $ und $ b $ i-te Bit $) ) = (0,0)) $ $ DP [i + 1] [1] = 2 * DP [i] [1] \ (\ weil a + b $ $ i $ Bit Wenn das erste 1 ist, $ (a $ und $ b $ i Bit) Auge $) = (0,1), (1,0)) $
Der folgende Code implementiert diesen Übergang. Das Spiel sollte in der Lage sein, sofort eine Ziffern-DP zu entwickeln, also hätte ich es ein bisschen mehr lösen sollen. Es ist beschämend.
abc129e.py
mod=10**9+7
l=input()
bit=[int(i) for i in l]
m=len(bit)
#Ich übertreibe es richtig, aber die Ziffer DP
#Gleich wie der kleinere
dp=[[0,0] for i in range(m)]
dp[0]=[1,2]
for i in range(m-1):
dp[i+1][0]=3*dp[i][0]%mod
if bit[i+1]==0:
dp[i+1][1]+=dp[i][1]
dp[i+1][1]%=mod
else:
dp[i+1][0]+=dp[i][1]
dp[i+1][1]+=(2*dp[i][1])
dp[i+1][0]%=mod
dp[i+1][1]%=mod
print(sum(dp[m-1])%mod)
Recommended Posts