[PYTHON] Codeforces Round # 679 (Div. 2) Review (10/25)
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Dieses Mal konnte ich meine Konzentration während des Wettbewerbs richtig aufrechterhalten, daher bin ich erleichtert.
Der Grund für den Sieg ist, dass ich eine ziemlich schwere Implementierung im C-Problem bestehen konnte. Heute konnte ich an meine Gedanken glauben, was das Debuggen erleichterte.
Darüber hinaus habe ich das Gefühl, dass sich die Genauigkeit verbessert hat, indem ab diesem Zeitpunkt in jedem Schritt ein Druck-Debugging durchgeführt wurde. Ich werde es beim nächsten Wettbewerb versuchen.
Problem A
** Kann immer ** halten, also ** benachbarte Zahlen ** auswählen und $ a \ _i \ mal b \ _i + a \ _ {i + 1} \ mal b \ _ {i + 1 auswählen Um} = 0 $ zu setzen, setze $ (b \ _i, b \ _ {i + 1}) = (-a \ _ {i + 1}, a \ _i) $. Zu diesem Zeitpunkt füllt jedes $ b \ _ {i} $ den absoluten Wertebereich und wird niemals 0. Da die Länge der Sequenz gerade ist, können Sie auch alle benachbarten Zahlen koppeln.
A.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
b=[0]*n
for i in range(n//2):
b[2*i]=-a[2*i+1]
b[2*i+1]=a[2*i]
print(" ".join(map(str,b)))
B-Problem
Ich habe es falsch verstanden und die Zeilen- und Spaltenbedingungen umgekehrt. Es war gefährlich ...
Die erste ist die Information für jede Zeile (die Reihenfolge der Zeilen ist nicht immer korrekt) und die zweite ist die Information für jede Spalte (die Reihenfolge der Spalten ist nicht immer korrekt). Außerdem werden alle Elemente der Matrix als unterschiedlich angegeben.
Zu diesem Zeitpunkt wird die ** Spaltennummer jedes Elements aus dem ersten ** eindeutig bestimmt, und die ** Zeilennummer jedes Elements wird aus dem zweiten ** eindeutig bestimmt. Durch Erstellen eines Wörterbuchs in Form von ** (Elementwert): (Zeilennummer, Spaltennummer) ** können daher die Zeilennummer und die Spaltennummer jedes Elements bekannt sein, und die ursprüngliche Matrix kann aus diesen Informationen wiederhergestellt werden. Das ist gut.
B.py
import sys
input=sys.stdin.readline
for _ in range(int(input())):
n,m=map(int,input().split())
ans=[[0]*m for i in range(n)]
d=dict()
for i in range(n):
l1=list(map(int,input().split()))
for j in range(m):
d[l1[j]]=[-1,j]
for i in range(m):
l2=list(map(int,input().split()))
for j in range(n):
d[l2[j]][0]=j
for i in d:
ans[d[i][0]][d[i][1]]=i
for i in range(n):
print(" ".join(map(str,ans[i])))
C-Problem
Es war ein wenig mühsam für meine Implementierung und Überlegung, aber ich bin froh, dass ich es vollständig in Betracht ziehen kann. Übrigens sind die Range Minimum Queries, die ich neulich gelöst habe, ein ähnliches Thema.
Überlegen Sie, ob Sie den minimalen Wert der Differenz zwischen dem minimalen und dem maximalen Wert von $ j $ ermitteln möchten, wenn $ b \ _k = a \ _i + j $ für jedes $ k $ festgelegt ist, wobei $ i $ entsprechend festgelegt ist. Ich werde. Außerdem gibt es für jeden $ n $ Sound bis zu 6 Kandidaten für $ j $. Berücksichtigen Sie auf dieser Grundlage den Minimalwert der Differenz zwischen dem Minimalwert und dem Maximalwert. Da jedoch ** der Freiheitsgrad hoch ist, sollten Sie den Minimalwert ** (** Fixieren der Variablen! **) festlegen. Zu diesem Zeitpunkt gibt es maximal $ 6n $ Kandidaten für den Mindestwert, aber wenn der Mindestwert auf $ x $ festgelegt ist, ist das Minimum $ j $ über $ x $ ein Seg-Baum für jedes $ b \ _k $. Wenn Sie es mit ** speichern, können Sie sehen, dass der maximale Wert darin mit hoher Geschwindigkeit erhalten werden kann, ohne $ O (n) $ ** auszugeben. Es ist auch notwendig, $ b \ _k $ zu aktualisieren, das im Seg-Baum gespeichert ist, um es über $ x $ zu bringen, aber ** die Anzahl der Aktualisierungen beträgt ungefähr $ 6n $ unter Berücksichtigung des Betrags der Amortisationsberechnung **. Das können Sie erwarten. Daher werden wir im Folgenden sowohl die Implementierung als auch die Lösungsmethode betrachten.
Bereiten Sie zuerst die folgenden Variablen usw. vor und führen Sie dann die Betrachtungsoperation aus.
$ a [i]: = $ (Wert von $ i $ th string) $ b [i]: = $ ($ i $ th Notenwert) $ ind [i]: = $ ($ b [i] -a [j] $ Wert gesetzt (aufsteigende Reihenfolge), wenn die $ i $ -te Note auf der $ j $ -ten Saite gespielt wird) $ cand: = $ (Mindestwert: (Karte gespeichert mit Index-Array von Sound $ i $, das zu diesem Wert wird)) $ itr [i]: = $ (** Iterator ** des Mindestwerts von $ ind [i] $ beim Spielen der $ i $ -ten Note) $ maxseg [i]: = $ (Wert von $ itr [i] $) (** einen Punkt aktualisieren, Segmentbaum des maximalen Abschnittswerts **) $ ans: = $ (Lösung)
$ a, b $ wird nur durch Eingabe empfangen, $ ind $ ist $ b [i] -a [j] > 0 $ besteht aus einem beliebigen $ i, j $. Drehen Sie also die Schleife zweimal und fügen Sie sie ein. $ cand $ setzt nur ein Element von $ ind $. Außerdem sollte $ itr [i] $ per Definition $ ind [i] $ $ begin () $ sein. Zu diesem Zeitpunkt wird $ maxseg [i] $ auch auf den Wert des Elements gesetzt, auf das der Iterator von $ ind [i] $ zeigt. Dann wird $ ans $ als (Maximalwert) - (Minimalwert) des Elements initialisiert, auf das $ itr $ zeigt.
Von hier aus sollten Sie das Minimum $ y $ über $ x $ und den Mindestwert von $ y-x $ ermitteln, wobei der Mindestwert $ x $ ist. ** $ x $ berücksichtigt in aufsteigender Reihenfolge, was in $ cand $ enthalten ist **. Zunächst wird bei der Initialisierung berücksichtigt, wann $ x $ der Mindestwert aller Elemente ist. Wenn Sie den Mindestwert von $ x $ von hier aus erhöhen, müssen Sie den Wert löschen, der kleiner als dieser $ x $ ist. Alles, was Sie tun müssen, ist, $ itr, maxseg $ für das in $ cand $ enthaltene Element $ x $ zu aktualisieren, von der kleineren Seite aus gesehen. Zu diesem Zeitpunkt kann der in $ cand [x] $ enthaltene Index $ i $ in $ itr [i] $ \ + \ + geändert werden. Außerdem wird der aktualisierte Wert von $ itr [i] $ auf $ maxseg $ aktualisiert. Wenn ** $ itr [i] $ zu $ end () $ wird, bedeutet dies, dass es keine Zeichenfolge gibt, die die $ i $ -te Note ** spielen kann, und $ ans $ an diesem Punkt ausgegeben und beendet wird. Machen. Beim Aktualisieren zum Löschen eines bestimmten $ x $ ist der minimale Wert das nächstkleinere Element nach diesem $ x $, und der maximale Wert ist der maximale Wert des von $ maxseg $ verwalteten Werts, und dieser Unterschied und ans sind gering. Aktualisiere ans selbst.
Sie finden die Lösung $ ans $, indem Sie das obige Update beenden.
C.cc
//Debug-Optionen:-fsanitize=undefined,address
//Compileroptimierung
#pragma GCC optimize("Ofast")
//Einschließen usw.
#include<bits/stdc++.h>
using namespace std;
typedef int 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 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
/* RMQ：[0,n-1]Struktur, die den Mindestwert für jeden Abschnitt verwaltet
update(i,x):Das i-te Element wurde auf x aktualisiert. Ö(log(n))
query(a,b): [a,b)Holen Sie sich das kleinste Element in. Ö(log(n))
*/
template <typename T>
struct RMQ {
const T INF = -1;
int n; //Anzahl der Blätter
vector<T> dat; //Voll gegabelte Anordnung
RMQ(int n_) : n(), dat(n_ * 4, INF) { //Die Anzahl der Blätter beträgt 2^Form von x
int x = 1;
while (n_ > x) {
x *= 2;
}
n = x;
}
void update(int i, T x) {
i += n - 1;
dat[i] = x;
while (i > 0) {
i = (i - 1) / 2; // parent
dat[i] = max(dat[i * 2 + 1], dat[i * 2 + 2]);
}
}
// the minimum element of [a,b)
T query(int a, int b) { return query_sub(a, b, 0, 0, n); }
T query_sub(int a, int b, int k, int l, int r) {
if (r <= a || b <= l) {
return INF;
} else if (a <= l && r <= b) {
return dat[k];
} else {
T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
return max(vl, vr);
}
}
};
signed main(){
//Ausgabespezifikation der Anzahl der Bruchstellen
//cout<<fixed<<setprecision(10);
//Code zur Beschleunigung der Eingabe
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
vector<ll> a(6);REP(i,6)cin>>a[i];
ll n;cin>>n;
RMQ<ll> maxseg(n);
vector<ll> b(n);REP(i,n)cin>>b[i];
vector<set<ll>> ind(n);
REP(i,n){
REP(j,6){
ind[i].insert(b[i]-a[j]);
}
//cout<<SIZE(ind[i])<<endl;
}
map<ll,vector<ll>> cand;
REP(i,n){
FORA(j,ind[i]){
cand[j].PB(i);
}
}
//cout<<1<<endl;
vector<set<ll>::iterator> itr(n);
ll ma=-1;
REP(i,n){
itr[i]=ind[i].begin();
maxseg.update(i,*itr[i]);
ma=max(ma,*itr[i]);
}
ll ans=ma-cand.begin()->F;
for(auto i=cand.begin();i!=cand.end();i++){
FORA(j,i->S){
itr[j]++;
if(itr[j]==ind[j].end()){
cout<<ans<<endl;
return 0;
}
maxseg.update(j,*itr[j]);
}
ans=min(ans,maxseg.query(0,n)-(++i)->F);
i--;
}
cout<<ans<<endl;
}
D Problem
Ich dachte, es wäre besser, es gierig zu packen, um die Bedingungen zu erfüllen, aber wenn es von vorne ist, ist es schwierig, die Bedingungen festzulegen. Warum also nicht von hinten denken? Ich dachte (** Denk in umgekehrter Reihenfolge! **).
Wenn es eine Reihe von Zahlen gibt, die von hinten betrachtet in die Position gepackt werden müssen (eine Reihe von + ?? Zahlen), ** ordnen Sie die Position in der Reihenfolge der kleinsten Zahl ** zu. Ist das Beste. Jede ** - Position wird durch diese Methode eindeutig bestimmt **. Wenn die Position von-nicht bestimmt werden kann (wenn die Größe des Satzes 0 ist), wird NO ausgegeben, und wenn sogar eins + ?? das Subjekt nach dem Bestimmen der Position von- nicht erfüllt, wird NO ausgegeben. Machen. Wenn diese Urteile geklärt sind, sollte JA ausgegeben werden. (Ich habe es nicht bewiesen, aber ich denke, es ist vernünftig genug)
D.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(){
//Ausgabespezifikation der Anzahl der Bruchstellen
//cout<<fixed<<setprecision(10);
//Code zur Beschleunigung der Eingabe
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n;cin>>n;
vector<ll> que(2*n,0);
REP(i,2*n){
string s;cin>>s;
if(s=="-"){
ll x;cin>>x;
que[i]=x;
}
}
set<ll> cand;
vector<ll> ans(n);
ll ind=n-1;
REPD(i,2*n){
if(que[i]!=0){
cand.insert(que[i]);
}else{
if(SIZE(cand)==0){
cout<<"NO"<<endl;
return 0;
}else{
ll y=*cand.begin();
ans[ind]=y;
ind--;
cand.erase(cand.begin());
}
}
}
ind++;
REP(i,2*n){
if(que[i]==0){
cand.insert(ans[ind]);
ind++;
}else{
ll y=*cand.begin();
if(que[i]!=y){
cout<<"NO"<<endl;
return 0;
}
cand.erase(cand.begin());
}
}
cout<<"YES"<<endl;
REP(i,n){
if(i==n-1)cout<<ans[i]<<endl;
else cout<<ans[i]<<" ";
}
}
E Problem
Ich werde diesmal überspringen.
Recommended Posts