[PYTHON] Codeforces Round # 660 (Div.2) Critique Bacha (8/4)

Les résultats de cette fois

Impressions de cette époque

J'ai résolu trois questions cette fois. L'implémentation du problème C était lourde, mais j'ai pu y répondre correctement en organisant la politique.

J'avais déjà résolu le problème D en organisant l'implémentation, j'aimerais donc continuer à en être conscient.

Problème A

$ X $ est représenté par la somme de quatre entiers positifs différents (dont au moins trois sont $ près de \ primer $), mais ** le minimum $ presque \ primer $ pour représenter autant de $ x $ que possible. J'ai décidé de chercher **. $ near \ primer $ est un nombre qui peut être exprimé en multipliant deux nombres premiers, et $ 6,10,14 $ est les trois plus petits $ near \ primer $. Par conséquent, si $ x $ est inférieur ou égal à 30 $ (= 6 + 10 + 14) $, les quatre entiers du sujet ne peuvent pas être construits.

De plus, si vous choisissez $ 6,10,14 $ lorsque $ x> 30 $, vous ne pouvez pas choisir $ 6,10,14 $ comme autre nombre à choisir, mais cette méthode lorsque $ x = 36,40,44 $ Dans le cas de, les quatre entiers du sujet ne peuvent pas être construits, mais en choisissant $ 15 $ au lieu de $ 14 $, les quatre entiers du sujet peuvent également être construits dans le cas de $ x = 36,40,44 $.

A.py

for i in range(int(input())):
    n=int(input())
    if n<=30:
        print("NO")
    elif n==36:
        print("YES")
        print("6 10 15 5")
    elif n==40:
        print("YES")
        print("6 10 15 9")
    elif n==44:
        print("YES")
        print("6 10 15 13")
    else:
        print("YES")
        print("6 10 14"+f" {n-30}")

Problème B

Pour résumer le problème, étant donné $ n $, considérons un binaire $ k $ dans lequel chaque chiffre du nombre décimal $ n $ chiffre $ x $ est concaténé en notation binaire, et le $ k $ Il constitue le plus petit $ x $ en maximisant le nombre $ r $, en ignorant les chiffres $ n $ inférieurs. De plus, lors de la conversion en notation binaire, elle n'est pas complétée par des 0.

Tout d'abord, il va de soi que $ x $ devrait être de 99 $… 99 $ ** pour maximiser ** $ r $. Cependant, à ce moment, $ x $ devient le maximum. Par conséquent, vous devez ** rendre les chiffres $ n $ inférieurs de $ k $ à ignorer ** aussi petits que possible. De plus, puisque 9 $ est dans le chiffre de 4 $ lorsqu'il est exprimé en binaire, la seule façon de réduire $ x $ tout en gardant $ r $ au maximum est de remplacer 9 $ par 8 $. Par conséquent, le chiffre de $ x $ correspondant au chiffre inférieur $ n $ du $ k $ ignoré doit être changé en $ 8 $, et le nombre de chiffres qui peuvent être remplacés par $ 8 $ est déterminé par la valeur de $ n % 4 $. Je vais l'examiner séparément.

D'après ce qui précède, lorsque $ n % 4 = 0 $, le chiffre inférieur $ [\ frac {n} {4}] $ de $ x $ est remplacé par $ 8 $, et lorsque $ n % 4 \ neq 0 $, $ Le chiffre inférieur $ [\ frac {n} {4}] + 1 $ de x $ peut être de 8 $, et le code ressemble à ceci:

B.py

for _ in range(int(input())):
    n=int(input())
    l=n//4 if n%4==0 else n//4+1
    ans="9"*(n-l)+"8"*(l)
    print(ans)

Problème C

Tout d'abord, considérons ** un arbre enraciné avec des racines dans la capitale (1 du haut) **. Sur cette base, le nombre de personnes qui se sentent bien et de ceux qui se sentent mal est décidé pour que $ h_i, p_i $ se maintienne à n'importe quel sommet, mais il s'avère qu'il est difficile de décider ** dans les nuages sombres **. Il est également difficile de gérer ** les humeurs changeantes au milieu du bord ** (la contribution à $ h_i $ passe de +1 à -1). Par conséquent, dans un tel cas, ** suivez l'arbre à partir de la direction racine ou de la direction feuille **. ** BFS est souvent utilisé dans le premier cas, et DFS ** est souvent utilisé dans le second cas. De plus, dans ce numéro, il semblait que ** le nombre de personnes qui se sentent bien et le nombre de personnes qui se sentent mal dans les feuilles peuvent être déterminés de manière unique **, j'ai donc décidé de faire DFS.

