[PYTHON] Yukicoder-Wettbewerb 263 Bewertung

Ergebnis

Impressionen

Ich bin wie beim letzten Mal gestorben. Es ist ein Problem, das immer gelöst werden sollte, wenn ich sterbe, und ich habe das Gefühl, den Eckfall vergessen oder ihn in der Implementierung abgehört zu haben **. ** Wann wird es möglich sein, die Ursache während des Wettbewerbs ruhig zu analysieren?

Problem A

A^2 -B^2 =N \leftrightarrow (A-B)(A+B)=N

Da die Formel wie oben transformiert werden kann und ** $ AB $ und $ A + B $ gerade und ungerade übereinstimmen , ist $ (AB, A + B) = $ (gerade, gerade), (ungerade, ungerade) Es sollte sein. Zu diesem Zeitpunkt muss das erstere ein Vielfaches von 4 sein und das letztere muss eine ungerade Zahl sein. Da $ A-B <A + B $ ist und $ N = 4,1 $ nicht gilt ( Eckfall! **), ist dies wie folgt.

A.py

n=int(input())
if n%2==1:
    if n==1:
        print(-1)
    else:
        print(1)
elif n%4==0:
    if n==4:
        print(-1)
    else:
        print(1)
else:
    print(-1)

B-Problem

Ich habe in den letzten Tagen viele DP-Probleme gelöst, sodass ich sie ziemlich schnell lösen konnte. Ich bedauere jedoch, dass ich einen Fehler im ** Index gemacht habe und WA ** geworden bin.

Bei diesem Problem können Sie sehen, dass Sie sich die Süßigkeiten ** in der Reihenfolge ** ansehen sollten. ** kann jedoch nicht mit der gierigen Methode ** ausgeführt werden, daher wird der folgende DP festgelegt.

$ dp [i] [j]: = $ (Maximales Glück bei der Auswahl einer ungeraden Anzahl (oder geraden Anzahl) von Süßigkeiten, wenn bis zur $ i $ -ten Süßigkeit aufgenommen wird)

Wenn jedoch $ j = 0 $ ist, ist die Zahl ungerade, und wenn $ j = 1 $ ist, ist die Zahl ungerade.

Zu diesem Zeitpunkt ist der Übergang nicht schwierig und wie folgt.

(1) Aktualisiere $ dp [i + 1] [0] $

Wenn Sie nicht $ a [i + 1] $ wählen, $ dp [i] [0] $ Bei Auswahl von $ a [i + 1] $, $ dp [i] [1] + a [i + 1] $

(2) Aktualisiere $ dp [i + 1] [0] $

Wenn Sie nicht $ a [i + 1] $ wählen, $ dp [i] [1] $ Bei Auswahl von $ a [i + 1] $, $ dp [i] [0] -a [i + 1] $

B.py

n,m=map(int,input().split())
a=[sum(list(map(int,input().split()))) for i in range(n)]
dp=[[0,0] for i in range(n)]
dp[0][0]=a[0]
for i in range(n-1):
    #Iss oder nicht
    dp[i+1][0]=max(dp[i][0],dp[i][1]+a[i+1])
    dp[i+1][1]=max(dp[i][1],dp[i][0]-a[i+1])
print(max(dp[n-1]))

C-Problem

Ich habe den Fehler gemacht, nur an eine der Gleichungen zu denken, die zuerst herauskamen, und dann die richtige Richtlinie erstellt, aber ich hatte das Gefühl, dass die ** Implementierung problematisch ** und infolgedessen ** die Implementierung chaotisch ** Ich konnte keinen Fall von WA bekommen.

Ich war am Anfang so ungeduldig, dass ich keine Richtlinie zusammenstellen konnte, also möchte ich mich dort beruhigen. Heutzutage ist meine Mentalität so schrecklich, dass ich es überhaupt nicht kann ...

