//Pour l'optimisation du compilateur
#pragma GCC optimize("Ofast")
//Comprendre(Ordre alphabétique)
#include<bits/stdc++.h>
using namespace std;
typedef int ll;

#define REP(i,n) for(ll i=0;i<n;i++)
//x est un conteneur tel que vector
#define SIZE(x) ll(x.size())
#define PB push_back //Insérer dans le vecteur
#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 Umap unordered_map

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;cin>>n;
    vector<vector<ll>> a(n,vector<ll>(n-1));
    REP(i,n){
        REP(j,n-1){
            ll c;cin>>c;
            if(c-1<i)a[i][j]=c-1+n*i;
            else a[i][j]=i+n*(c-1);
        }
    }
    Umap<ll,ll> d;
    REP(i,n)d[a[i][0]]++;
    vector<ll> b(n,0);
    ll ans=0;
    deque<ll> nextd;
    deque<ll> cleard;
    while(!d.empty()){
        ans++;
        bool g=true;
        for(const auto& i : d){
            if(i.S==2){
                g=false;
                ll e=(i.F)/n;ll f=(i.F)%n;
                cleard.insert(cleard.begin(),i.F);
                b[e]++;b[f]++;
                if(b[e]<n-1)nextd.insert(nextd.begin(),a[e][b[e]]);
                if(b[f]<n-1)nextd.insert(nextd.begin(),a[f][b[f]]);
            }
        }
        if(g){
            cout<<-1<<endl;
            return 0;
        }
        ll ln,lc;ln=SIZE(nextd);lc=SIZE(cleard);
        REP(i,ln){
            d[*--nextd.end()]++;
            nextd.pop_back();
        }
        REP(i,lc){
            d.erase(*--cleard.end());
            cleard.pop_back();
        }
    }
    cout<<ans<<endl;
    return 0;
}

from collections import deque
n=int(input())
#Chaque longueur est n-1
a=[[j-1+n*i if j-1<i else i+n*(j-1) for j in list(map(int,input().split()))] for i in range(n)]
#Entrez les candidats pour le match
d=dict()
for i in range(n):
    if a[i][0] in d:
        d[a[i][0]]+=1
    else:
        d[a[i][0]]=1
#Dans quelle mesure avez-vous vu
b=[0]*n
#N maximum(n-1)/Deux fois
ans=0
nextd=deque()
cleard=deque()
changeable1=deque(set([a[i][0] for i in range(n)]))
while len(d):
    ans+=1
    #Si aucun d'entre eux n'est le même
    g=True
    changeable2=deque()
    for i in changeable1:
        if d[i]==2:
            g=False
            e,f=i//n,i%n
            cleard.append(i)
            b[e]+=1
            b[f]+=1
            if b[e]<n-1:
                nextd.append(a[e][b[e]])
                changeable2.append(a[e][b[e]])
            if b[f]<n-1:
                nextd.append(a[f][b[f]])
                changeable2.append(a[f][b[f]])
    if g:
        exit(print(-1))
    ln,lc=len(nextd),len(cleard)  
    for _ in range(ln):
        i=nextd.popleft()
        if i in d:
            d[i]+=1
        else:
            d[i]=1
    for _ in range(lc):
        i=cleard.popleft()
        d.pop(i)
    changeable1=set(changeable2)
print(ans)

Jour 19

ABC140-E Second Sum

Temps pris

Je ne sais pas après l'avoir utilisé pendant environ 30 minutes → Explication AC

Cause d'erreur

Je n'avais pas confiance en ma solution. La solution ne peut être simplifiée.

Considération

Premièrement, s'il n'est ** pas à temps de compter tous les candidats dans un tel calcul de somme ** et ** dans la plage dans laquelle la valeur des candidats peut être comptée **, la valeur des candidats est dans le calcul de la somme. Vous pouvez accélérer en pensant au nombre de fois où il apparaît **.

Dans ce problème, nous pouvons voir qu'il n'y a que $ 1 \ leqq X_ {L, R} \ leqq N-1 $ $ N-1 $, donc il est probable que nous puissions compter par valeur des candidats.

Ensuite, en regardant les conditions de l'énoncé du problème, quand $ L, R (1 \ leqq L <R \ leqq N) $, le deuxième nombre dans $ P_L, P_ {L + 1},…, P_R $ Est $ X_ {L, R} $. Par conséquent, lorsque $ P_i $ devient $ X_ {L, R} $, il n'y a qu'un seul nombre dans $ P_L, P_ {L + 1},…, P_R $ plus grand que ** $ P_i $ * *Faire. Par conséquent, pour savoir s'il existe un moyen de sélectionner $ L, R $ de cette manière, vous devez faire attention aux nombres supérieurs à ** $ P_i $ **, donc ces nombres doivent être des cercles rouges et $ P_i $ doivent être des cercles bleus. Il est représenté par et est comme indiqué dans la figure ci-dessous. (Cela signifie que vous ** binarisez ** si elle est supérieure à $ P_i $.)

$ L et R $ peuvent être sélectionnés pour inclure les cercles rouges et bleus entre ① et ② dans la figure ci-dessus (✳︎), donc l'élément le plus proche sur le côté gauche des nombres plus grands que ** $ P_i $ 2 On peut dire qu'il suffit de connaître les deux éléments les plus proches du côté droit **.