Ici, en supposant que le ** $ i $ ème apex soit une feuille **, et en laissant le nombre de bonnes et de mauvaises personnes passant par cet apex respectivement $ c et d $, le nombre de personnes passant par cet apex est Puisque seuls ceux qui vivent dans cette ville, $ cd = h \ _i, c + d = p \ _i $ est valable. Quand ceci est transformé en une expression, il devient $ c = \ frac {p_i + h_i} {2}, d = \ frac {p_i-h_i} {2} $, et si $ c et d $ valent à la fois 0 et un entier, le sujet est Rencontrer.

Ensuite, en supposant que le ** $ i $ e sommet n'est pas une feuille **, ** DFS recherche dans l'ordre à partir du sommet le plus proche de la feuille **, de sorte que chaque sommet inclus dans le sous-arbre enraciné à ce sommet Nous savons déjà combien de personnes se sentent bien et mal. Ici, si vous retournez une paire de bonnes et de mauvaises personnes qui passent par chaque sommet avec la ** fonction récursive DFS **, elle passera par le $ i $ ème sommet mais au $ i $ ème sommet. Vous pouvez trouver le nombre de bonnes et de mauvaises personnes qui ne vivent pas en premier et les définir comme $ x et y $, respectivement.

A ce moment, si le nombre de bonnes et de mauvaises personnes passant par le $ i $ ème pic est respectivement $ c et d $, alors $ cd = h \ _i, c + d = p \ _i + x + y $ Est établi. Lorsque cela est transformé en équation, cela devient $ c = \ frac {p_i + x + y + h_i} {2}, d = \ frac {p_i + x + y-h_i} {2} $. De plus, $ c et d $ valent à la fois 0 et des entiers, et ** une personne qui se sent malade une fois ne se sent pas mieux **, donc $ c <x $ peut être obtenue. En aucune façon.

Vous pouvez trouver une réponse de levier qui vérifie tous les sommets en exécutant DFS, en faisant attention au cas des feuilles et des non-feuilles. De plus, s'il y a des sommets qui ne tiennent pas, la fonction récursive renvoie une paire de (-1, -1).

Questions importantes cette fois

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 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
#define CANT MP(ll(-1),ll(-1))

pair<ll,ll> dfs(vector<ll> &p,vector<ll> &h,vector<bool> &seen,vector<vector<ll>> &graph,ll v) {
    seen[v] = true;
    bool f=false;
    //Une paire de bons et de mauvais
    pair<ll,ll> x(0,0);
    for (auto ne:graph[v]) { 
        if(seen[ne])continue;
        f=true;
        pair<ll,ll> y=dfs(p,h,seen,graph,ne);
        if(y==CANT)return CANT;
        x.F+=y.F;x.S+=y.S;
    }
    //cout<< x.F << " " << x.S << " " << v << endl;
    if(f){
        if(abs(p[v]+x.F+x.S)%2!=abs(h[v])%2){
            //cout<<-1<<endl;
            return CANT;
        }else{
            ll c=(p[v]+x.F+x.S+h[v])/2;ll d=(p[v]+x.F+x.S-h[v])/2;
            if(c<0 or d<0 or c<x.F){
                //cout<<-2<<endl;
                return CANT;
            }else{
                return MP(c,d);
            }
        }
    }else{
        if(abs(p[v]%2)!=abs(h[v]%2)){
            //cout<<-3<<endl;
            return CANT;
        }else{
            ll c=(p[v]+h[v])/2;ll d=(p[v]-h[v])/2;
            if(c<0 or d<0){
                //cout<<-4<<endl;
                return CANT;
            }else{
                return MP(c,d);
            }
        }
    }
}

