[PYTHON] Bildungs-Codeforces-Runde 87
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Ich nahm an einem Wettbewerb namens Edufo teil, der allgemein als Codeforces bekannt ist. Ich war verwirrt, weil ich den Unterschied zwischen den regulären Wettbewerben nicht verstehen konnte. Es waren drei Abschlüsse bis A, B, C1. Ich hatte das Gefühl, dass sowohl C2 als auch D gelöst werden könnten, aber am Ende konnte ich auch nicht lösen.
Als ich die Lösung auf Twitter usw. überprüfte, schien es mir möglich zu sein, die Methode zu finden, die ich mir vorstellen wollte, und ich möchte die Ursache der Lösung untersuchen.
Problem A
Es war schwierig, die Problemstellung zu entschlüsseln, und es dauerte lange, sie zu lösen. Es werden vier Werte von $ a, b, c und d $ angegeben, aber dieses Problem kann durch Zeichnen der folgenden Abbildung richtig beantwortet werden.
Die Gesamtschlafzeit sollte $ a $ oder mehr betragen. Wenn Sie zu Beginn für $ b $ schlafen, ertönt der Alarm, und danach ertönt der Alarm für $ c $, und die $ d $ -Zeit versucht ** zu schlafen. ** Sie können also tatsächlich nur $ cd $ schlafen und dies wird endlos wiederholt.
Erstens, wenn $ b \ geqq a $, passiert es, wenn $ b $ vergangen ist. Beachten Sie, dass dies $ b $ anstelle von $ a $ ist.
Wenn $ c \ leqq d $ ist, können Sie nur beim ersten $ b $ schlafen, sodass Sie -1 ausgeben müssen, wenn a> b.
Das Obige ist implementiert und wird wie folgt.
A.py
t=int(input())
for i in range(t):
a,b,c,d=map(int,input().split())
if d>=c:
if b>=a:
print(b)
else:
print(-1)
else:
if b>=a:
print(b)
else:
a-=b
num=-((-a)//(c-d))
print(b+num*c)
B-Problem
Gibt die Länge des kürzesten Teilstrings aus, der alle 1, 2 und 3 enthält. Wenn ein solcher Teilstring jedoch nicht vorhanden ist, sollte 0 ausgegeben werden.
Dieses Problem kann mit der ** Skalierungsmethode ** gelöst werden, da die Abschnitte ** kontinuierlich ** verschoben und gezählt werden können. Die Implementierung ist jedoch nach der Entwicklung der Skalierungsmethode langsam. Ich fühlte mich selbst als Amateur.
Bei der Implementierung der Skalierungsmethode sollte die Abfrageverarbeitung in der Reihenfolge "** Vorrücken des rechten Endes nach rechts ** → ** Vorrücken des linken Endes nach rechts **" durchgeführt werden. Beachten Sie auch, dass ** die rechte Kante den Bereich der zu untersuchenden Sequenz nicht überschreitet ** und ** die linke Kante die rechte Kante ** nicht überschreitet.
B.py
t=int(input())
for i in range(t):
s=input()
le=len(s)
l,r=0,0
d=[0,0,0]
d[int(s[0])-1]=1
ans=0
while True:
#R Entscheidung
while not all(d) and r!=le-1:
r+=1
d[int(s[r])-1]+=1
if r==le-1:
break
#l Entscheidung
while l!=le-1:
if all(d):
if ans==0:
ans=r-l+1
else:
ans=min(ans,r-l+1)
d[int(s[l])-1]-=1
l+=1
else:
break
if r==le-1 or l==le-1:
break
print(ans)
C1-Problem
Bei einer geraden Zahl können Sie das Polygon mit dem kleinsten Quadrat einschließen, indem Sie die Zahlen wie unten gezeigt anordnen (ich kann es nicht beweisen, weil ich es heuristisch gemacht habe).
Wenn Sie ein Dreieck bilden, indem Sie die Mitte des Polygons und die Eckpunkte des Polygons verbinden und mit dem trigonometrischen Verhältnis (sin, cos, tan) berechnen, wird $ \ frac {1} {\ tan {\ frac {90} {n}} } $ Du kannst fragen.
Übrigens ist es als heuristische Idee der Scheitelpunkt des Polygons, der am weitesten von der Mitte des Polygons entfernt ist, und diese Form ist eine, weil es notwendig ist, eine ** Anordnung mit guter Symmetrie ** zu berücksichtigen. Es fühlt sich bequem an.
C1.py
import math
t=int(input())
for i in range(t):
n=int(input())
print(1/math.tan(math.radians(90/n)))
C2-Problem
Bei einer ungeraden Zahl habe ich falsch verstanden, dass die am weitesten links stehende Figur schmutzig geschrieben war und die obere und untere Seite das Quadrat berührten (** Zeichne die Figur ordentlich! **).
Nach wie vor gibt es beim Zeichnen mit Symmetrie nur die oben genannten drei Muster **, aber das linke und das rechte Muster können beim Drehen des Quadrats als ** dasselbe Muster angesehen werden **. Überlegen Sie daher, welches der Muster ganz links und in der Mitte den größeren Bereich hat, bei dem es sich eindeutig um das mittlere Muster handelt (dies können Sie durch Berechnung herausfinden).
Dieses mittlere Muster befindet sich zwischen dem rechten und dem linken Muster, und da es $ \ frac {180} {n} $ vom linken zum rechten Ende verschiebt, wird angenommen, dass $ \ frac {90} {n} $ vom Muster des linken Endes verschoben wird. Zum Beispiel ist es möglich, $ \ frac {\ cos {\ frac {45} {n}} {\ sin {\ frac {90} {n}}} $ zu erhalten, indem dieselbe geometrische Überlegung wie zuvor durchgeführt wird. Ich kann es schaffen
C2.py
import math
t=int(input())
for i in range(t):
n=int(input())
print(math.cos(math.radians(45/n))/math.sin(math.radians(90/n)))
D Problem
Ich dachte, es wäre möglich, es mit BIT zu lösen, aber ich konnte es nicht lösen, weil ich nicht wusste, dass es möglich ist, eine Dichotomie für BIT durchzuführen. Es ist nicht schwierig, eine Dichotomie durchzuführen.
Zuallererst werden die einzufügende Position und die zu löschende Position ** basierend auf der Sortierung ** bestimmt. Erwägen Sie daher, diesen Mehrfachsatz zu sortieren und zu arbeiten, während Sie diese Sortierung beibehalten.
Hier sind ** doppelte Zahlen ** gleich, auch wenn sie beim Sortieren zusammen betrachtet werden, also ** ein Array x ** ($ 1 \ leqq $ (Element von x), das speichert, wie viele jede Zahl ist) Bereiten Sie $ \ leqq n $) vor.
Wenn Sie darüber nachdenken, darunter einzufügen, können Sie es mit O (1) ausführen (da Sie dem Element des Arrays $ \ weil $ nur +1 hinzufügen), aber beim Löschen entscheiden Sie, dass das Element des Arrays -1 ist Es ist notwendig, die Nummer des Elements zu erhalten, die O (n) ist.
Hier wird das Array x **, in dem die Nummer jeder Nummer gespeichert ist, von BIT verwaltet (siehe dieser Artikel für BIT). Dann ist die Einfügung O ($ \ log {n}
Wenn Sie die Bestellung bisher löschen können, können Sie ein Programm mit O ($ n (\ log {n}) ^ 2
ios::sync_with_stdio(false);
cin.tie(nullptr);
D.cc
//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
#define MAX(x) *max_element(ALL(x)) //Finden Sie den Maximalwert
#define MIN(x) *min_element(ALL(x)) //Finden Sie den Mindestwert
//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
//1-indexed
class BIT {
public:
ll n; //Datenlänge
vector<ll> bit; //Datenspeicherort
BIT(ll n):n(n),bit(n+1,0){} //Konstrukteur
//k & -k ist LSB
//bit_x bis i o(log(n))Fügen Sie mit hinzu
void add(ll i,ll x){
if(i==0) return;
for(ll k=i;k<=n;k+=(k & -k)){
bit[k]+=x;
}
}
//bit_1 + bit_2 + … + bit_n bis O.(log(n))Fragen Sie nach
ll sum(ll i){
ll s=0;
if(i==0) return s;
for(ll k=i;k>0;k-=(k & -k)){
s+=bit[k];
}
return s;
}
//a_1 + a_2 + … + a_i >=Finde das kleinste i so, dass x(a_k >= 0)
//Wenn x 0 oder weniger ist, gibt es kein entsprechendes Element → 0 wird zurückgegeben
ll lower_bound(ll x){
if(x<=0){
return 0;
}else{
ll i=0;ll r=1;
//Holen Sie sich die maximal mögliche Abschnittslänge
//Sollte das kleinste Quadrat von n oder weniger sein(Der größte Abschnitt einer Reihe von Spalten, die von BIT verwaltet werden)Ich suche
while(r<n) r=r<<1;
//Die Länge des Abschnitts wird bei jeder Untersuchung halbiert
for(int len=r;len>0;len=len>>1) {
//Bei der Übernahme dieses Abschnitts
if(i+len<n && bit[i+len]<x){
x-=bit[i+len];
i+=len;
}
}
return i+1;
}
}
};
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n,q;cin >> n >> q;
BIT a(n);REP(i,n){ll a_sub;cin >> a_sub;a.add(a_sub,1);}
vector<ll> k(q);REP(i,q) cin >> k[i];
REP(i,q){
if(k[i]>0){
a.add(k[i],1);
}else{
//Was in der Zahlenspalte enthalten ist, wird immer angegeben
a.add(a.lower_bound(-k[i]),-1);
}
}
vector<ll> answers(n);
REP(i,n){answers[i]=a.sum(i+1);}
if(answers[n-1]<=0){
cout << 0 << endl;return 0;
}
REP(i,n){
if(i>0){
if(answers[i]-answers[i-1]>0){
cout << i+1 << endl;return 0;
}
}else{
if(answers[i]>0){
cout << i+1 << endl;return 0;
}
}
}
}
E-Problem, F-Problem, G-Problem //codeforces.com/contest/1354/problem/G)
Ich glaube, mir fehlen immer noch die Fähigkeiten, also werde ich diese Zeit überspringen.
Recommended Posts