[PYTHON] AtCoder Beginner Contest 164 Bewertung
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Problem A
Fälle werden danach klassifiziert, ob w s oder mehr ist.
A.py
s,w=map(int,input().split())
print("unsafe" if w>=s else "safe")
B-Problem
Aufgrund des Angriffs von Takahashi-kun wird die physische Stärke von Aoki-kun zu c → cb, und die physische Stärke von Takahashi-kun wird zu einer → Anzeige als der Angriff von Aoki-kun. Da die Einschränkungen locker sind, wird die physische Stärke zuerst 0 oder weniger, indem der Angriff simuliert wird. Derjenige, der verliert. Der Scheck speichert, welche Angriffsrunde.
B.py
a,b,c,d=map(int,input().split())
check=True
while True:
if check:
c-=b
if c<=0:
print("Yes")
break
else:
a-=d
if a<=0:
print("No")
break
check=not check
C-Problem
Dies ist ein allgemeines Muster. Es gibt verschiedene Möglichkeiten ohne Abdeckung. Verwenden Sie daher set.
C.py
n=int(input())
s=set()
for i in range(n):
s.add(input())
print(len(s))
D Problem
Wenn Sie auch nur für einen Moment in D stecken bleiben, werden Sie einen Fehler wie diesen haben ... ** Sie müssen die typischen Probleme genau kennen **.
Als ich mir das Beispiel ansah, bemerkte ich, dass ** es nur wenige Muster gibt **, und wenn ich ehrlich alle Zeichenketten von i bis j schreibe, ist klar, dass O ($ N ^ 2 $) nicht ausreicht **. Sie können sehen, dass es gibt.
Basierend darauf, wenn man die Zahl $ n $ vom $ i $ -Zeichen bis zum $ j $ -Zeichen betrachtet, ** "Zahl vom $ i $ -Zeichen bis zum letzten Zeichen ($ k
answerD.py
s=input()
l=len(s)
se=dict()
k=0
for i in range(l-1,-1,-1):
k+=(pow(10,l-1-i,2019)*int(s[i]))
k%=2019
if k in se:
se[k]+=1
else:
se[k]=1
ans=0
for j in se:
i=se[j]
if i>1:
ans+=(i*(i-1)//2)
if j==0:
ans+=i
print(ans)
E Problem
Es ist ein Problem der erweiterten Dyxtra-Methode (ich habe die Dyxtra-Methode bemerkt, konnte sie aber nicht rechtzeitig lösen ...). Sogar die Implementierung der grundlegenden Dyxtra-Methode war verdächtig, daher habe ich sie in einem anderen Artikel als Zusammenfassung der Dyxtra-Methode zusammen mit einer Erläuterung dieses Problems angegeben. Bitte seien Sie dabei, wenn es eine gute Referenz ist. Vorerst werde ich nur den folgenden Code einfügen.
answerE.cc
//Einschließen(Alphabetischer Reihenfolge,bits/stdc++.Eine Fraktion, die h nicht benutzt)
#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
//Die Größe dieses INF ist ebenfalls wichtig(Wenn es klein ist, wird es WA sein)
#define INF 1000000000000000 //10^15:Extrem großer Wert,∞
#define MOD 10000007 //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
//Ab hier ist eine Vorlage
#define VL vector<ll>
//Größer in aufsteigender Reihenfolge
//Vektorvergleich ist die Priorität des ersten Elements, des zweiten Elements ...
#define PQ priority_queue<VL,vector<VL>,greater<VL>>
//Maximale Anzahl an Silbermünzen
#define MAXS ll(2999)
//f ist der Index des Startpunktes
//n ist die Gesamtzahl der Eckpunkte
//s ist die Anzahl der Währungen, die Sie zuerst haben
//Kante ist der Index und die Abnahme der Scheitelpunkte jenseits dieser Seite für die Seite, die sich von jedem Scheitelpunkt erstreckt(oder erhöhen)Ein Array mit der Anzahl der Silbermünzen und der dafür benötigten Zeit
vector<VL> dijkstra(ll f,ll n,ll s,vector<vector<VL>>& edge){
//Die maximale Anzahl an Silbermünzen beträgt MAX
s=min(s,MAXS);
//Ein Array, das prüft, ob die kürzeste Zeit im Status der Nummer jeder Währung an jedem Scheitelpunkt ermittelt wurde
vector<VL> confirm(n,VL(MAXS+1,false));
//Ein Array, das die kürzeste Zeit im Status der Nummer jeder Währung an jedem Scheitelpunkt speichert
//Ausgangszustand am Startpunkt(Ich habe S Währung)Ist 0, sonst initialisiert INF die kürzeste Zeit
vector<VL> mincost(n,VL(MAXS+1,INF));mincost[f][s]=0;
//Bestätigt(Scheitel,Anzahl der Währungen)Entlang der Seite, die sich vom Satz aus erstreckt(Scheitel,Anzahl der Währungen)Prioritätswarteschlange, die die Zeit spart, die ab dem Anfangszustand von benötigt wird
PQ mincand;mincand.push({mincost[f][s],f,s});
//Die kürzeste Zeit kann aktualisiert werden, wenn das mincand-Element Null ist(Scheitel,Anzahl der Währungen)Zeigt an, dass kein Status von vorhanden ist
while(!mincand.empty()){
//Es scheint die kürzeste Entfernung zu erreichen(Scheitel,Anzahl der Währungen)Nehmen Sie den Zustand von
VL next=mincand.top();mincand.pop();
//Schon das(Scheitel,Anzahl der Währungen)Wenn die kürzeste Zeit im Status bestätigt ist, überspringen Sie sie
if(confirm[next[1]][next[2]]) continue;
//Wenn es nicht bestätigt wird, machen Sie es bestätigt
confirm[next[1]][next[2]]=true;
//Bestätigt(Scheitel,Anzahl der Währungen)Die Information der Seite, die sich aus dem Zustand von erstreckt, wird abgerufen, l ist die Nummer der Seite
vector<VL>& v=edge[next[1]];ll l=SIZE(v);
REP(i,l){
//Berechnen Sie, wie viele Silbermünzen nach dem Umzug sein werden. Wenn es MAXS überschreitet, setzen Sie es auf MAXS.
ll nextS=min(next[2]+v[i][1],MAXS);
//Kann sich nicht bewegen, wenn die Anzahl der Silbermünzen nach dem Bewegen weniger als 0 beträgt
if(nextS<0) continue;
//Es ist keine Aktualisierung erforderlich, wenn die Zeit beim Bewegen länger ist als die Mincost am Ende der Seite(Erfüllen Sie dies, wenn die Spitze der Seite bestätigt ist)
if(mincost[v[i][0]][nextS]<=next[0]+v[i][2]) continue;
//aktualisieren
mincost[v[i][0]][nextS]=next[0]+v[i][2];
//Wenn aktualisiert, das(Scheitel,Anzahl der Währungen)Der Zustand(Nicht bestätigt(Scheitel,Anzahl der Währungen)In dem Staat von)Kann die kürzeste Entfernung sein
mincand.push({mincost[v[i][0]][nextS],v[i][0],nextS});
}
}
return mincost;
}
signed main(){
ll n,m,s;cin >> n >> m >> s;
vector<vector<VL>> edge(n);
REP(i,m){
ll u,v,a,b;cin >> u >> v >> a >> b;
//Hier sind die Seiten bidirektional
edge[u-1].PB({v-1,-a,b});
edge[v-1].PB({u-1,-a,b});
}
REP(i,n){
ll c,d;cin >> c >> d;
//Fügen Sie die Operation hinzu, um die Währung als Kante zu erhöhen
edge[i].PB({i,c,d});
}
vector<VL> mincost=dijkstra(0,n,s,edge);
FOR(i,1,n-1) cout << MIN(mincost[i]) << endl;
}
F Problem
Ich war müde von der Anstrengung eines Artikels aufgrund des E-Problems, also werde ich es zu einem anderen Zeitpunkt lösen.
Recommended Posts