[PYTHON] Codeforces Round # 646 (Div.2) Critique Bacha (9/6)

Les résultats de cette fois

Impressions de cette époque

C'est exactement la même impression qu'hier. J'ai pu résoudre le problème C avec une considération légère, mais j'ai perdu ma concentration à cause du ** problème E ** que je regardais YouTube pendant le bachacon. Je ne pense pas qu'il y ait d'autre moyen que de marcher moi-même, alors je ferai de mon mieux pour que cela fonctionne.

Aussi, bien que le problème E soit trop poussiéreux et trop particulier à propos de DP, il peut être résolu avec une méthode gourmande conçue, donc je pourrai l'identifier calmement.

Problème A

J'ai trop réfléchi et émis 1WA. C'est une réflexion. Afin de rendre le total impair, j'ai remarqué que ** des ajustements pairs et impairs peuvent être effectués en échangeant des paires pair et impair **. En raison de la condition que les paires et les impairs sont échangés, ** lorsque seuls les paires ou les impairs ** ne peuvent pas être échangés, il est donc nécessaire de séparer les cas. De plus, même lorsque $ x = n $, tous les éléments sont sélectionnés, il est donc impossible de les remplacer. Par conséquent, les cas suivants doivent être mis en œuvre.

(1) En cas de nombre pair uniquement Étant donné que la somme des éléments arbitraires est paire, Non est affiché. (2) En cas de nombre impair uniquement Si le nombre d'éléments sélectionnés est impair, la somme est impaire et Oui est affiché. Si le nombre d'éléments sélectionnés est pair, la somme est paire et Non est affiché. (3) Lorsque $ x = n $ Si la somme de tous les éléments est impaire, Oui est affiché, et s'il est pair, Non est affiché.

A.py

for _ in range(int(input())):
    n,x=map(int,input().split())
    a=list(map(int,input().split()))
    l,r=sum(a[i]%2==1 for i in range(n)),sum(a[i]%2==0 for i in range(n))
    if l==0:
        print("No")
    elif x==n:
        print(["No","Yes"][sum(a)%2])
    elif r==0:
        print(["No","Yes"][x%2])
    else:
        print("Yes")

Problème B

Paraphrasez la condition d'une chaîne qui n'inclut pas $ 010 $ ou $ 101 $ comme sous-colonne. Cela signifie que si la chaîne commence par 1, par exemple, la prochaine fois que 0 arrive, 1 n'apparaîtra pas après cela (même si elle commence par 0).

Par conséquent, on peut dire que la chaîne de caractères suivante est une chaîne de caractères qui satisfait le sujet.

0…01…1
1…10…0

Par conséquent, changez la chaîne de caractères d'origine en «0… 0», calculez le nombre d'opérations requis et gérez la différence entre les deux modèles d'augmentation de 1 du côté gauche et d'augmentation du côté droit de cet état. Cependant, vous pouvez calculer le nombre requis d'opérations pour chacune et trouver le nombre minimum d'opérations.

Aussi, en ce qui concerne la différence, si $ s [i] = "0" $, le nombre d'opérations doit être +1 et si $ s [i] = "1" $, le nombre d'opérations doit être -1. * Il a fallu beaucoup de temps pour le mettre en œuvre à cause de la considération. C'est une réflexion.

B.py

for _ in range(int(input())):
    s=input()
    n=len(s)
    c0,c1=s.count("1"),s.count("1")
    ans=min(c0,c1)
    #0...Changer de gauche quand 0
    for i in range(n):
        if s[i]=="0":
            c0+=1
        else:
            c0-=1
        ans=min(ans,c0)
    #De la droite
    for i in range(n-1,-1,-1):
        if s[i]=="0":
            c1+=1
        else:
            c1-=1
        ans=min(ans,c1)
    print(ans)

Problème C

C'est un problème simple si vous le voyez comme un bâillon. Je veux avoir la capacité de réfléchir à ces problèmes de manière stable.

Envisagez de supprimer la commande de celle-ci. À ce moment, ** lorsque l'ordre est de 1 ou moins à partir du début pour le sommet donné $ x $ **, le premier Ayush peut supprimer ce sommet, envisagez donc d'exclure ce cas.

Par conséquent, pour un sommet donné $ x $, l'ordre est supérieur ou égal à 2. De plus, si l'ordre de $ x $ devient 1, $ x $ sera sélectionné par l'autre partie, donc ** évitez cet état **. De plus, j'ai remarqué que la défaite est confirmée lorsque les deux sommets s'étendent du sommet $ x $ comme indiqué dans la figure ci-dessous.