signed main(){
    //Code pour accélérer la saisie
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll t;cin>>t;
    REP(_,t){
        ll n,m;cin>>n>>m;
        vector<bool> seen(n,false);
        vector<vector<ll>> graph(n);
        vector<ll> p(n);REP(i,n)cin>>p[i];
        vector<ll> h(n);REP(i,n)cin>>h[i];
        REP(i,n-1){
            ll x,y;cin>>x>>y;
            graph[x-1].PB(y-1);
            graph[y-1].PB(x-1);
        }
        pair<ll,ll> z=dfs(p,h,seen,graph,0);
        if(z==CANT){
            cout<<"NO"<<endl;
        }else{
            cout<<"YES"<<endl;
        }
    }
}

Problème D

Comme il me restait peu de temps, j'étais impatient et j'avais une politique rude. Je ne veux pas trop m'inquiéter du temps restant.

Pendant le concours, j'ai pensé que je choisirais avidement un grand nombre, mais ** si l'ordre est pertinent, pensez à un graphe orienté ** pour améliorer les perspectives.

Dans ce problème, lors de la sélection de $ i $ et de l'exécution d'une opération, $ a [i] $ est ajouté à $ a [b [i]] $ ainsi qu'à $ ans $, mais $ a [i] $ S'il est négatif, vous pouvez opérer dans l'ordre de $ b [i] \ rightarrow i $ plutôt que $ i \ rightarrow b [i] $. Inversement, si $ a [i] $ est positif, vous pouvez opérer avec $ i \ rightarrow b [i] $.

J'y ai pensé et j'ai essayé avidement de choisir parmi un grand nombre de points positifs, mais ** chaque $ a [i] $ n'est pas optimal car la valeur peut changer **. Cependant, à l'inverse, vous pouvez choisir $ a [i] $ dont la valeur ne change pas **. Par conséquent, si vous considérez un graphe orienté avec chaque nombre comme un sommet pondéré, la valeur ne changera pas pour les ** sommets avec 0 côtés provenant d'autres sommets ** (sommets avec 0 sortie, point source). Hmm.

Par conséquent, considérons un graphe orienté en supposant que $ b [i] $ reçu en entrée indique le bout du côté, et faites le jugement suivant à partir du point source ($ \ car $ ** Puisqu'il s'agit d'un graphe en circuit non fermé dirigé, le point source est toujours Existe **). Quand $ a [i] \ geqq 0 $, ** les poids des autres sommets peuvent être augmentés **, insérez donc un [i] dans f et connectez-vous au $ i $ ème sommet. Ajoutez $ a [i] $ au poids. Lorsque $ a [i] <0 $, ** les poids des autres sommets ne peuvent pas être augmentés **, insérez donc simplement un [i] dans s. De plus, ** l'ordre des sommets sur lesquels le jugement est fait est réduit de un **, et celui d'ordre 0 est utilisé comme candidat pour un nouveau sommet. Puisqu'il s'agit d'un graphe en circuit non fermé dirigé, vous pouvez vérifier n'importe quel sommet avec ce qui précède. De plus, la somme des valeurs mises à jour de a [i] est la valeur maximale de $ ans $, et l'ordre des opérations est d'ordre croissant avant «s» car les sommets insérés dans «f» augmentent le poids. Les sommets insérés dans s` réduisent le poids, vous pouvez donc le faire dans l'ordre inverse.

D.py

from collections import deque
ans=0
n=int(input())
a=list(map(int,input().split()))
b=[i-1 if i!=-1 else -1 for i in list(map(int,input().split()))]
flow=[0]*n
graph=[[] for i in range(n)]
for i in range(n):
    if b[i]!=-1:
        flow[b[i]]+=1
        graph[i].append(b[i])
check=[a[i] for i in range(n)]
ver=deque()
lv=0
for i in range(n):
    if flow[i]==0:
        ver.append(i)
        lv+=1
f,s=[],[]
while lv:
    #print(ver)
    for i in range(lv):
        x=ver.popleft()
        lv-=1
        if check[x]>=0:
            f.append(x)
            for j in graph[x]:
                flow[j]-=1
                check[j]+=check[x]
                if flow[j]==0:
                    ver.append(j)
                    lv+=1
        else:
            s.append(x)
            for j in graph[x]:
                flow[j]-=1
                if flow[j]==0:
                    ver.append(j)
                    lv+=1
#print(check)
print(sum(check))
print(" ".join(map(lambda x:str(x+1),f+s[::-1])))

Après le problème E

Je vais sauter cette fois