Ich hatte nicht für die Graduiertenschule studiert, aber ich konnte es fast nicht jeden Tag lösen. Ich möchte mein Bestes geben, damit beide kompatibel sind, und sobald ich es jeden Tag löse, werde ich daran denken, einen Artikel als Rezension zu schreiben.

Tag 4

Ich habe das ABC172-E gelöst, das ich während des Wettbewerbs nicht bestehen konnte. Dies ist ein Problem des Einschlussprinzips und wurde in diesem Artikel erläutert.

Tag 5

ABC137-D Summer Vacation

Zeit genommen

14 Minuten

Erwägung

Es ist ein relativ einfaches Problem, also habe ich es ohne viel Rücksicht gelöst.

Der Teilzeitjob für $ i $ Tag (im Folgenden als Teilzeitjob abgekürzt) erhält die Belohnung $ B \ _i $ nach $ A \ _i $ Tagen. Wenn Sie also nicht vor $ MA \ _i $ Tagen Teilzeit arbeiten, erhalten Sie die Belohnung. Ich kann nicht Daher sind die Bytes, die am $ j $ Tag arbeiten und Belohnungen erhalten können, die Bytes, die die Belohnung innerhalb von $ M-j $ Tagen erhalten können. Mit anderen Worten, Sie können sehen, dass ** in späteren Tagen nur wenige Kandidatenbytes erstellt werden können . Berücksichtigen Sie daher in der Reihenfolge die Bytes, die am $ M-1 $ -Tag ausgeführt werden können (Belohnung innerhalb eines Tages), die Bytes, die am $ M-2 $ -Tag ausgeführt werden können (Belohnung innerhalb von 2 Tagen), ... ** Belohnung Wenn Sie gierig aus hochrangigen Bytes auswählen ** ( Die Grundlage für belohnungsbezogene Probleme ist die gierige Methode! **), werden Sie feststellen, dass sie gut ist.

Python-Code

`abc137d.py`


from heapq import *
n,m=map(int,input().split())
#Wie viele Tage wird es dauern(1-indexed)
ab=[[] for i in range(m)]
for i in range(n):
    a,b=map(int,input().split())
    #Nicht überschreiten
    if a<=m:
        ab[a-1].append(b)
x=[]
l=0
ans=0
for i in range(m-1,-1,-1):
    for j in ab[m-1-i]:
        heappush(x,-j)
        l+=1
    if l:
        l-=1
        ans+=heappop(x)
print(-ans)

Tag 6

ABC130-E Common Subsequence

Zeit genommen

Ich konnte es nicht länger als 30 Minuten machen, also Kommentar AC

Fehlerursache

Ich konnte den Indexfehler und die Lösung der gemeinsamen Unterspalte nicht aussortieren.

Erwägung

Erläuterung Obwohl es sich um AC handelt, war es nur ein ** Fehler im Index **. Python erlaubt negative Indizes, daher möchte ich mir angewöhnen, Indizes zu überprüfen.

Zunächst einmal mögen Sie das Gefühl haben, dass es DP-ähnlich ist, aber ** allgemeine Unterspalten ** sind sehr schwierig zu handhaben. Tatsächlich ist das typischste Musterproblem von Teilsequenzen ** LCS (Longest Common Sequence) **, und es ist dieses Mal leicht zu lösen, wenn Sie einer ähnlichen Richtlinie folgen.

Daher ist das in DP verwendete Array ** $ dp [i] [j]: = $ (bis zu $ i $ Zeichen ($ S_i $) von S und $ j $ Zeichen ($ T_j $) von T). Die Anzahl der allgemeinen Unterspalten, die von bis zu ** erstellt werden können. Um den Übergang von DP zu berücksichtigen, sollten Sie auf dieser Grundlage überlegen, wie $ dp [i + 1] [j + 1] $ bestimmt werden soll.

Ich konnte mir das Problem der gemeinsamen Unterspalte nicht vorstellen, aber es hängt davon ab, ob ** $ S_ {i + 1} $ und $ T_ {j + 1} $ in der gemeinsamen Unterspalte enthalten sind ** Es ist leicht zu verstehen, wenn Sie darüber nachdenken.