Wenn Sie das Problem in eine Formel einfügen, lautet es zunächst $ A \ mal B = X-C, A \ mal C = Y-B $. Wenn dies transformiert wird, ist $ (A-1) (B-C) = X-Y, (A + 1) (B + C) = X + Y $. Um die Implementierung zu vereinfachen, nehmen wir an, dass $ X \ geqq Y $ gilt, und wenn dies nicht der Fall ist, tauschen Sie aus.

Wenn Sie sich auf $ (A-1) (BC) = XY $ konzentrieren, ist $ A-1 $ ein Bruchteil von $ XY $, also ist ** $ O (\ sqrt {X}) $ $ A $. Kandidaten können aufgezählt werden **. Wenn $ A $ festgelegt ist, gilt $ B-C = \ frac {X-Y} {A-1}, B + C = \ frac {X + Y} {A + 1} $. Wenn Sie also $ v = \ frac {XY} {A-1}, w = \ frac {X + Y} {A + 1} $ setzen, dann ist $ B = \ frac {v + w} {2}, C. = \ frac {wv} {2} $ gilt. Zu diesem Zeitpunkt ist $ B, C $ möglicherweise keine Ganzzahl, aber wandeln Sie sie in einen Ganzzahltyp um und suchen Sie $ B, C $. Überprüfen Sie für dieses $ B, C $, ob $ (A-1) (BC) = XY, (A + 1) (B + C) = X + Y $ gilt, und zählen Sie die Zahl. ..

Da die obige Diskussion auf der Annahme von $ X \ neq Y $ basiert, ist es auch notwendig, den Fall von ** $ X = Y $ separat zu betrachten **. Wenn $ X = Y $, von $ (A-1) (B-C) = 0 \ leftrightarrow A = 1 \ oder \ B = C $, können Sie die Fälle wie folgt teilen.

(1) Wenn $ A = 1 $ Von $ (A + 1) (B + C) = X + Y \ linker rechter Pfeil B + C = X $, $ (B, C) = (1, X-1), (2, X-2),…, Es gibt $ X-1 $ Straßen von (X-1,1) $.

(2) Wenn $ B = C $ Von $ (A + 1) (B + C) = X + Y \ linker rechter Pfeil (A + 1) B = X $ ist $ A + 1 $ ein Bruchteil von $ X $ und kann in der vorherigen Diskussion verwendet werden. .. Wenn jedoch ** $ \ frac {X} {A + 1} $ zu 1 oder 2 wird, müssen die Fälle ** sorgfältig getrennt werden, sie wurden jedoch separat als ** Eckfall ** verarbeitet. ..

C.cc

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

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

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

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


ll check_divisors(ll x,ll y){
    ll ret=0;
    ll n=x-y;
    vector<ll> divisors;//Ein Array, das die Brüche speichert
    FOR(i,1,sqrt(n)){
        if(n%i==0){
            divisors.PB(i);
            if(i!=n/i){
                divisors.PB(n/i);
            }
        }
    }
    //a-Kandidat für 1
    FORA(i,divisors){
        ll a,b,c;a=i+1;
        ll v,w;v=n/(a-1);w=(x+y)/(a+1);
        b=(v+w)/2;c=(w-v)/2;
        if(b>0 and c>0 and (a-1)*(b-c)==(x-y) and (a+1)*(b+c)==(x+y)){
            ret++;        
        }
    }
    return ret;
}

ll check_divisors2(ll x,ll y){
    ll ret=x-1;
    FOR(i,3,sqrt(x)){
        if(x%i==0){
            if(i!=ll(x/i)){
                ret+=2;
            }else{
                ret++;
            }
        }
    }
    if(x%2==0){
        if(2!=ll(x/2) and x!=2){
            ret++;
        }
    }
    if(x!=1 and x!=2)ret++;
    return ret;
}

signed main(){
    //Code zur Beschleunigung der Eingabe
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll s;cin>>s;
    REP(i,s){
        ll x,y;cin>>x>>y;
        if(x<y)swap(x,y);
        if(x==y){
            cout<<check_divisors2(x,y)<<endl;
        }else{
            cout<<check_divisors(x,y)<<endl;
        }
    }
}

Nach D Problem

Ich werde diesmal nicht lösen.