Obwohl in den folgenden Fällen Nein ausgegeben werden sollte, wird im Fall des zweiten Codes Ja ausgegeben.

2
2 3
-1 -1

Der Grund dafür ist, dass ich die Anzahl der Paare, bei denen $ (A \ _i, B \ _i) = (-1, -1) $ in der Variablen ** $ ot $ ** gespeichert war, nicht berücksichtigt habe. (Siehe unten für $ ot $). Um dies zu berücksichtigen, ist $ dp [l] [r] anstelle von $ dp [l] [r]: = $ (ob $ [l, r] $ aus mehreren Intervallen besteht, die das Subjekt erfüllen) : = $ (** $ (A \ _i, B \ _i) = (-1, -1) $ in $ [l, r] $, der Mindestanzahl von Personen **). Und wenn es schließlich zu $ dp [0] [n-1] = ot $ wird, wird Ja ausgegeben, andernfalls wird Nein ausgegeben. Im obigen Fall ist $ ot = 1 $ und $ dp [0] [n-1] = 2 $, was nicht geeignet ist.

Impressionen

Ich konnte während des Wettbewerbs nicht daran denken, aber ich konnte es lösen, indem ich es überprüfte. Die Implementierung war schwer und WA wurde herausgegeben, aber als Ergebnis war ich froh, dass ich es selbst lösen konnte. Darüber hinaus ist das Folgende nicht die Richtlinie, wenn Sie unmittelbar nach dem Wettbewerb auflösen, sondern die Richtlinie, nachdem Sie den Abschnitt DP richtig verstanden haben. Der zweite Teil des Codes ist das. Darüber hinaus ist das Intervall DP ein DP **, das Informationen über das Intervall $ [l, r] $ als ** $ dp [l] [r] $ enthält. Weitere Informationen finden Sie in diesem Artikel.

Politik

Zuerst dachte ich im ersten Experiment, dass es in Abschnitte unterteilt werden könnte, in denen Personen mit demselben ** $ c \ _i $ kombiniert wurden **. Bei ** $ c \ _i $ bestimmt dieser Wert auch eindeutig die Länge des Intervalls ** (das habe ich während des Wettbewerbs nicht bemerkt). Wenn umgekehrt der Abschnitt $ [l, r] $ angegeben wird, werden daher die Stockwerke, auf denen die in dem Abschnitt enthaltenen Personen fahren, und die Stockwerke, auf denen sie absteigen, eindeutig wie folgt bestimmt ($ (r-l + 1) \ % \ 2 = 0 $ ist erforderlich). In der folgenden Abbildung gilt außerdem $ k = \ frac {r-k + 1} {2} $.

Wenn ** $ [l, r] $ angegeben wird, scheint $ O (n) $ zu zeigen, ob der Abschnitt wie in der obigen Abbildung gezeigt gilt **. Daher kann jedes $ l, r $ die Einrichtung dieses Intervalls anzeigen, und $ dp [l] [r]: = $ ($ [l, r] $ wird zu einem Intervall, das das Thema ** erfüllt. Sie können ein Array mit **) vorbereiten.

Außerdem möchten wir endlich $ dp [l] [r]: = $ finden (ob $ [l, r] $ aus mehreren Intervallen besteht, die das Thema erfüllen **), also * * Es ist notwendig, ein Urteil zu fällen, indem jeder Abschnitt zusammengeführt wird **.

Von oben können Sie ein $ O (n ^ 3) $ -Programm schreiben, das schnell genug ist.

Implementierung

Nachdem wir eine grundlegende Richtlinie haben, werden wir überlegen, diese umzusetzen.

** (1) Vorbereitung **