(1) Wenn sowohl $ S_ {i + 1} $ als auch $ T_ {j + 1} $ in der gemeinsamen Unterspalte enthalten sind

Das Ende des gemeinsamen Teilstrings muss ** $ S_ {i + 1} = T_ {j + 1} $ von $ S_ {i + 1} $ und $ T_ {j + 1} $ ** sein , $ Dp [i] [j] $ kann als gemeinsame Unterspalte plus $ S_ {i + 1} (= T_ {j + 1}) $ betrachtet werden.

(2) Wenn nur $ S_ {i + 1} $ in der gemeinsamen Unterspalte enthalten ist

Gemeinsame Unterspalten von $ S_ {i + 1} $ und bis zu $ T_j $ ($ dp [i + 1] [j] $) bis $ S_i $ und gemeinsame Unterspalten von $ T_j $ ($ dp) Alles was Sie tun müssen, ist [i] [j] $) auszuschließen.

(3) Wenn nur $ T_ {j + 1} $ in der gemeinsamen Unterspalte enthalten ist

Gemeinsame Unterspalten von $ S_ {i} $ und $ T_ {j + 1} $ ($ dp [i] [j + 1] $) bis $ S_i $ und $ T_j $ Alles was Sie tun müssen, ist ausschließen ($ dp [i] [j] $).

(4) Wenn weder $ S_ {i + 1} $ noch $ T_ {j + 1} $ in der gemeinsamen Unterspalte enthalten sind

Stellen Sie sich einen allgemeinen Teilstring ($ dp [i] [j] $) vor, der bis zu $ S_ {i} $ und bis zu $ T_ {j + 1} $ betragen kann.

Von Oben,

