[PYTHON] concours yukicoder 263 avis

résultat

Impressions

Je suis mort comme la dernière fois. C'est un problème qui devrait toujours être résolu quand je meurs, et j'ai l'impression d'avoir oublié le cas du coin ou de l'avoir mis sur bug dans l'implémentation **. ** Quand sera-t-il possible d'analyser calmement la cause pendant le concours?

Problème A

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

Puisque la formule peut être transformée comme ci-dessus et que la régularité de ** $ AB $ et $ A + B $ correspond , $ (AB, A + B) = $ (pair, pair), (impair, impair) Ça devrait être. En outre, à ce stade, le premier doit être un multiple de 4 et le second doit être un nombre impair. Aussi, puisque $ A-B <A + B $, si $ N = 4,1 $ ne tient pas ( case du coin! **), ce sera comme suit.

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)

Problème B

J'ai résolu beaucoup de problèmes de DP ces derniers jours, donc j'ai pu les résoudre assez rapidement. Cependant, c'est le reflet que j'ai fait une erreur dans l'indice ** et que je suis devenu WA **.

Pour ce problème, vous pouvez voir que vous devriez regarder les bonbons ** dans l'ordre **. Cependant, ** ne peut pas être effectué par la méthode gourmande **, donc le DP suivant est défini.

$ dp [i] [j]: = $ (Bonheur maximum lors de la sélection d'un nombre impair (ou pair) de bonbons lors de la prise jusqu'au $ i $ e bonbon)

Cependant, lorsque $ j = 0 $, le nombre est impair, et lorsque $ j = 1 $, le nombre est impair.

À ce stade, la transition n'est pas difficile et se déroule comme suit.

(1) Mettre à jour $ dp [i + 1] [0] $

Si vous ne choisissez pas $ a [i + 1] $, $ dp [i] [0] $ Lors du choix de $ a [i + 1] $, $ dp [i] [1] + a [i + 1] $

(2) Mettre à jour $ dp [i + 1] [0] $

Si vous ne choisissez pas $ a [i + 1] $, $ dp [i] [1] $ Lors du choix de $ 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):
    #Manger ou pas
    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]))

Problème C

J'ai fait l'erreur de penser à une seule des équations qui sont apparues en premier, puis j'ai fait la bonne politique, mais j'ai senti que ** la mise en œuvre était gênante **, et par conséquent j'ai fait ** une mise en œuvre désordonnée **, donc la dernière Je n'ai pas pu avoir un seul cas de WA.

J'étais tellement impatient au début que je ne pouvais pas mettre en place une politique, alors je veux être ** calme ** là-bas. Ces jours-ci, ma mentalité est si terrible que je ne peux pas du tout le faire ...

Premièrement, si vous mettez le problème dans une formule, ce sera $ A \ fois B = X-C, A \ fois C = Y-B $. Lorsque cela est transformé, $ (A-1) (B-C) = X-Y, (A + 1) (B + C) = X + Y $. Aussi, pour rendre l'implémentation plus facile, supposons que $ X \ geqq Y $ tient, et si ce n'est pas le cas, échangez.

En se concentrant sur $ (A-1) (BC) = XY $, $ A-1 $ est une fraction de $ XY $, donc ** $ O (\ sqrt {X}) $ est $ A $. Les candidats peuvent être énumérés **. De plus, quand $ A $ est fixe, $ B-C = \ frac {X-Y} {A-1}, B + C = \ frac {X + Y} {A + 1} $ tient. Par conséquent, si vous définissez $ v = \ frac {XY} {A-1}, w = \ frac {X + Y} {A + 1} $, alors $ B = \ frac {v + w} {2}, C = \ frac {wv} {2} $ tient. À ce stade, $ B, C $ peut ne pas être un entier, mais le transtyper en un type entier et trouver $ B, C $. Pour ce $ B, C $, vérifiez si $ (A-1) (BC) = XY, (A + 1) (B + C) = X + Y $ tient, et comptez le nombre. ..

De plus, puisque la discussion ci-dessus est basée sur l'hypothèse de $ X \ neq Y $, il est nécessaire de considérer le cas de ** $ X = Y $ séparément **. Lorsque $ X = Y $, à partir de $ (A-1) (B-C) = 0 \ leftrightarrow A = 1 \ ou \ B = C $, vous pouvez diviser les observations comme suit.

(1) Lorsque $ A = 1 $ Depuis $ (A + 1) (B + C) = X + Y \ leftrightarrow B + C = X $, $ (B, C) = (1, X-1), (2, X-2),…, Il y a des rues $ X-1 $ de (X-1,1) $.

(2) Lorsque $ B = C $ De $ (A + 1) (B + C) = X + Y \ leftrightarrow (A + 1) B = X $, $ A + 1 $ est une fraction de $ X $ et peut être utilisé dans la discussion précédente. .. Cependant, lorsque ** $ \ frac {X} {A + 1} $ devient 1 ou 2, il est nécessaire de séparer soigneusement les cas **, mais il a été traité séparément comme un ** cas d'angle **. ..

C.cc

//Options de débogage:-fsanitize=undefined,address

//Optimisation du compilateur
#pragma GCC optimize("Ofast")

//Inclure etc.
#include<bits/stdc++.h>
using namespace std;
typedef int ll;

//macro
//pour boucle
//L'argument est(Variables dans la boucle,Amplitude de mouvement)Ou(Variables dans la boucle,Premier numéro,Nombre d'extrémités)、のどちらOu
//Les variables de boucle sans D sont incrémentées de 1 et les variables de boucle avec D sont décrémentées de 1.
//FORA est une gamme de déclaration(Si c'est difficile à utiliser, effacez-le)
#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 est un conteneur tel que vector
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//constant
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 100000 //10^5:Portée maximale de la baie
//Abréviation
#define PB push_back //Insérer
#define MP make_pair //constructeur de paires
#define F first //Le premier élément de paire
#define S second //Le deuxième élément de paire


ll check_divisors(ll x,ll y){
    ll ret=0;
    ll n=x-y;
    vector<ll> divisors;//Un tableau qui stocke les fractions
    FOR(i,1,sqrt(n)){
        if(n%i==0){
            divisors.PB(i);
            if(i!=n/i){
                divisors.PB(n/i);
            }
        }
    }
    //a-Candidat pour 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 pour accélérer la saisie
    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;
        }
    }
}

Problème après D

Je ne résoudrai pas cette fois.