Empfängt die Informationen der angegebenen Person (Einstiegs- und Abstiegsetagen) und speichert sie in der Datenstruktur. Wenn Sie sowohl die Boarding-Etage als auch die absteigende Etage kennen, speichern Sie die Informationen im Array $ lr $ als "$ lr $ [Boarding-Etage] = absteigende Etage". Wenn nur der zu fahrende Boden bekannt ist, speichern Sie die Informationen im Array $ lx $ als "$ lx $ [board] = True". Wenn nur die absteigende Etage bekannt ist, speichern Sie die Informationen im Array $ rx $ als "$ rx $ [absteigende Etage] = True". Wenn Sie nicht wissen, auf welcher Etage Sie ein- oder aussteigen sollen, sollten Sie sie für Anpassungen verwenden. Speichern Sie diese Zahl also in einer Variablen namens $ ot $.

Außer wenn es überhaupt nicht möglich ist, Informationen als Vorbereitung zu lesen. Mit anderen Worten, ** wenn es zu "Boarding Floor > absteigender Floor" wird ** und ** wenn es mehrere gleiche Stockwerke ** gibt, wird das Thema eindeutig nicht erfüllt. Geben Sie in diesem Fall zuerst No aus und führen Sie das Programm aus. Ich bin fertig.

** (2) Finde $ dp [l] [r]: = $ (ob $ [l, r] $ ein Intervall ist, das das Thema erfüllt) **

Bestimmen Sie zunächst, ob $ [l, r] $ ein Intervall für $ l, r $ ist. Wenn ** $ (r-l) \% \ 2 = 0 $, gilt dies nicht **. Schauen Sie sich also den nächsten Abschnitt an. Außerdem beträgt der Unterschied zwischen der Etage, in der Personen aussteigen, und der Etage, in der Personen in diesem Abschnitt aussteigen, $ seglen = \ frac {r-l + 1} {2} $. Hier wird für jedes $ l \ leqq i \ leqq r-seglen $ beurteilt, ob $ i, i + seglen $ als Satz der Etage geeignet ist, auf der der Aufzug fährt, und der Etage, auf der der Aufzug in den folgenden 6 Fällen herunterfährt.

[1] $ lr [i]! = -1 $ und $ lr [i]! = I + seglen $

** Es ist nicht geeignet, da Sie auf einer anderen Etage aussteigen **.

[2] Wenn $ lx [i + seglen] $ True ist oder $ rx [i] $ True ist

Es ist nicht geeignet, da sich der Boden zum Aussteigen und der Boden zum Einsteigen gegenüberliegen.

[3] Wenn $ lr [i] = i + $ seglen

Das Ein- und Aussteigen ist angemessen.

[4] Wenn $ lx [i] $ wahr ist und $ rx [i + seglen] $ wahr ist

Es ist nicht geeignet, weil $ i, i + seglen $, das gepaart werden soll, ** auf dem Boden liegt, auf dem verschiedene Personen einsteigen, und auf dem Boden, auf dem sie aussteigen **.

[5] Wenn $ lx [i] $ True ist oder $ rx [i + seglen] $ True ist

Es ist angemessen, weil Sie richtig entscheiden können, welche Etage Sie verlassen oder betreten möchten.

[6] Wenn $ lx [i] $ falsch und $ rx [i + seglen] $ falsch ist

Dies ist angemessen, da Sie das in $ ot $ gespeicherte Paar verwenden können.

** (3) Finde $ dp [l] [r]: = $ (ob $ [l, r] $ aus mehreren Abschnitten besteht, die das Thema erfüllen) **

Führen Sie das soeben gefundene $ dp [l] [r] $ zusammen und prüfen Sie, ob $ dp [0] [2n-1] $ True ist.

Wenn zu diesem Zeitpunkt ** $ dp [l] [i] $ wahr und $ dp [i + 1] [r] $ wahr ist, dann ist $ dp [l] [r] $ wahr ** und willkürlich. Versuchen Sie $ l, r, i $. Sie können korrekt zusammenführen, indem Sie die Schleife von außen als $ l, r, i $ drehen.

C.py

n=int(input())
#B gegen A.
#Es ist langsam, hier mit einem Wörterbuch zu verwalten
lr,lx,rx,ot=[-1]*(2*n),[0]*(2*n),[0]*(2*n),0
ab=[[j-1 for j in list(map(int,input().split()))] for i in range(n)]