dp[i+1][j+1] = \left\{
\begin{array}{ll}
dp[i][j]+(dp[i+1][j]-dp[i][j])+(dp[i][j+1]-dp[i][j])+dp[i][j]=dp[i+1][j]+dp[i][j+1](S_{i+1}=T_{j+1})\\
(dp[i+1][j]-dp[i][j])+(dp[i][j+1]-dp[i][j])+dp[i][j]=dp[i+1][j]+dp[i][j+1]-dp[i][j](S_{i+1} \neq T_{j+1})
\end{array}
\right.

Es wird sein.

Außerdem hat $ dp [i] [0], dp [0] [j] \ (i = 0 $ ~ $ N, j = 0 $ ~ $ M) $ ** nur eine leere Zeichenfolge als gemeinsamen Teilstring * * Es kann also als 1 initialisiert werden.

Mit dem Obigen können Sie die Antwort finden, indem Sie $ S_i $ und $ T_j $ in der Reihenfolge durch eine zweidimensionale Schleife entscheiden. Sie müssen auch durch $ 10 ^ 9 + 7 $ teilen.

Python-Code

`abc130e.py`


mod=10**9+7
n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[[0]*(m+1) for i in range(n+1)]
for i in range(n+1):
    dp[i][0]=1
for i in range(m+1):
    dp[0][i]=1
for i in range(n):
    for j in range(m):
        if s[i]==t[j]:
            dp[i+1][j+1]=(dp[i+1][j]+dp[i][j+1])%mod
        else:
            dp[i+1][j+1]=(dp[i+1][j]+dp[i][j+1]-dp[i][j])%mod
print(dp[n][m])

Tag 7

ABC131-E Friendships

Zeit genommen

Es dauerte mehr als 40 Minuten und ich konnte keine Klimaanlage, also erklärte ich die Klimaanlage

Fehlerursache

Ich konnte die typischen Muster der Graphkonstruktion nicht aussortieren.

Erwägung

** Vorläufig habe ich beschlossen, verschiedene Diagramme zu zeichnen und sie auffindbar zu machen **, aber ich konnte die Logik nicht einfach konstruieren. Als Ergebnis des Experiments ist, wenn sich Seiten zwischen allen Scheitelpunkten befinden, die Anzahl der Scheitelpunktpaare, deren kürzester Abstand 2 ist, 0, also die Anzahl der Scheitelpunktpaare, deren kürzester Abstand 2 ist, indem die Seiten nacheinander reduziert werden. Ich habe versucht, einen Weg zu finden, um eins nach dem anderen zu erhöhen. Außerdem war mir zu diesem Zeitpunkt nicht klar, dass der verkettete Graph mindestens $ N-1 $ benötigt, aber ich habe mich verlaufen **.

(Das Folgende ist eine Überlegung, nachdem Sie die Erklärung usw. gesehen haben.)

Zunächst scheint es einfach zu sein, eine Richtlinie zu erstellen, die ** bei einem Konstruktionsproblem, bei dem der Minimalfall und der Maximalfall entschieden werden, den Minimalfall und den Maximalfall berücksichtigt und gut zwischen ihnen konfiguriert werden kann **. Mit anderen Worten, wenn zwischen allen Eckpunkten Kanten vorhanden sind, ist K das Minimum (0). Betrachten Sie also den Fall, in dem es das Maximum ist.

Hier erfordern ** verkettete Graphen $ N-1 $ Kanten und der kürzeste Abstand zwischen ihren Eckpunkten ist 1 , also $ K> \ frac {N (N-1)} {2 } - (N-1) = \ frac {(N-1) (N-2)} {2} $ Ein verketteter Graph kann nicht erstellt werden. Daher wird erwartet, dass $ K $ das Maximum bei ** $ K = \ frac {(N-1) (N-2)} {2} $ ** ist. Betrachtet man hier einen Graphen (Sterngraphen) mit einer Kante zwischen Scheitelpunkt 1 und einem anderen Scheitelpunkt, zwischen zwei beliebigen Scheitelpunkten außer Scheitelpunkt 1 ($ \ frac {{(N-1)} {(N) Die kürzeste Entfernung von -2)}} {2} $ Straßen) beträgt 2, und Sie können ein verkettetes Diagramm erstellen, das $ K $ erfüllt ( Kürzeste, um die Anzahl der Scheitelpunkte mit der kürzesten Entfernung von 2 zu erhöhen). Es kann einfacher sein, sich vorzustellen, dass ** der Abstand zwischen Scheitelpunkten mit einem Abstand von mehr als 3) beseitigt wird.

Dann ** sollten Sie die Seiten nacheinander gegenüber dem Sterngraphen vergrößern und die Scheitelpunkte mit dem kürzesten Abstand von 2 nacheinander verringern , aber die Seiten zwischen zwei Scheitelpunkten verbinden, die nicht durch die Seiten verbunden sind () Sie können den Abstand zwischen den Scheitelpunkten um eins verringern, ohne den kürzesten Abstand zwischen den anderen Scheitelpunkten zu beeinflussen **). Der Grund, warum sich dies nicht auf den Abstand zwischen den beiden anderen Scheitelpunkten auswirkt, besteht darin, dass der kürzeste Abstand zwischen den beiden Scheitelpunkten im Diagramm 1 oder 2 beträgt, wobei einige Seiten zum Sterndiagramm hinzugefügt werden, sodass die Änderung des kürzesten Abstands 2 beträgt, wenn die Seiten hinzugefügt werden. Weil es nur 1 ist.

Aus dem Obigen wird der Graph des Subjekts konstruiert, indem die Operation zum Erhöhen der Kanten um $ \ frac {{(N-1)} \ times {(N-2)}} {2} -k $ mal aus dem Zustand des Sterngraphen ausgeführt wird. können.

Außerdem ** scheint es besser, sich beim Erstellen von Diagrammen an typische Diagramme zu erinnern, die unterschiedliche Formen haben **. Die folgenden drei sind besonders berühmt.

Python-Code

`abc131e.py`


n,k=map(int,input().split())
if k>(n-1)*n//2-(n-1):
    print(-1)
