[PYTHON] Codeforces Round # 665 (Div.2) Examen Bacha (8/23)

Les résultats de cette fois

Impressions de cette époque

Bien que je me sois trompé, j'ai pu passer à travers le problème C à une vitesse raisonnable, mais j'ai pu résoudre le problème D avec ** à moitié abandonné **. Du coup, j'ai pu le réussir après le concours, donc je le regrette. Comme je l'ai mentionné dans l'article précédent, je pense que les résultats s'amélioreront au fur et à mesure que les problèmes qui peuvent être résolus deviendront rapidement stables, alors je ferai de mon mieux. Je pense que cela changera si je résous environ 100 questions, donc je vais le supporter pendant environ un mois ** et essayer de bacha tous les jours.

Problème A

J'ai mal lu l'énoncé du problème, mais je suis content d'avoir pu récupérer.

Tout d'abord, il est illustré pour comprendre la relation de position entre ** A et B **. Il existe les deux modèles suivants.

Lorsque ** $ n <k $ **, le motif ② nécessite que les coordonnées de $ A $ soient $ k $ ou plus, le nombre d'étapes requis est donc d'au moins $ k-n $. De plus, dans le motif ①, les coordonnées de $ A $ sont $ k $, donc le nombre de pas requis est $ k-n $. Par conséquent, le nombre minimum d'étapes requises à ce moment est $ k-n $.

n \geqq ktemps, Dans le modèle de ②BÀOAAucune étape n'est nécessaire si vous le mettez au bon endroit entreBの座標ÀxPuis|OB|<|BA|étant donné que|OB-BA|=|OA|-2|OB|=n-2x=kEst établi. Donc,x=\frac{n-k}{2}Est vrai,xEst un entiernQuandkLes cotes et les cotes doivent correspondre. Donc,nQuandkLe nombre minimum d'étapes requis est de 0 lorsque les cotes et les cotes correspondent, et lorsque les paires et les cotes ne correspondent pasnから一つずらして一致させるこQuandで必要な最小のステップ数は1Quandなります。

A.py

for _ in range(int(input())):
    n,k=map(int,input().split())
    if n==k:
        print(0)
    elif n>k:
        if (n+k)%2==0:
            print(0)
        else:
            print(1)
    else:
        print(k-n)

Problème B

Vous devriez penser à la combinaison optimale dans l'ordre. Puisqu'il n'y a que trois types de $ a \ _i $, considérez la combinaison optimale pour chaque valeur.

(1) Lorsque $ a \ _i = 2 $ ** $ c \ _i $ prend une valeur maximale de 2 en la combinant avec $ b \ _i = 1 $ **. Combinez-en autant que vous le pouvez, mais s'il y a un surplus ($ z \ _1> y \ _2 $) ** le reste peut être combiné avec $ b \ _i = 2 $ **. En effet, $ a \ _i = 1 $ a un effet négatif sur la valeur totale lorsqu'il est combiné avec $ b \ _i = 2 . De plus, s'il y a plus de surplus ( z \ _1> z \ _2 $), vous pouvez soustraire le surplus du $ x \ _2 $ restant.

(2) Lorsque $ a \ _i = 1 $ Puisque $ c \ _i $ n'est pas positif, il doit être ** associé à $ b \ _i \ neq 2 $ afin qu'il ne soit pas négatif **. En d'autres termes, s'il peut être associé à $ x \ _2 + y \ _2 $ autre que la combinaison de (1), le montant du changement sera de 0. De plus, s'il y a un surplus ($ y \ _1> x \ _2 + y \ _2 $) même s'il est jumelé avec ceux-ci, il suffit de soustraire $ \ fois 2 $ (le nombre de paires) car cela a un effet négatif.

(3) Lorsque $ a \ _i = 0 $ Le résultat est 0 lorsqu'il est combiné avec n'importe quel $ b \ _i $, donc la valeur totale n'est pas affectée et peut être ignorée.

Si vous mettez soigneusement en œuvre le cas d'angle ci-dessus, ce sera comme suit. Veillez également à ne pas vous tromper dans l'ordre de soustraction **.

B.py