check=[0]*(2*n)
for i in range(n):
    if ab[i][0]!=-2:
        check[ab[i][0]]+=1
    if ab[i][1]!=-2:
        check[ab[i][1]]+=1
    #Wenn es umgekehrt ist
    if ab[i][0]!=-2 and ab[i][1]!=-2:
        if ab[i][0]>ab[i][1]:
            print("No")
            exit()

#Wenn 2 oder mehr enthalten sind
if any(i>1 for i in check):
    print("No")
    exit()

for i in range(n):
    if ab[i][0]==-2 and ab[i][1]==-2:
        ot+=1
    elif ab[i][0]==-2:
        rx[ab[i][1]]=1
    elif ab[i][1]==-2:
        lx[ab[i][0]]=1
    else:
        lr[ab[i][0]]=ab[i][1]

#dp[l][r]=([l,r]Minimum zu verwenden ot in)
#Wird es eine Position sein?
inf=10**12
dp=[[inf]*(2*n) for i in range(2*n)]
for l in range(2*n):
    #r ist größer als l
    for r in range(l+1,2*n):
        dp_sub=0
        #Existiert dieser Abschnitt sicherlich?(Wenn es nicht vorhanden ist, ändern Sie es so, dass es sofort unterbrochen wird(Ast))
        seglen=(r-l+1)//2
        #Die Länge des Abschnitts ist ungerade(2x+1)
        #Zu diesem Zeitpunkt ist der darin enthaltene Abschnitt x+1 Länge
        if (r-l)%2==1:
            for i in range(l,r-seglen+1):
                #Ich und Ich+seglen Paar
                if lr[i]!=-1:
                    if lr[i]!=i+seglen:
                        break
                elif lx[i]:
                    if not rx[i+seglen]:
                        dp_sub+=0
                    else:
                        break
                elif rx[i]:
                    break
                else:
                    #i+Auch das Muster, wo seglen in rx ist
                    if not rx[i+seglen]:
                        #Nur zu diesem Zeitpunkt(-1,-1)
                        dp_sub+=1
            #Wenn dieser Abschnitt die Bedingungen erfüllt
            else:
                dp[l][r]=dp_sub

#Finden Sie hier heraus, ob es Kandidaten in der DFS gibt
#Beenden Sie, wenn auch nur einer gefunden wird
#Wenn nicht, nein
#Überprüfen Sie, ob es passt
def dfs(i,otc):
    if otc>ot:
        return
    if i==2*n:
        if otc==ot:
            print("Yes")
            exit()
        else:
            return
    for j in range(i+1,2*n):
        if dp[i][j]!=inf:
            dfs(j+1,otc+dp[i][j])
dfs(0,0)
print("No")

C2.py

n=int(input())
#B gegen A.
#Es ist langsam, hier mit einem Wörterbuch zu verwalten
lr,lx,rx,ot=[-1]*(2*n),[0]*(2*n),[0]*(2*n),0
ab=[[j-1 for j in list(map(int,input().split()))] for i in range(n)]

check=[0]*(2*n)
for i in range(n):
    if ab[i][0]!=-2:
        check[ab[i][0]]+=1
    if ab[i][1]!=-2:
        check[ab[i][1]]+=1
    #Wenn es umgekehrt ist
    if ab[i][0]!=-2 and ab[i][1]!=-2:
        if ab[i][0]>ab[i][1]:
            print("No")
            exit()

#Wenn 2 oder mehr enthalten sind
if any(i>1 for i in check):
    print("No")
    exit()

for i in range(n):
    if ab[i][0]==-2 and ab[i][1]==-2:
        ot+=1
    elif ab[i][0]==-2:
        rx[ab[i][1]]=1
    elif ab[i][1]==-2:
        lx[ab[i][0]]=1
    else:
        lr[ab[i][0]]=ab[i][1]

