[PYTHON] Codeforces Round # 652 (Div.2) Examen Bacha (8/24)

Les résultats de cette fois

Impressions de cette époque

Cette fois, je sens que j'ai pu le résoudre comme je le voulais. Cependant, la vitesse est encore insuffisante, je voudrais donc ** améliorer le sens de la solution **.

Problème A

En repensant au problème, pensant que ce serait bien s'il y avait des côtés parallèles, il a été dit qu'il devrait y avoir au moins un côté parallèle à l'axe $ X $ et parallèle à l'axe $ Y $, de sorte que le nombre de côtés est de quatre. "OUI" n'était affiché que s'il s'agissait d'un multiple de. Je l'ai fait passer par le concours avec une idée graphique, mais c'est facile à prouver si l'on fait attention à l'angle central.

A.py

for i in range(int(input())):
    n=int(input())
    print("YES"if n%4==0 else "NO")

Problème B

Il semble qu'il ait été résolu à une vitesse considérablement plus rapide que l'environnement. Cependant, je suis désolé car j'étais un peu perdu dans la mise en œuvre. Pour les chaînes (binaires) **, il est particulièrement important d'expérimenter des échantillons pour en avoir une idée **.

Puisque l'un des deux caractères adjacents «10» est effacé, ** le 0 qui est continu à l'extrémité gauche et le 1 qui est continu à l'extrémité droite ne peuvent pas être effacés ** (je pense que c'est facile à comprendre si vous regardez le premier échantillon) Je vais.). Par conséquent, j'ai essayé de sauvegarder le nombre de ces éléments dans $ l et r $. De plus, si ** tous les éléments sont inclus dans une partie contiguë (✳︎) **, il ne peut pas être raccourci, de sorte que la chaîne de caractères donnée est sortie telle quelle.

De plus, si vous ignorez la partie continue de l'extrémité gauche et de l'extrémité droite, la chaîne de caractères suivante apparaîtra. (Puisque le motif de (✳︎) est exclu, un ou plusieurs 1 apparaîtront toujours à l'extrémité gauche et un ou plusieurs 0 apparaîtront à l'extrémité droite.)

11…00