else:
    ans=[(1,i) for i in range(2,n+1)]
    lestnum=(n-1)*n//2-(n-1)-k
    for i in range(2,n):
        for j in range(i+1,n+1):
            if lestnum!=0:
                ans.append((i,j))
                lestnum-=1
    print(len(ans))
    for i in ans:
        print(" ".join(map(str,i)))

Tag 8

Ich konnte es nicht tun, weil ich viele Stunden hatte und es vom Morgen an voll war. Ich werde es in Zukunft nicht tun.

Tag 9

Ich sagte ihm, er solle es nicht tun, aber ich habe das Timing verpasst, weil ich zu genau über die Themen war ...

Tag 10

ABC134-E Sequence Decomposing

Zeit genommen

Ich denke nicht, dass es für ungefähr 30 Minuten schlecht ist.

Erwägung

Es ist ziemlich schwierig, es zu beweisen, wie die Antwort sagt, aber ich denke, es ist nicht so schwierig, es mit einer vernünftigen Politik zu lösen.

Betrachten Sie zunächst das Malen von $ A \ i $ in der Reihenfolge des kleinsten $ i $, aber wenn es zu $ A \ i \ geqq A \ j (i <j) $ wird, können Sie nicht dieselbe Farbe malen. Sie müssen mit einer neuen Farbe malen. Malen Sie nun bis zu $ A_i $ mit $ k $ Farbe, ** um zu überlegen, welche Farbe als nächstes neu gestrichen werden soll **, die maximale Anzahl von $ A_1 $ ~ $ A_i $ für jede Farbe ($ \ leftrightarrow $) Speichern Sie die letzte Nummer) (Farben). Wenn zu diesem Zeitpunkt keine Zahl kleiner als $ A {i + 1} $ in Farben ist, wird $ A {i + 1} $ in Farben als die Zahl eingefügt, die mit einer neuen Farbe gemalt werden soll. Wenn umgekehrt eine Zahl kleiner als $ A {i + 1} $ in Farben ist, schreiben Sie die größte Zahl darin um (entfernen Sie diese Zahl aus Farben und dann $ A_ {i +) Es ist leicht zu erkennen, dass (Einfügen von 1} $) optimal ist **, wenn man das Gegenbeispiel betrachtet.

Um eine Zahl kleiner als XX zu finden, muss sie ** sortiert ** sein, ** das Einfügen und Löschen muss mit hoher Geschwindigkeit erfolgen ** und ** Elemente mit demselben Wert können vorhanden sein *. Wenn Sie auch * berücksichtigen, können Sie sehen, dass ** Farben Multiset ** verwenden sollte. Außerdem können Zahlen kleiner als XX links von Zahlen größer als XX (untere \ _Bindung) umformuliert werden, wenn sie in aufsteigender Reihenfolge sortiert werden. Darüber hinaus ist zu beachten, dass eine Angabe mit einem Iterator erforderlich ist, da beim Löschen mehrere Elemente gelöscht werden können, wenn dies durch einen Wert angegeben wird.

C ++ - Code

`abc134e.cc`


//Zur Compileroptimierung
#pragma GCC optimize("O3")
//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
//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(){
    ll n;cin>>n;
    vector<ll> a(n);REP(i,n)cin>>a[i];
    multiset<ll> colors;
    colors.insert(a[0]);
    FOR(i,1,n-1){
        auto ne=colors.lower_bound(a[i]);
        if(ne==colors.begin()){
            colors.insert(a[i]);
        }else{
            colors.erase(--ne);
            colors.insert(a[i]);
        }
    }
    cout<<SIZE(colors)<<endl;
}

[PYTHON] Wettbewerbsfähiges professionelles Andachtstagebuch 4. bis 10. Tag (28.06. Bis 04.07.)

Tag 4

Tag 5

Zeit genommen

Erwägung

abc137d.py

Tag 6

Zeit genommen

Fehlerursache

Erwägung

abc130e.py

Tag 7

Zeit genommen

Fehlerursache

Erwägung

abc131e.py

Tag 8

Tag 9

Tag 10

Zeit genommen

Erwägung

abc134e.cc

`abc137d.py`

`abc130e.py`

`abc131e.py`

`abc134e.cc`