#dp[l][r]=Wird es eine Position sein?
dp=[[False]*(2*n) for i in range(2*n)]
for l in range(2*n):
    #r ist größer als l
    for r in range(l+1,2*n):
        #Existiert dieser Abschnitt sicherlich?(Wenn es nicht vorhanden ist, ändern Sie es so, dass es sofort unterbrochen wird(Ast))
        seglen=(r-l+1)//2
        #Die Länge des Abschnitts ist ungerade(2x+1)
        #Zu diesem Zeitpunkt ist der darin enthaltene Abschnitt x+1 Länge
        if (r-l)%2==1:
            for i in range(l,r-seglen+1):
                #Ist lr anders,l,Ist es falsch in r eingegeben?
                if (lr[i]!=-1 and lr[i]!=i+seglen) or lx[i+seglen] or rx[i]:
                    #print(l,r,1)
                    break
                if lr[i]==i+seglen:
                    continue
                #Kann es gleichzeitig aufgenommen werden?
                if [lx[i],rx[i+seglen]].count(True)==2:
                    #print(l,r,2)
                    break
                elif [lx[i],rx[i+seglen]].count(True)==1:
                    continue
            #Wenn dieser Abschnitt die Bedingungen erfüllt
            else:
                dp[l][r]=True

#Von hier aus ist es in Ordnung, wenn Sie den Abschnitt DP zusammenführen und schließlich zusammenführen können
#dp[l][i],dp[i+1][r]Richtig, wenn beide wahr sind
for l in range(2*n):
    for r in range(l+1,2*n):
        for i in range(l+1,r):
            if dp[l][r]==False:
                if dp[l][i] and dp[i+1][r]:
                    dp[l][r]=True
                    break
#print(dp)
if dp[0][2*n-1]:
    print("Yes")
else:
    print("No")

D Problem

Ich verstehe nicht, wie man die richtige Antwort löst, aber ich werde es erklären, weil sie von einer konstanten Mehrfachbeschleunigung (✳︎1) bestanden wurde.

(Die Primzahl, für die Sie den angegebenen Rest geteilt finden möchten, wird unten als $ mod $ angezeigt.)

Grundlegende Überlegung

Wenn der Durchschnitt $ x $ beträgt, ist es typisch, dass ** der gesamte Betrag $ -x $ beträgt und die Anzahl der Teile verloren geht und der Rechenaufwand reduziert wird **. Betrachten Sie daher den Fall, in dem die Summe der folgenden Zahlen 0 ist, wenn der Durchschnitt $ x $ beträgt.

Betrachten Sie zu diesem Zeitpunkt die linke und die rechte Seite von 0 getrennt (✳︎2). Dann ist die linke Seite ganz negativ und die rechte Seite ist positiv. Wenn also beide positiv ausgerichtet sind, ** sind die Summe links und die Summe rechts gleich **. Außerdem ist die linke Seite die Summe bei der Auswahl von $ 1,2,…, x-1 $ und die rechte Seite die Summe bei der Auswahl von $ 1,2,…, nx $, also $ dp [i] [j]: Wenn = $ (die Zahl, wenn die Summe von 1 bis $ i + 1 $ $ j $ ist) im Voraus berechnet wird, ist die endgültige Lösungsausgabe $ x = $ 1 ~ $ n $. Sie kann durch den Berechnungsbetrag von $ O (n ^ 3k) $ durch Vergleich mit $ j $ berechnet werden.

DP-Teil

Hier ** über den vorberechneten DP **, aber da jede Zahl von 0 bis $ k $ $ k + 1 $ ausgewählt werden kann, gibt es $ k + 1 $ Übergänge. Mit anderen Worten, der Berechnungsbetrag beträgt $ O (n ^ 3k ^ 2) $ und das Maximum ist $ n ^ 3k ^ 2 = 10 ^ {10} $. Hier in der Antwort habe ich es durch die Technik des minimalen Folienwerts auf $ O (n ^ 3k) $ fallen lassen, aber ich habe es bestanden, indem ich die Geschwindigkeit um ein konstantes Vielfaches (✳︎1) erhöht habe.