Une telle chaîne de caractères peut finalement être laissée dans l'état "10" en ajustant l'ordre des caractères à effacer. Ici, ** si les longueurs sont les mêmes, elles sont plus petites dans l'ordre lexical **, il est donc préférable d'effacer 1 et de laisser 0, et la chaîne de caractères à afficher est `(0 continu à l'extrémité gauche) +0. + (Continu 1) ʻà l'extrémité droite.

B.py

for i in range(int(input())):
    n=int(input())
    s=input()
    if all([i=="1" for i in s]) or all([i=="0" for i in s]):
        print(s)
        continue
    #l,r doit être
    l,r=-1,n
    for i in range(n):
        if s[i]=="1":
            l=i
            break
    for i in range(n-1,-1,-1):
        if s[i]=="0":
            r=i
            break
    if l>r:
        print(s)
        continue
    print(s[:l]+"0"+s[r+1:])

Problème C

Pensez à maximiser le bonheur de chacun. À ce moment, j'ai pensé à la ** méthode de la cupidité ** en pensant à utiliser des éléments aussi grands que possible pour max et min. Autrement dit, considérez que ** les petits éléments sont consommés autant que possible ** pour augmenter «min», et ** les grands éléments sont consommés aussi peu que possible ** pour augmenter «max». Autrement dit, vous pouvez penser comme suit.

Disposer $ a \ _i $ et $ w \ _i $ dans l'ordre décroissant. Pour chaque $ w \ _i $ max, sélectionnez et supprimez le plus grand élément restant. Ensuite, sélectionnez et supprimez les pièces $ w \ _i-1 $ des éléments restants dans l'ordre croissant. À ce stade, «min» est le plus petit élément. En faisant cela, max peut sélectionner les plus gros éléments $ k $ ** dans ** $ a \ _i $, et ** consommer les plus petits éléments autant que possible ** en premier. Vous pouvez viser la maximisation avec.

Cependant, vous devez faire attention ici lorsque ** $ w \ _i = 1 $ **. À ce stade, ** max et min correspondent **, donc en sélectionnant un élément plus grand, vous pouvez sélectionner deux fois le bonheur de cet élément. Par conséquent, lorsque $ w \ _i = 1 $, sélectionnez un grand élément à l'avance.

C.py

from collections import deque
for _ in range(int(input())):
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort(reverse=True)
    a=deque(a)
    w=list(map(int,input().split()))
    w.sort(reverse=True)
    #Processus 1 en premier
    ans=0
    for i in range(w.count(1)):
        ans+=2*a.popleft()
    for i in range(k-w.count(1)):
        p=a.popleft()
        ans+=p
        #print(p)
        for j in range(w[i]-1):
            p=a.pop()
            if j==0:
                ans+=p
                #print(p)
    print(ans)

Problème D

Pour le moment, j'ai pensé ** en dessinant un diagramme ** pour savoir de quel genre d'arbre il s'agit. A ce moment, les sommets ont augmenté dans l'ordre rouge → jaune → bleu → vert → rouge, et j'ai compris que c'était un ** arbre qui était déterminé récursivement dans l'ordre à partir de la racine ** (on peut aussi l'appeler une figure fractale).

De plus, si vous regardez la griffe (un sous-arbre qui a trois côtés s'étendant à partir d'une racine), ** les racines de la griffe sont également incluses dans la griffe **. Par conséquent, il est possible de ne peindre que la griffe créée au temps $ n $, et (le nombre de racines de la griffe créée au temps $ n $) $ \ times $ 4 est le nombre de sommets pouvant être peints en jaune. C'était (✳︎).

Ici, ** il peut être déterminé récursivement à partir de la racine et ** il y a trois états de l'apex ** (qu'il n'ait pas de feuilles, une feuille ou trois feuilles). En se concentrant sur, il est facile à mettre en œuvre si vous le considérez comme dp. Par conséquent, définissez DP comme suit:

$ dp [i] [j]: = $ (Combien de sommets sont dans l'état $ j $ à partir de la première tentative $ i $)

Cependant, il n'a pas de feuille quand $ j = 0 $, a une feuille quand $ j = 1 $, et a trois feuilles quand $ j = 2 $.

À ce moment, le changement de DP est le suivant. (Si la transition de DP est difficile à comprendre comme ce problème, il est facile à comprendre en tabulant la transition **.)

Quand ceci est transcrit en code, cela ressemble à ceci:

dp[i][0]+=dp[i-1][0]
dp[i][1]+=dp[i-1][0]
dp[i][0]+=dp[i-1][1]*2
dp[i][2]+=dp[i-1][1]
dp[i][2]+=dp[i-1][2]

De plus, si vous utilisez (✳︎), $ (dp [i] [2] -dp [i-1] [2]) \ times 4 $ sera la réponse, mais ** $ n $ la troisième griffe Autre que cela peut être peint **, donc certains des échantillons n'ont pas réussi. Compte tenu de la figure ci-dessous, si vous appliquez la griffe créée au $ n $ ème temps, vous pouvez appliquer la griffe créée au ** $ n-3 $ ème fois parmi les griffes supérieures **.

Par conséquent, la griffe qui peut être peinte dans le Rooted Dead Bush dont le niveau est $ n $ est "($ n $ claw) + ($ n-3 $ claw) + ($ n-6 $) Ce sera la deuxième griffe) + ... ".

De plus, en termes de quantité de calcul **, il ne suffit pas de calculer le DP à chaque fois **, donc le ** tableau DP jusqu'à 2 $ \ fois 10 ^ 6 $ est précalculé ** et l '(index) du tableau DP est calculé. La ** somme cumulée (pour chaque valeur de $ mod \ 3 $) doit également être préparée dans le pré-calcul **.

De plus, le pré-calcul de DP semblait utiliser trop de mémoire dans mon implémentation et est devenu MLE, donc je l'ai réécrit en ** C ++ et j'ai pris MLE **.

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

signed main(){
    //Code pour accélérer la saisie
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n=2000000;
    vector<vector<ll>> dp(n,vector<ll>(3,0));
    dp[0][0]=1;
    FOR(i,1,n-1){
        dp[i][0]+=dp[i-1][0];
        dp[i][1]+=dp[i-1][0];
        dp[i][0]+=dp[i-1][1]*2;
        dp[i][2]+=dp[i-1][1];
        dp[i][2]+=dp[i-1][2];
        dp[i][0]%=MOD;
        dp[i][1]%=MOD;
        dp[i][2]%=MOD;
    }
    vector<ll> ans(n,0);
    REP(i,3){
        if(i!=0){
            ans[i]+=(MOD+dp[i][2]-dp[i-1][2])*4;
            ans[i]%=MOD;
        }
        for(ll j=i;j<n-3;j+=3){
            ans[j+3]+=ans[j];
            ans[j+3]+=(MOD+dp[j+3][2]-dp[j+2][2])*4;
            ans[j+3]%=MOD;
        }
    }
    ll t;cin>>t;
    REP(i,t){
        cin>>n;
        cout<<ans[n-1]<<endl;
    }
}

Après le problème E

Je vais sauter cette fois