[PYTHON] Codeforces Round # 657 (Div. 2) Review
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Ich bin zum ersten Mal seit 2 Monaten wieder bei codeforces. A Ich war auf ein kaltes Wetter vorbereitet, weil ich das Problem lange Zeit nicht lösen konnte, aber aus irgendeinem Grund wurde es ziemlich warm. Es kann zu Boden gekommen sein.
Wie auch immer, es hat zum ersten Mal seit langer Zeit wieder seine Farbe geändert, also denke ich, dass es eine gute Erfahrung war. Ich werde mein Bestes tun, um AtCoder: Blau, Coderforces: Lila anzustreben.
Problem A
Ich wurde in das A-Problem versetzt, verlor also die Fassung und konnte es nicht lösen. Im Prinzip ist nichts schwierig ...
Es ist nicht allzu schwierig, da der Berechnungsbetrag von $ O (t \ times n ^ 2) $ zulässig ist. Überprüfen Sie zunächst, welcher Teil der Zeichenfolge "abacaba" (im Folgenden als Zeichenfolge S bezeichnet) wahrscheinlich erscheint. Wenn die Zeichenfolge S beim Aktivieren mehrmals angezeigt wird, wird "Nein" ausgegeben, und wenn die Zeichenfolge S nur einmal angezeigt wird, ändern Sie "?" In "d ~ z" und geben Sie aus. Das ist gut. In anderen Fällen prüfen wir, ob es eine Zeichenfolge S gibt, indem wir das "?" Ändern. Dadurch wird nur eine ** Zeichenfolge S ** erstellt.
Außerdem ist es leicht zu verstehen, ob Sie die Prüfung der Teilzeichenfolge, die die Zeichenfolge S sein kann, trennen und ob es nur eine ** Zeichenfolge S ** gibt.
A.py
#Überprüfen Sie, wo die Möglichkeit von Abaca besteht
#Seltsam
#Indexfehler ...
a=["a","b","a","c","a","b","a"]
t=int(input())
for _ in range(t):
n=int(input())
s=list(input())
check=[0]*(n-6)
for i in range(n-6):
for j in range(i,i+7):
if s[j]!=a[j-i] and s[j]!="?":
break
else:
if s[i:i+7]==a:
check[i]=2
else:
check[i]=1
if check.count(2)>1:
print("No")
continue
elif check.count(2)==1:
print("Yes")
print(("".join(s)).replace("?","z"))
continue
#?Ändern und nur ein Muster
g=False
for i in range(n-6):
if check[i]==1:
f=False
cand=[a[j-i] if i<=j<=i+6 else s[j] if s[j]!="?" else "z" for j in range(n)]
for j in range(n-6):
if i!=j:
for k in range(j,j+7):
if cand[k]!=a[k-j]:
break
else:
f=True
if not f:
print("Yes")
print("".join(cand))
g=True
break
if not g:print("No")
B-Problem
Betrachten Sie zunächst den Bereich, der durch $ a, b, c $ ausgedrückt werden kann. Da dies mehr als $ l $ und weniger als $ r $ ist, wenden wir jede auf die angegebene Formel an. Dann wird es wie folgt.
Erwägen Sie auf dieser Grundlage, eines von ① und ② zu fixieren. ** ② ist kontinuierlich und leicht zu denken **, also überlegen Sie, ① zu reparieren.
Dann ist ① optimal nahe an m, so dass es zu $ Ceil (\ frac {m} {a}) \ mal $ oder $ Etage (\ frac {m} {a}) \ mal a $ wird.
Wenn daher die Differenz zwischen diesem Wert und dem absoluten Wert von $ m $ $ r-l $ ist, dann existieren auch $ b und c $ und die Antwort lautet.
Sie können nach jedem $ a $ suchen und die Antwort finden.
Außerdem beträgt der Berechnungsbetrag $ O (t \ times (r-l)) $, und im Fragensatz steht, dass die Antwort immer erhalten wird. Schreiben Sie den Code also wie folgt.
B.py
t=int(input())
for _ in range(t):
l,r,m=map(int,input().split())
f=False
for a in range(l,r+1):
n1,n2=m//a,-((-m)//a)
if l-r<=m-n1*a<=r-l:
for c in range(l,r+1):
b=m-n1*a+c
if l<=b<=r:
if m+c-b!=0:
print(a,b,c)
f=True
break
if f:break
if l-r<=m-n2*a<=r-l:
for c in range(l,r+1):
b=m-n2*a+c
if l<=b<=r:
if m+c-b!=0:
print(a,b,c)
f=True
break
if f:break
C-Problem
Ich denke nicht, dass die Richtlinie schwierig ist, aber ist sie in Python nur knapp? ?? Ich habe Angst, also habe ich C ++ verwendet.
Ich kann nicht alles ausprobieren, weil $ n $ groß ist. Nach einer bestimmten Anzahl von Versuchen müssen Sie jedoch nur ein bestimmtes $ b_i $ ** auswählen. Ich dachte, es wäre am besten, das Maximum von $ b_i $ zu nehmen, aber die Stichprobe passte nicht. Wenn Sie sorgfältig darüber nachdenken, müssen Sie $ a_i $ auswählen, wenn Sie ** $ b_i $ ** auswählen. Abhängig vom Wert ist es nicht optimal, das Maximum $ b_i $ zu nehmen. Deshalb habe ich mich entschlossen, alle Wege ($ m $ Wege) auszuprobieren, um weiterhin das $ b_i $ zu nehmen.
Wenn ** $ b_i $ nicht genommen wird **, gilt $ n \ leqq m $, und in diesem Fall können Sie $ n $ aus dem größeren von $ a $ auswählen. Außerdem muss $ a_i $ in aufsteigender Reihenfolge angeordnet werden. Da jedoch $ a_i $ entsprechend ** $ b_i $ später benötigt wird **, bereiten Sie ein Array $ c $ vor, in dem $ a_i $ in aufsteigender Reihenfolge angeordnet ist. Machen.
Wenn Sie hier $ b_i $ auswählen, sind diejenigen, die in $ a $ größer als $ b_i $ sind, auch am besten geeignet, um die Summe zu maximieren, und die Elemente des Arrays $ c $ sind mehr als die Elemente, nach denen Upper_bound sucht Alles was Sie tun müssen, ist auszuwählen. Zu diesem Zeitpunkt ist es ineffizient, die Summe dieser Elemente jedes Mal zu berechnen, daher wird sie durch die kumulative Summe ** berechnet.
Außerdem müssen Sie $ a_i $ gleichzeitig mit $ b_i $ auswählen, und ** $ a_i $ wird danach klassifiziert, ob es zuvor ausgewählt wurde. Sie können das oben Gesagte wiederholen und die maximale Antwort finden.
C.cc
//Zur Compileroptimierung
#pragma GCC optimize("Ofast")
//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 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.
#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
signed main(){
//Code zur Beschleunigung der Eingabe
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll t;cin>>t;
while(t--){
ll n,m;cin>>n>>m;
vector<ll> a(m);
vector<ll> b(m);
vector<ll> c(m);
REP(i,m){cin>>a[i]>>b[i];c[i]=a[i];}
//Sortierter Typ in einem
sort(ALL(c));
//Finden Sie die kumulative Summe von c(Aus der Gegenrichtung)
vector<ll> d(m+1);d[m]=0;
REPD(i,m)d[i]=c[i]+d[i+1];
ll ans=0;
//Bei Auswahl nur a
if(n<=m)ans=max(ans,d[m-n]);
//Welches b-Element soll ich wählen?
REP(i,m){
auto as=upper_bound(ALL(c),b[i]);
ll anum=distance(c.begin(),as);
if(a[i]>b[i] and m-anum<=n)ans=max(d[anum]+b[i]*(n-(m-anum)),ans);
if(a[i]<=b[i] and m-anum<=n-1)ans=max(d[anum]+b[i]*(n-(m-anum)-1)+a[i],ans);
}
cout<<ans<<endl;
}
}
Nach D Problem
Ich werde diesmal überspringen
Recommended Posts