[PYTHON] Educational Codeforces Round 94 Bacha Review (9/3)
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Die Zeit ist auf unbestimmte Zeit geschmolzen, weil ich viel Zeit mit dem B-Problem verbracht habe. Als Reflexion von Problem B habe ich gerade versucht, es analytisch zu lösen. ** Ich denke, dass ich es lösen könnte, wenn ich die gierige Methode intuitiv ausführen würde **, also bereue ich es.
Problem A
Wechseln Sie 01, wenn Sie es zum ersten Mal sehen? Ich dachte das, aber ich fand es problematisch, weil sich die Position verschieben würde. Daher dachte ich, dass es gut wäre, wenn alle Zeichen gleich wären, um nicht von der Position abhängig zu sein **. Zu diesem Zeitpunkt zeigt die fragliche Bedingung, dass ** jede Zeichenfolge $ s [n] $ ** enthält. Wenn Sie also eine Zeichenfolge erstellen, die $ n $ dieses Zeichens verbindet, entspricht das Zeichen, das $ s [n] $ entspricht, einer beliebigen Zeichenfolge. Das ist also die Antwort.
A.py
for _ in range(int(input())):
n=int(input())
s=input()
print(n*s[n-1])
B-Problem
Wie Sie im Eindruck sehen können, kann es durch ** normale Giermethode ** gelöst werden.
Bedenken Sie, dass ** der leichteste der beste ** ist, um so viele wie möglich auszuwählen. Außerdem $ s \ leqq w $ (andernfalls tauschen Sie den Wert aus). Wählen Sie zunächst **, was Sie mitnehmen **, aber je nach Kombination ist es möglicherweise besser, schwere zu speichern, sodass ich nur $ i (0 \ leqq i \ leqq cnts) $ leichtere bin Angenommen, Sie wählen. Zu diesem Zeitpunkt ist es auch erforderlich, $ i \ times s \ leqq p $ zu erfüllen. Darunter können Sie $ min (\ frac {p-i \ times s} {w}, cntw) $ auswählen. Da es leicht ist herauszufinden, wie viele von jedem noch übrig sind, ** sollten Ihre Follower gierig in der Reihenfolge des leichtesten ausgewählt werden **. Daher wird die Anzahl der Dinge, die gestohlen werden können, wenn $ i $ gesetzt ist, mit $ O (1) $ berechnet, und es ist möglich, ein ausreichend schnelles Programm zu schreiben.
B.py
for _ in range(int(input())):
p,f=map(int,input().split())
cnts,cntw=map(int,input().split())
s,w=map(int,input().split())
if s>w:
s,w=w,s
cnts,cntw=cntw,cnts
ans=0
for i in range(cnts+1):
if i*s>p:break
ans_sub=0
nows=cnts-i
ans_sub+=i
#s ist ausgewählt
rest1=p-i*s
#w
noww=cntw-min(rest1//w,cntw)
ans_sub+=min(rest1//w,cntw)
#Nächste Person
#s
ans_sub+=min(f//s,nows)
rest2=f-min(f//s,nows)*s
#w
ans_sub+=min(noww,rest2//w)
ans=max(ans,ans_sub)
print(ans)
C-Problem
Da $ s $ angegeben ist, wird ** $ w $ wiederhergestellt **. Wenn hier $ s \ _i = 1 $ ist, wird $ w $ unter der Bedingung wiederhergestellt, dass entweder $ w \ _ {ix} = 1 $ oder $ w \ _ {i + x} = 1 $ gilt. Da es schwierig ist, gilt $ w $ unter der Bedingung, dass sowohl $ w \ _ {ix} = 1 $ als auch $ w \ _ {i + x} = 1 $ gelten, wenn ** $ s \ _i = 0 $ ** Ich beschloss, wiederherzustellen.
Obwohl ein Teil von $ w $ mit dieser Methode nicht wiederhergestellt wird, wird der gesamte Teil, der nicht wiederhergestellt wurde, um die Bedingung ** $ s \ _i = 1 $ zu erfüllen, auf 1 ** gesetzt. Aus dem oben Gesagten konnten wir $ w $ wiederherstellen, aber wir wissen nicht, ob es tatsächlich von $ w $ in $ s $ transformiert werden kann. Daher müssen wir bestätigen, ob es am Ende transformiert werden kann.
C.py
for _ in range(int(input())):
s=list(map(int,input()))
x=int(input())
n=len(s)
w=[1]*n
for i in range(n):
if s[i]==0:
if i-x>=0:
w[i-x]=0
if i+x<n:
w[i+x]=0
t=[1]*n
for i in range(n):
g=0
if i-x>=0:
if w[i-x]==1:
g+=1
if i+x<n:
if w[i+x]==1:
g+=1
if g>0:
t[i]=1
else:
t[i]=0
if s==t:
print("".join(map(str,w)))
else:
print(-1)
D Problem
Ich wurde ungeduldig mit MLE, aber ich war erleichtert, es rechtzeitig zu lösen. ** Konvertierte pair <ll, ll> in ll und änderte ll in int **.
Ich hatte das Gefühl, dass dieses Problem nicht so schwer zu berücksichtigen und ein wenig mühsam umzusetzen war.
Suchen Sie nach $ i, j, k, l $, so dass $ a \ _i = a \ _k $ und $ a \ _j = a \ _l $ unter $ i <j <k <l $ liegen. Zu diesem Zeitpunkt bemerkte ich, dass ** $ (a \ _ i, a \ _ j) = (a \ _ k, a \ _l) $ gilt **. Da es höchstens 3000 $ n $ gibt, können Sie auch alle $ _ {3000} C_2 $ -Paare generieren. Das gleiche Set wird auch per Karte zusammengestellt. Mit anderen Worten, nehmen wir an, dass $ m $ ein Kartenobjekt ist, der Schlüssel ein Paar von zwei Elementen ist und der Wert ein Vektor ist und das Indexpaar, das die beiden Elemente sind, enthalten ist.
Darunter muss es ** $ a \ _ j <a \ _k $ ** sein, um $ (a \ _i, a \ _j) = (a \ _ k, a \ _l) $ zu sein. Verwenden Sie daher Upper_bound, um die Nummer jedes Paares von zwei Elementen zu ermitteln, die dies erfüllt. Es dauert jedoch eine lineare Zeit, um den Index zu kennen, wenn Sie die Distanzfunktion verwenden. ** Implementieren Sie Ihre eigene Dichotomie und geben Sie den Index zurück **. Bei der Implementierung der Dichotomie habe ich auf meinen [diesen Artikel] verwiesen (https://qiita.com/DaikiSuyama/items/84df26daad11cf7da453).
D.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 INF 1000000000000 //10^12:∞
#define MOD 4000 //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
//MLE
signed main(){
//Code zur Beschleunigung der Eingabe
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll t;cin>>t;
REP(_,t){
ll n;cin>>n;
vector<ll> a(n);
REP(i,n)cin>>a[i];
//Verwaltet von jedem Wert
map<ll,vector<ll>> m;
REP(i,n){
FOR(j,i+1,n-1){
m[a[i]*MOD+a[j]].PB(i*MOD+j);
}
}
long long ans=0;
FORA(i,m){
//Halbierungssuche
ll m=SIZE(i.S);
REP(j,m-1){
ll l,r;l=j+1;r=m-1;
if(i.S[j]%MOD<ll(i.S[l]/MOD)){
ans+=(m-j-1);
continue;
}
if(i.S[j]%MOD>=ll(i.S[r]/MOD)){
continue;
}
while(l+1<r){
ll k=l+(r-l)/2;
if(ll(i.S[k]/MOD)>i.S[j]%MOD){
r=k;
}else{
l=k;
}
}
ans+=(m-r);
}
}
cout<<ans<<endl;
}
}
E Problem
Wiederholung kann mit PyPy leicht zu MLE werden, warum ... Wie auch immer ** Ich werde Rekursion in C ++ schreiben **.
Führen Sie die folgenden zwei Vorgänge aus.
(1) Eine Operation, die einen bestimmten Abschnitt auswählt und die in diesem Abschnitt enthaltene Anzahl um eins reduziert (es gibt jedoch jeweils mindestens einen)
② Wählen Sie eine Nummer und setzen Sie die Nummer auf 0.
Berücksichtigen Sie die Mindestanzahl von Vorgängen, wenn Sie diese Vorgänge ausführen und alle Spalten leeren. Die Operation von ② kann leicht erhalten werden, indem einfach die Anzahl der Operationen für die Länge des Abschnitts berechnet wird. Andererseits ist die Operation von ① wie folgt etwas kompliziert.
Für Operation (1) ist es am besten, den Abschnitt so lange wie möglich auszuwählen. Ich werde es diesmal nicht beweisen, aber ich habe das Gefühl, dass das Muster **, dass Sie nur das Ganze auswählen müssen, wenn Sie einen Abschnitt auswählen und eine Operation ausführen **, häufig erscheint (diesmal können Sie die Anzahl der Operationen reduzieren, indem Sie den Abschnitt eingrenzen Ich dachte, es sei nicht intuitiv, also fuhr ich mit dieser Richtlinie fort. ** Es sollte gerechtfertigt sein **, aber ...).
Wenn Sie die Operation von ① ausführen, führen Sie die Operation außerdem am Minimum des Abschnitts aus, nicht ** 1 auf einmal **. Darüber hinaus gibt es ein Element, das nach der Operation 0 wird, und der gesamte Abschnitt kann nicht so betrieben werden, wie er aus der Betriebsbedingung von ** ① ** stammt. Ermitteln Sie daher die Mindestanzahl von Operationen für jeden Abschnitt geteilt durch DFS * *.
In Anbetracht der Implementierung von DFS ist dies daher wie folgt.
(1) Wenn die Länge des gegebenen Intervalls $ x $ 1 ist.
Gibt $ min $ der Anzahl der Elemente (Anzahl der Operationen in ①) und 1 (Anzahl der Operationen in ②) zurück, die im Intervall $ x $ enthalten sind.
(2) Wenn die Länge des gegebenen Intervalls $ x $ größer als 1 ist.
Die Länge des Intervalls beträgt $ l $, die Mindestanzahl unter den im Intervall enthaltenen Zahlen beträgt $ m $, der Rückgabewert ist $ ret = 0 $ und der Vektor, der die geteilten Intervalle ersetzt, ist $ nex = $ { }Wird besorgt.
Darunter betrachten wir $ x [i] $ mit $ i = $ 0 ~ $ l $ -1, aber wenn $ x [i]! = M $, können wir es durch nex ersetzen. Wenn $ i = l $ -1 ist, ist das Intervall fest. Rufen Sie also dfs mit nex als Intervall auf und fügen Sie den Rückgabewert zu ret hinzu. Wenn $ x [i] = m $ ist und $ nex $ nicht leer ist, ist das Intervall fest. Rufen Sie also dfs mit $ nex $ als Intervall auf und fügen Sie den Rückgabewert zu ret hinzu. Lassen Sie zu diesem Zeitpunkt $ nex $ für das nächste Intervall leer.
Sie können die Lösung finden, indem Sie einfach die oben genannte DFS ausführen. Auch wenn DFS nicht perfektioniert ist, werden Probleme dieses Grades ein Problem sein, deshalb möchte ich mich dem widmen.
E.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 Enden)、のどちら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
ll dfs(vector<ll>& x){
ll l=SIZE(x);
//Wenn 0
if(l==1)return min(1,x[0]);
ll m=*min_element(ALL(x));
ll ret=m;
vector<ll> nex;
REP(i,l){
if(x[i]!=0){
nex.PB(x[i]-m);
if(i==l-1)ret+=dfs(nex);
}else{
if(SIZE(nex)){
ret+=dfs(nex);
nex.clear();
}
}
}
return min(ret,l);
}
signed main(){
ll n;cin>>n;
vector<ll> a(n);REP(i,n)cin>>a[i];
cout<<dfs(a)<<endl;
}
Nach F Problem
Ich werde diesmal überspringen
Recommended Posts