for _ in range(int(input())):
    x1,y1,z1=map(int,input().split())
    x2,y2,z2=map(int,input().split())
    ans=0
    #Premier à partir de z1
    if z1<=y2:
        ans+=(2*z1)
        y2-=z1
        z1=0
    else:
        ans+=(2*y2)
        z1-=y2
        y2=0
        if z1<=z2:
            z2-=z1
            z1=0
        else:
            z1-=z2
            z2=0
            x2-=z1
    #Vient ensuite y1(x1 n'a pas d'importance, c'est zéro de toute façon)
    if y1<=x2+y2:
        print(ans)
    else:
        print(ans-(y1-x2-y2)*2)

Problème C

(Mes pensées pendant le concours étaient assez appropriées et proches d'une solution de mensonge. ** Pensées avec une faible reproductibilité et précision **, donc j'écrirai une meilleure considération.)

Tout d'abord, examinez s'il est possible de changer les éléments qui sont dans des positions différentes ** à la position correcte par rapport au tableau trié **. À ce stade, si vous faites attention aux éléments avec des positions différentes et que certains d'entre eux ne sont pas des multiples de ** $ a \ _ {min} $ **, gcd est $ a \ _ entre cet élément et d'autres éléments. Cela ne peut jamais être {min} $. Par conséquent, s'il y a quelque chose qui n'est pas un multiple de $ a \ _ {min} $, vous pouvez afficher "NON".

Ensuite, considérons le cas où tous les éléments dans différentes positions sont des multiples de $ a \ _ {min} $. À ce stade, tous les éléments peuvent être déplacés vers la bonne position en passant par ** $ a \ _ {min} $ **. Autrement dit, supposons que $ a \ _ {min} $ soit dans $ i $ et que vous vouliez déplacer $ a \ _j $ vers $ k $. À ce moment, ① sélectionnez $ a \ _ {min} $ et $ a \ _ k $ et échangez ② $ a \ _ k (= a \ _ {min}) $ et $ a \ _ j $ pour permuter Et gcd peut être déplacé comme $ a \ _ {min} $. Par conséquent, il est possible de déplacer un élément différent à n'importe quelle position vers la bonne position en le déplaçant via $ a \ _ {min} $.

C.py

from math import gcd
def gcditer(x):
    ret=x[0]
    for i in range(1,len(x)):
        ret=gcd(ret,x[i])
    return ret
for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    b=sorted(a)
    #Vous devriez utiliser le même
    #Vous pouvez l'utiliser si c'est une fraction
    m=min(a)
    c=[a[i] for i in range(n) if a[i]!=b[i] or a[i]%m==0]
    if len(c)==0:
        print("YES")
    elif gcditer(c)==m:
        print("YES")
    else:
        print("NO")

Problème D

C'est un problème similaire, mais je n'avais pas l'habitude de régler ce problème **, donc j'ai passé trop de temps. En conséquence, j'ai trouvé la bonne solution, mais ** je n'ai pas eu assez de temps pour remarquer l'erreur d'index **.

Tout d'abord, considérons $ \ sum_ {i = 1} ^ {n-1} \ sum_ {j = i + 1} ^ {n} f (i, j) $, mais pensez honnêtement comme ça ** Pour une somme difficile **, il vaut mieux ** considérer la contribution de chaque élément **. En d'autres termes, vous devez considérer combien de fois chaque côté est inclus comme chemin simple (chemin ouvert) entre des sommets arbitraires (✳︎) et multiplier la valeur du chemin.

Ici, il est préférable de supposer que ** (✳︎) se trouve de n'importe quel côté ** et ** pour augmenter le nombre de côtés qui apparaissent plus souvent **. De plus, comme le nombre de 1 qui apparaissent sur le côté ** doit être aussi petit que possible **, les cas peuvent être classés comme suit.

① Lorsque $ m <n-1 $ Lors de la disposition des côtés dans l'ordre décroissant du nombre d'apparitions, $ p $ doit également être organisé par ordre décroissant et combiné. A ce moment, comme il n'y a pas de $ p $ correspondant aux arêtes $ n-1-m $ qui apparaissent moins fréquemment, 1 est combiné.