Ici, si vous essayez de rechercher des éléments plus grands à partir de $ P_1, P_2,…, P_N $ pour chaque $ P_i $ à chaque fois, vous ne chercherez que $ O (N ^ 2) $ au total, ce qui n'est pas dans le temps. Cependant, il est préférable de regarder la ** plage de recherche inutile ** et le ** besoin seulement de connaître le nombre d'index plus grand que ** $ P_i $ **. En d'autres termes, si vous préparez un conteneur s qui ne stocke que des nombres plus grands que ce nombre, vous pouvez calculer à grande vitesse en vérifiant l'index ** dans l'ordre du plus grand nombre et en l'enregistrant dans s. .. De plus, ** s doit être ordonné ** afin que vous puissiez rechercher les deux index les plus proches de $ i $ sur les côtés gauche et droit **, j'ai donc décidé d'utiliser set ici.

La politique ci-dessus peut être résumée comme suit.

Insérez l'index dans s dans l'ordre décroissant. Dans cet enfant, lors de l'insertion de l'index $ i $ du nombre $ P_i $ que vous regardez dans s, les deux plus petits index ( r1 <r2) sur le côté droit et le minimum sur le côté gauche Trouvez l'index (l1> l2) des deux nombres de et trouvez le nombre lorsque $ X_ {L, R} = P_i $. De plus, dans l'état actuel des choses, il est possible que «r1», «r2», «l1», «l2» n'existent pas, donc «-2», «-1», «n comme index pour la garde ** Stockez d'abord , n + 1danss`. Sous cela, le nombre lorsque $ X_ {L, R} = P_i $ est satisfait peut être calculé par (✳︎) comme indiqué dans la figure ci-dessous.

De plus, si «l1 <0», il n'y a aucun cas qui satisfait ①, et si «r1> n-1», il n'y a aucun cas qui satisfait ②, il est donc nécessaire d'exclure ces modèles dans le calcul. Oui, vous pouvez écrire un programme de $ O (N \ log {N}) $ en effectuant le calcul ci-dessus pour tout $ P_i $.

<détails>

//Pour l'optimisation du compilateur
#pragma GCC optimize("O3")
//Comprendre(Ordre alphabétique)
#include<algorithm>//sort,Recherche de bisection,Tel
#include<bitset>//Jeu de bits de longueur fixe
#include<cmath>//pow,journal etc.
#include<complex>//Nombre complexe
#include<deque>//File d'attente d'accès double
#include<functional>//trier plus
#include<iomanip>//setprecision(Erreur de sortie en virgule flottante)
#include<iostream>//Entrée sortie
#include<iterator>//Régler l'opération(Ensemble de produits,Ensemble de somme,Ensemble de différences, etc.)
#include<map>//map(dictionnaire)
#include<numeric>//iota(Génération d'une chaîne entière),pgcd et lcm(c++17)
#include<queue>//queue
#include<set>//ensemble
#include<stack>//empiler
#include<string>//Chaîne
#include<unordered_map>//Carte avec itérateur mais sans ordre
#include<unordered_set>//Il y a un itérateur mais l'ordre n'est pas maintenu défini
#include<utility>//pair
#include<vector>//Tableau de longueur variable

using namespace std;
typedef long long ll;

//macro
//pour la relation de 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.
#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--)
//x est un conteneur tel que vector
#define ALL(x) x.begin(),x.end() //Je souhaite omettre des arguments tels que le tri
#define SIZE(x) ll(x.size()) //taille à la taille_Changement de t à ll
//constant
#define INF 1000000000000 //10^12:Valeur extrêmement élevée,∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 100000 //10^5:Portée maximale de la baie(Utilisé pour l'énumération des nombres premiers, etc.)
//Abréviation
#define PB push_back //Insérer dans le vecteur
#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 Umap unordered_map
#define Uset unordered_set
//.lower_lié est O(√n)
signed main(){
    //Code pour accélérer la saisie
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n;cin>>n;
    vector<ll> p(n);vector<ll> p_num(n);
    REP(i,n){cin>>p[i];p[i]--;p_num[p[i]]=i;}
    //C'est une bonne idée d'avoir un garde
    //p[i]Enregistrer un plus grand nombre d'index
    set<ll> s;
    s.insert(-2);s.insert(-1);
    s.insert(n);s.insert(n+1);
    ll ans=0;
    //Processus à partir d'un grand nombre
    REPD(i,n){
        //Index sur p
        ll j=p_num[i];
        ll l1,l2,r1,r2;
        r1=*(s.upper_bound(j));
        r2=*(++s.upper_bound(j));
        l1=*(--s.lower_bound(j));
        l2=*(--(--s.lower_bound(j)));
        //cout<<l2<<" "<<l1<<" "<<r1<<" "<<r2<<endl;
        if(l1>-1)ans+=((i+1)*(l1-l2)*(r1-j));
        if(r1<n)ans+=((i+1)*(r2-r1)*(j-l1));
        s.insert(j);
    }
    cout<<ans<<endl;
}

n=int(input())
paths=[[] for i in range(n)]
colors=[0]*(n-1)
for i in range(n-1):
    a,b=map(int,input().split())
    paths[a-1].append(i)
    paths[b-1].append(i)
m=0
for i in range(n):
    m=max(m,len(paths[i]))
print(m)
for i in range(n):
    cand1,cand2=set(),[]
    for j in paths[i]:
        if colors[j]!=0:
            cand1.add(colors[j])
        else:
            cand2.append(j)
    now=1
    for j in cand2:
        while now in cand1:
            now+=1
        colors[j]=now
        now+=1
for i in range(n-1):
    print(colors[i])