[PYTHON] Codeforces Round # 679 (Div.2) Révision (10/25)

Les résultats de cette fois

Impressions de cette époque

Cette fois, j'ai pu maintenir ma concentration correctement pendant le concours, donc je suis soulagé.

La raison de la victoire est que j'ai pu passer une implémentation assez lourde dans le problème C. Aujourd'hui, j'ai pu ** croire en mes pensées **, ce qui a facilité le débogage.

De plus, je pense que la précision s'est améliorée en effectuant un débogage d'impression à chaque étape à partir de ce moment. Je vais l'essayer lors du prochain concours.

Problème A

** Peut toujours contenir **, alors sélectionnez ** nombres adjacents ** et sélectionnez $ a \ _i \ times b \ _i + a \ _ {i + 1} \ times b \ _ {i + 1 Pour définir} = 0 $, définissez $ (b \ _i, b \ _ {i + 1}) = (-a \ _ {i + 1}, a \ _i) $. À ce stade, tout $ b \ _ {i} $ remplit la plage de valeurs absolues et ne devient jamais 0. De plus, comme la longueur de la séquence est paire, vous pouvez associer tous les nombres adjacents.

A.py

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    b=[0]*n
    for i in range(n//2):
        b[2*i]=-a[2*i+1]
        b[2*i+1]=a[2*i]
    print(" ".join(map(str,b)))

Problème B

Je l'ai mal lu et inversé les conditions de ligne et de colonne. C'était dangereux ...

Le premier est l'information pour chaque ligne (l'ordre des lignes n'est pas toujours correct), et le second est l'information pour chaque colonne (l'ordre des colonnes n'est pas toujours correct). De plus, tous les éléments de la matrice sont donnés comme différents.

À ce stade, le ** numéro de colonne de chaque élément est déterminé de manière unique à partir du premier **, et le ** numéro de ligne de chaque élément est uniquement déterminé à partir du second **. Par conséquent, en créant un dictionnaire sous la forme ** (valeur de l'élément): (numéro de ligne, numéro de colonne) **, le numéro de ligne et le numéro de colonne de chaque élément peuvent être connus, et la matrice d'origine peut être restaurée à partir de ces informations. C'est bon.

B.py

import sys
input=sys.stdin.readline
for _ in range(int(input())):
    n,m=map(int,input().split())
    ans=[[0]*m for i in range(n)]
    d=dict()
    for i in range(n):
        l1=list(map(int,input().split()))
        for j in range(m):
            d[l1[j]]=[-1,j]
    for i in range(m):
        l2=list(map(int,input().split()))
        for j in range(n):
            d[l2[j]][0]=j
    for i in d:
        ans[d[i][0]][d[i][1]]=i
    for i in range(n):
        print(" ".join(map(str,ans[i])))

Problème C

C'était un peu gênant pour ma mise en œuvre et mon examen, mais je suis heureux de pouvoir l'examiner pleinement. Soit dit en passant, le Range Minimum Queries que j'ai résolu l'autre jour est un sujet similaire.

Envisagez de trouver la valeur minimale de la différence entre les valeurs minimale et maximale de $ j $ lorsque $ b \ _k = a \ _i + j $ est défini pour tout $ k $ avec $ i $ défini de manière appropriée. Je vais. De plus, pour chaque son $ n $, il y a jusqu'à 6 candidats pour $ j $. Sur cette base, considérez la valeur minimale de la différence entre la valeur minimale et la valeur maximale, mais puisque ** le degré de liberté est élevé, envisagez de fixer la valeur minimale ** (** fixant la variable! **). Pour le moment, il y a un maximum de $ 6n $ candidats pour la valeur minimale, mais lorsque la valeur minimale est fixée à $ x $, le minimum $ j $ au-dessus de $ x $ est un arbre seg pour chaque $ b \ _k $. Si vous l'enregistrez avec **, vous pouvez voir que la valeur maximale qu'il contient peut être obtenue à grande vitesse sans dépenser $ O (n) $ **. De plus, il est nécessaire de mettre à jour $ b \ _k $ sauvé dans l'arborescence des segments afin de le dépasser $ x $, mais ** le nombre de mises à jour est d'environ 6 $ n $ en considérant le montant du calcul de l'amortissement **. Vous pouvez vous attendre à cela. Par conséquent, dans ce qui suit, nous examinerons l'implémentation ainsi que la méthode de solution.

Préparez d'abord les variables suivantes, etc., puis effectuez l'opération de considération.

$ a [i]: = $ (valeur de $ i $ th chaîne) $ b [i]: = $ ($ i $ ème valeur de la note) $ ind [i]: = $ ($ b [i] -a [j] $ valeur définie (ordre croissant) lorsque la $ i $ ème note est jouée sur la $ j $ ème chaîne) $ cand: = $ (valeur minimale: (carte enregistrée avec le tableau d'index du son $ i $ qui devient cette valeur)) $ itr [i]: = $ (** iterator ** de la valeur minimale de $ ind [i] $ lors de la lecture de la $ i $ e note) $ maxseg [i]: = $ (valeur de $ itr [i] $) (** mettre à jour un point, arborescence de segments de valeur de section maximale **) $ ans: = $ (solution)

$ a, b $ est juste reçu par l'entrée, $ ind $ est $ b [i] -a [j] > 0 $ se compose de n'importe quel $ i, j $, donc il suffit de tourner la boucle deux fois et de l'insérer, $ cand $ met juste un élément de $ ind $. De plus, $ itr [i] $ devrait être $ begin () $ de $ ind [i] $ par définition. A ce moment, $ maxseg [i] $ est également mis à la valeur de l'élément pointé par l'itérateur de $ ind [i] $. Ensuite, $ ans $ est initialisé comme (valeur maximale) - (valeur minimale) de l'élément pointé par $ itr $.

À partir de là, envisagez de trouver le minimum $ y $ au-dessus de $ x $ et la valeur minimale de $ y-x $, la valeur minimale étant $ x $. ** $ x $ considère ce qui est contenu dans $ cand $ par ordre croissant **. Tout d'abord, lors de l'initialisation, nous considérons quand $ x $ est la valeur minimale de tous les éléments. Lors de l'augmentation de la valeur minimale de $ x $ à partir d'ici, il est nécessaire de supprimer la valeur inférieure à cette $ x $. Tout ce que vous avez à faire est de mettre à jour $ itr, maxseg $ pour l'élément $ x $ contenu dans $ cand $ vu du petit côté. A ce moment, l'indice $ i $ inclus dans $ cand [x] $ peut être changé en $ itr [i] $ \ + \ +. Il met également à jour la valeur $ itr [i] $ mise à jour sur $ maxseg $. De plus, si ** $ itr [i] $ devient $ end () $, cela signifie qu'il n'y a pas de chaîne qui peut jouer la $ i $ ème note **, et $ ans $ à ce moment-là est sorti et sorti. Faire. De plus, lors de la mise à jour pour supprimer un certain $ x $, la valeur minimale est le plus petit élément suivant après ce $ x $, et la valeur maximale est la valeur maximale de la valeur gérée par $ maxseg $, et cette différence et ans sont faibles. Mettez à jour et par vous-même.

Vous pouvez trouver la solution $ ans $ en quittant la mise à jour ci-dessus.

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 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

/* RMQ：[0,n-1]Structure qui gère la valeur minimale pour chaque section
    update(i,x):Mise à jour du i-ème élément en x. O(log(n))
    query(a,b): [a,b)Obtenez le plus petit élément. O(log(n))
*/
template <typename T>
struct RMQ {
    const T INF = -1;
    int n;         //Nombre de feuilles
    vector<T> dat; //Disposition entièrement bifurquée
    RMQ(int n_) : n(), dat(n_ * 4, INF) { //Le nombre de feuilles est de 2^forme de x
        int x = 1;
        while (n_ > x) {
            x *= 2;
        }
        n = x;
    }

    void update(int i, T x) {
        i += n - 1;
        dat[i] = x;
        while (i > 0) {
            i = (i - 1) / 2;  // parent
            dat[i] = max(dat[i * 2 + 1], dat[i * 2 + 2]);
        }
    }

    // the minimum element of [a,b)
    T query(int a, int b) { return query_sub(a, b, 0, 0, n); }
    T query_sub(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) {
            return INF;
        } else if (a <= l && r <= b) {
            return dat[k];
        } else {
            T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
            T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
            return max(vl, vr);
        }
    }
};

signed main(){
    //Spécification de sortie du nombre de chiffres fractionnaires
    //cout<<fixed<<setprecision(10);
    //Code pour accélérer la saisie
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    vector<ll> a(6);REP(i,6)cin>>a[i];
    ll n;cin>>n;
    RMQ<ll> maxseg(n);
    vector<ll> b(n);REP(i,n)cin>>b[i];
    vector<set<ll>> ind(n);
    REP(i,n){
        REP(j,6){
            ind[i].insert(b[i]-a[j]);
        }
        //cout<<SIZE(ind[i])<<endl;
    }
    map<ll,vector<ll>> cand;
    REP(i,n){
        FORA(j,ind[i]){
            cand[j].PB(i);
        }
    }
    //cout<<1<<endl;
    vector<set<ll>::iterator> itr(n);
    ll ma=-1;
    REP(i,n){
        itr[i]=ind[i].begin();
        maxseg.update(i,*itr[i]);
        ma=max(ma,*itr[i]);
    }
    ll ans=ma-cand.begin()->F;
    for(auto i=cand.begin();i!=cand.end();i++){
        FORA(j,i->S){
            itr[j]++;
            if(itr[j]==ind[j].end()){
                cout<<ans<<endl;
                return 0;
            }
            maxseg.update(j,*itr[j]);
        }
        ans=min(ans,maxseg.query(0,n)-(++i)->F);
        i--;
    }
    cout<<ans<<endl;
}

Problème D

Je pensais qu'il valait mieux l'emballer goulûment pour répondre aux conditions, mais si c'est de l'avant, il est difficile de fixer les conditions, alors pourquoi ne pas penser de l'arrière? J'ai pensé (** Pensez dans l'ordre inverse! **).

Lorsqu'il y a un ensemble de nombres qui doivent être emballés dans la position lorsqu'ils sont vus de l'arrière (un ensemble de + ??? Numbers), ** attribuez le plus petit nombre à la position ** Est le meilleur. Chaque ** - position est déterminée de manière unique par cette méthode **. De plus, si la position de-ne peut pas être déterminée (lorsque la taille de l'ensemble est 0), NO est émis, et si même l'un de + ?? ne satisfait pas le sujet après avoir déterminé la position de-, NON est émis. Faire. Si ces jugements sont effacés, OUI doit être affiché. (Je ne l'ai pas prouvé, mais je pense que c'est assez raisonnable)

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(){
    //Spécification de sortie du nombre de chiffres fractionnaires
    //cout<<fixed<<setprecision(10);
    //Code pour accélérer la saisie
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n;cin>>n;
    vector<ll> que(2*n,0);
    REP(i,2*n){
        string s;cin>>s;
        if(s=="-"){
            ll x;cin>>x;
            que[i]=x;
        }
    }
    set<ll> cand;
    vector<ll> ans(n);
    ll ind=n-1;
    REPD(i,2*n){
        if(que[i]!=0){
            cand.insert(que[i]);
        }else{
            if(SIZE(cand)==0){
                cout<<"NO"<<endl;
                return 0;
            }else{
                ll y=*cand.begin();
                ans[ind]=y;
                ind--;
                cand.erase(cand.begin());
            }
        }
    }
    ind++;
    REP(i,2*n){
        if(que[i]==0){
            cand.insert(ans[ind]);
            ind++;
        }else{
            ll y=*cand.begin();
            if(que[i]!=y){
                cout<<"NO"<<endl;
                return 0;
            }
            cand.erase(cand.begin());
        }
    }
    cout<<"YES"<<endl;
    REP(i,n){
        if(i==n-1)cout<<ans[i]<<endl;
        else cout<<ans[i]<<" ";
    }
}

Problème E

Je vais sauter cette fois.