Wenn Sie den DP wie zuvor setzen, ist der Übergang von $ dp [i-1] [j] $ wie folgt. Angenommen, Sie wählen nur $ l $ für $ i + 1 $ aus.

dp[i][j+l*(i+1)]+=dp[i-1][j]

Hier muss die Antwort mit dem Rest von $ mod $ ausgegeben werden, und gleichzeitig möchte ich $ dp [i] [j + l * (i + 1)] % = mod $ setzen, aber ** $ % $ Da die Berechnung einige Zeit in Anspruch nimmt und hier nur eine Addition durchgeführt wird **, muss $ mod $ nur subtrahiert werden, wenn $ dp [i] [j + l * (i + 1)] $ $ mod $ überschreitet. ist.

Ausgabeteil

Durch Berechnung von DP kann $ dp [i] [j] $ für jedes $ i, j $ erhalten werden. Berücksichtigen Sie also die Ausgabe.

Erstens, wenn $ x = 1, n $, gibt es 1 bis $ k $ $ k $, und ansonsten gibt es $ dp [n-2] [0] = 1 $. , Multipliziere und dividiere durch $ mod $, um den Rest zu finden.

In anderen Fällen, wenn der als Antwort zu erhaltende Wert als $ ans = 0 $ initialisiert wird, wenn nur ** $ x $ ausgewählt ist, ist ** dasselbe wie $ k $ und wenn ein anderer als ** $ x $ ausgewählt ist. ** ist $ dp [x-2] [j] \ * dp [nx-1] [j] $, wenn die Summe von links und rechts gleich $ j $ ist. Fügen Sie für jedes $ j (\ geqq 1) $ $ ans $ hinzu und finden Sie schließlich den Rest geteilt durch $ mod $. Um einen Überlauf zu vermeiden **, nehmen Sie $ mod $ jedes Mal, wenn Sie multiplizieren **. Und da es $ k + 1 $ Möglichkeiten gibt, $ x $ auszuwählen, können Sie schließlich $ ans \ * (k + 1) + k $ ausgeben.

(✳︎1)… Ich habe „$ % $ Berechnung durch $ mod “ und „** Die Summe ( j $), die Sie nicht sehen müssen **“ nicht sehen, für eine konstante Mehrfachbeschleunigung verwendet.

(✳︎2)… ** 0 Es ist leicht zu glauben, dass es zu Beginn um 1 zunimmt (oder abnimmt) **. Ich habe während des Wettbewerbs nicht an einen Fehler in meinem Kopf gedacht ...

D.cc

//Debug-Optionen:-fsanitize=undefined,address

//Compileroptimierung
#pragma GCC optimize("Ofast")

//Einschließen usw.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//Makro
//für Schleife
//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.
//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

signed main(){
    //Code zur Beschleunigung der Eingabe
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n,k,mod;cin>>n>>k>>mod;
    if(n==1){
        cout<<k<<endl;
        return 0;
    }else if(n==2){
        cout<<k<<endl;
        cout<<k<<endl;
        return 0;
    }
    ll ran=k*n*(n+1)/2;
    vector<vector<ll>> dp(n,vector<ll>(ran+1,0));
    REP(j,k+1){
        dp[0][j]=1;
    }
    FOR(i,1,n-1){
        REP(j,k*i*(i+1)/2+1){
            ll ran2=min(k+1,(ran-j)/(i+1)+1);
            REP(l,ran2){
                dp[i][j+l*(i+1)]+=dp[i-1][j];
                if(dp[i][j+l*(i+1)]>=mod)dp[i][j+l*(i+1)]-=mod;
            }
        }
    }
    cout<<k*dp[n-2][0]%mod<<endl;
    FOR(i,2,n-1){
        ll ans=0;
        FOR(j,1,ran){
            ans+=(dp[i-2][j]*dp[n-i-1][j]);
            ans%=mod;
        }
        cout<<((k+1)*ans+k)%mod<<endl;
    }
    cout<<k*dp[n-2][0]%mod<<endl;
}

Nach dem E-Problem

Ich werde diesmal nicht lösen.