② Lorsque $ m \ geqq n-1 $ Lorsque les côtés sont disposés dans l'ordre décroissant du nombre d'apparitions, si $ p $ est disposé en ordre décroissant et combiné, il ne reste que $ m-n + 1 $ de $ p $, donc le côté avec le plus grand nombre d'apparitions est plus grand que $ p $. Combinez-le avec le produit de $ m-n + 2 $. De plus, pour les côtés restants, combinez les $ n-2 $ restants de $ p $ dans l'ordre décroissant.

Sur cette base, considérons (✳︎). Par conséquent, j'ai décidé de ** faire attention à un côté ** comme indiqué dans la figure ci-dessous.

Ensuite, en sélectionnant le point de départ et le point final du chemin simple à partir de chacun des ** cercles ** ci-dessus, vous pouvez créer un chemin simple qui inclut ce côté. De plus, si vous faites attention au cercle inférieur ici, vous pouvez voir qu'il ** constitue un sous-arbre **. En d'autres termes, il suffit de connaître le nombre de sommets du sous-arbre, qui peut être calculé par DFS ** car il peut être compté à partir de la direction des feuilles. De plus, le nombre de sommets dans le cercle supérieur peut être calculé par (nombre total de sommets) - (nombre de sommets dans le cercle inférieur). Le cercle inférieur est le sous-arbre qui ne contient pas la racine $ \ leftrightarrow $ Le sous-arbre dont la racine est le sommet éloigné de la racine $ \ leftrightarrow $ ** Le nombre de sommets inclus dans le sous-arbre parmi les deux sommets Il peut être reformulé comme le sous-arbre ** avec le plus petit nombre.

Par conséquent, (1) trouvez le nombre de sommets du sous-arbre enraciné à chaque sommet par DFS, (2) découvrez combien de fois chaque côté est inclus en utilisant (1), et (3) triez et donnez par ordre décroissant le nombre de fois que chaque côté est inclus. Triez les $ p $ par ordre décroissant et trouvez la valeur maximale en combinant les côtés et les nombres (rappelez-vous qu'il s'agit de $ mod \ 10 ^ 9 + 7 $). Ce sera comme.

D.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 long long 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 n,m;
vector<vector<ll>> edges;
vector<ll> dpc;
vector<vector<ll>> tree;
vector<ll> p;
vector<bool> check;

//Nombre de sommets du sous-arbre
ll dfs(ll i){
    //cout<<1<<endl;
    ll ret=1;
    check[i]=true;
    FORA(j,tree[i]){
        if(!check[j]){
            ret+=dfs(j);
        }
    }
    dpc[i]=ret;
    return ret;
}

signed main(){
    //Code pour accélérer la saisie
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    //Débordement quand même
    ll t;cin>>t;
    REP(_,t){
        cin>>n;
        dpc=vector<ll>(n,0);
        tree=vector<vector<ll>>(n);
        edges=vector<vector<ll>>(n-1);
        check=vector<bool>(n,false);
        REP(i,n-1){
            ll u,v;cin>>u>>v;u--;v--;
            tree[u].PB(v);
            tree[v].PB(u);
            edges[i]={u,v};
        }
        dfs(0);
        vector<ll> dp(n-1,0);
        REP(i,n-1){
            ll l,r;l=edges[i][0];r=edges[i][1];
            dp[i]=min(dpc[l],dpc[r])*(n-min(dpc[l],dpc[r]));
        }
        //FORA(i,dpc)cout<<i<<" ";
        sort(ALL(dp),greater<ll>());
        //Processus de calcul
        cin>>m;
        p=vector<ll>(m);
        REP(i,m){
            cin>>p[i];
        }
        sort(ALL(p),greater<ll>());
        vector<ll> calc(n-1,1);
        if(m<n-1){
            REP(i,m){
                calc[i]=p[i];
            }
        }else{
            //Peut-être que ce côté est différent
            //Je le réparerai plus tard
            REP(i,m-n+2){
                calc[0]*=p[i];
                calc[0]%=MOD;
            }
            FOR(i,m-n+2,m-1){
                calc[i-m+n-1]=p[i];
            }
        }
        ll ans=0;
        REP(i,n-1){
            ans+=(calc[i]*dp[i]);
            ans%=MOD;
        }
        cout<<ans<<endl;
    }
}

Après le problème E

Je vais sauter cette fois