De ce qui précède, on peut dire que lorsque l'ordre des sommets $ x $ est de 2 ou plus, ** l'un l'autre prend l'action optimale et arrive enfin à la forme indiquée dans la figure ci-dessus ** (** faites attention à l'état final! * *)à propos de ça. Par conséquent, lorsque l'ordre du sommet $ x $ est égal ou supérieur à 2, la victoire ou la défaite ne dépend que du nombre de sommets $ n $, et non de la forme de l'arbre. De plus, s'il reste trois sommets à la fin, vous perdez, donc si $ n $ est impair, vous perdez le premier Ayush, et si $ n $ est pair, vous perdez le deuxième Ashish.

C.py

name=["Ayush","Ashish"]
for _ in range(int(input())):
    n,x=map(int,input().split())
    check=0
    for i in range(n-1):
        u,v=map(int,input().split())
        if u==x or v==x:
            check+=1
    if check==0 or check==1:
        print(name[0])
    else:
        print(name[n%2])

Problème D

Je ne l'ai pas résolu parce que c'est interactif.

Problème E

C'est un problème qui peut être résolu si vous vous concentrez comme vous pouvez le voir dans l'impression. Je ne pense pas que je peux améliorer ma mentalité et ma concentration de ma vie quotidienne, alors j'aimerais l'améliorer. De plus, dans ce problème, quand je l'ai écrit dans PyPy en utilisant la récurrence, c'était MLE, donc lors de l'écriture de la récurrence dans Codeforces, j'aimerais l'écrire en C ++ **.

Premièrement, si ** $ b [i] = c [i] $, il n'est pas nécessaire de changer **, donc mélangez dans l'arborescence partielle pour remplacer ceux de $ b [i] \ neq c [i] $. Je le ferai. A ce moment, un type (type 0) dans lequel $ b [i] = 0 $ et $ c [i] = 1 $ et un type (type 0) dans lequel $ b [i] = 1 $ et $ c [i] = 0 $ Il existe deux types de 1), et ** si ces sommes ne sont pas égales ** ne peut pas satisfaire le sujet. De plus, s'ils sont égaux l'un à l'autre, le sujet est toujours satisfait.

Sur cette base, ** la chose la plus simple à demander est de sélectionner un sous-arbre qui considère le sommet 1 comme le sommet. Cependant, dans certains cas, il est préférable de sélectionner un sous-arbre plus proche des feuilles et de le mélanger. ** En généralisant ce qui précède, si le coût du parent d'un certain sommet est plus petit **, le coût de ce parent peut être utilisé comme coût de ce sommet **. Par conséquent, il est possible de faire DFS (ou BFS) et de mettre à jour à partir des sommets supérieurs.

À partir de ce qui précède, ** le coût de chaque sommet a été mis à jour **, et le coût peut être défini de sorte qu'il diminue de manière monotone de la racine à la feuille **. Par conséquent, vous pouvez avec gourmandise ** mélanger les feuilles sous cette source. En d'autres termes, le nombre de sommets de type $ i $ contenus dans le sous-arbre est $ c \ _i $, et le nombre de sommets pouvant être mélangés pour correspondre est $ 2 \ times min (c \ _0, c \ _1) $. Faites-le dans l'ordre du sommet le plus proche de la feuille. De plus, ** l'un des types peut ne pas être mis en correspondance par le sous-arbre seul **, donc mélangez le sous-arbre avec son parent comme racine pour correspondre. De plus, comme il est effectué dans l'ordre à partir du sommet le plus proche de la feuille, il est implémenté ici par ** DFS **.

E.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 1000000000000000 //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

vector<ll> a,b,c;
vector<vector<ll>> tree;
vector<bool> check;
vector<ll> ans;

void dfs1(ll i,ll m){
    FORA(j,tree[i]){
        if(!check[j]){
            check[j]=true;
            a[j]=min(a[j],m);
            dfs1(j,a[j]);
        }
    }
}

pair<ll,ll> dfs2(ll i){
    ll ret=0;
    pair<ll,ll> now={(b[i]==0 and c[i]==1),(b[i]==1 and c[i]==0)};
    FORA(j,tree[i]){
        if(!check[j]){
            check[j]=true;
            pair<ll,ll> d=dfs2(j);
            ret+=ans[j];
            now.F+=d.F;
            now.S+=d.S;
        }
    }
    ret+=(min(now.F,now.S)*a[i]*2);
    ans[i]=ret;
    return MP(now.F-min(now.F,now.S),now.S-min(now.F,now.S));
}

signed main(){
    //Code pour accélérer la saisie
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n;cin>>n;
    a=vector<ll>(n);b=vector<ll>(n);c=vector<ll>(n);
    REP(i,n)cin>>a[i]>>b[i]>>c[i];
    tree=vector<vector<ll>>(n);
    REP(i,n-1){ll u,v;cin>>u>>v;tree[u-1].PB(v-1);tree[v-1].PB(u-1);}
    if(accumulate(ALL(b),0)!=accumulate(ALL(c),0)){cout<<-1<<endl;return 0;}
    check=vector<bool>(n,false);check[0]=true;
    dfs1(0,a[0]);
    ans=vector<ll>(n,INF);
    check=vector<bool>(n,false);check[0]=true;
    dfs2(0);
    cout<<ans[0]<<endl;
}

Après problème F

Je vais sauter cette fois