P2569 https://www.luogu.com.cn/problem/P2569
Référence à cet article.
/* Optimisation de DP par file monotone
L'équation de transfert pour l'achat d'actions énumère j de manière séquentielle, car le nombre d'actions détenues devrait augmenter. La décision actuelle pourrait être nécessaire pour des j plus tardifs, donc elle doit être calculée à l'avance. De même, lors de la vente d'actions, le nombre d'actions détenues diminue, donc la décision actuelle pourrait nécessiter des états avec moins d'actions, nécessitant un traitement inversé.*/
https://www.luogu.com.cn/record/223728748
AT_arc098_b \(x \oplus y \oplus \cdots \oplus z \le x+y+..+z\). Le OU exclusif est une addition sans retenue, donc une partie inégale n'implique pas une égalité totale.
P2882 Comment traiter en \(O(1)\) le retournement d'intervalles dans une séquence 01 et les requêtes en temps réel ? Voici \(a_i \oplus x\) comme valeur réelle, \(b\) comme tableau de différences, \(k\) comme longueur de retournement, et l'instruction if est simplement une condition.
bool x=0;
for(int i=1;i<=n;i++)b[i]=0;
for(int i=1;i<=n;i++){
x^=b[i];
if(a[i]^x){
x^=1;
b[i+k]^=1;
}
}
Les trois énoncés suivants sont équivalents :
- La valeur maximale minimale sur tous les chemins simples entre deux nœuds dans le graphe original.
- La valeur maximale sur le chemin simple entre deux nœuds dans l'arbre couvrant minimal.
- La valeur du LCA de deux nœuds dans l'arbre de reconstruction de Kruskal.
P6835 https://www.luogu.com.cn/article/icz18zjz Il est recommandé de re-deriver les formules manuellement.
L'équation de transfert pour la plus longue sous-séquence commune.
[f_{i,j}=\max(f_{i-1,j},f_{i,j-1}) ][if(a_i==b_j)\quad f_{i,j}=\max(f_{i,j},f_{i-1,j-1}+1) ]P2516 https://www.luogu.com.cn/record/224495353
Il y a trois difficultés. D'après l'énoncé :
- \(a_i\) et \(b_j\) appartiennent tous à toutes les \(lcs(i,j)\).
- \(a_i\) appartient à toutes les \(lcs(i,j)\), mais \(b_j\) n'appartient pas à toutes.
- \(a_i\) n'appartient pas à toutes les \(lcs(i,j)\), mais \(b_j\) y appartient.
- \(a_i\) et \(b_j\) n'appartiennent pas à toutes les \(lcs(i,j)\).
- Si \(a_i=b_j\), alors \(f_{i,j}=f_{i-1,j-1}+1\), correspondant au cas 1.
- Si \(f_{i,j}=f_{i,j-1}\), alors \(b_j\) n'appartient pas à toutes les \(lcs(i,j)\), correspondant aux cas 2 et 4.
- Si \(f_{i,j}=f_{i-1,j}\), alors \(a_i\) n'appartient pas à toutes les \(lcs(i,j)\), correspondant aux cas 3 et 4.
- Si \(f_{i,j}=f_{i-1,j-1}\), alors cela correspond au cas 4, et les deux conditions précédentes sont également satisfaites.
- Pourquoi soustraire cette partie ? Selon le principe d'inclusion-exclusion, cela a été compté une fois en trop, donc on le soustrait.
- Optimisation par déroulement (facile à écrire incorrectement). Puis le transfert minimal commence de l'état précédent, la première dimension de taille 2 suffit. Utiliser une nouvelle variable pour dérouler la première dimension.
- Initialisation. La première dimension étant déroulée, il n'est pas nécessaire de l'initialiser. N'oubliez pas de définir les autres frontières avec au moins une solution pour pouvoir accumuler.
Skip1
P2051 https://www.luogu.com.cn/problem/P2051Pour ce genre de problèmes de grille, considérez toujours une compression d'état. Au plus deux canons par ligne et par colonne. Divisez ensuite selon que cette ligne utilise 0, 1 ou 2 canons. Il s'agit simplement d'une grande discussion de classification. Cependant, la conception de l'état est également un défi.
\(f_{i,j,k}\) représente le nombre de solutions pour les \(i\) premières lignes avec \(j\) colonnes contenant 1 pièce et \(k\) colonnes contenant 2 pièces.
Le point d'erreur facile est le placement de 2 pièces. Le cas où une colonne vide est ajoutée. À ce moment, une colonne avec 1 pièce est perdue et une autre est gagnée. Le nombre total de colonnes ne change pas !
L'ajout d'une fonction convexe à une fonction affine conserve la convexité.
P3605 Différence sur les sous-arbres https://www.luogu.com.cn/problem/P3605
Étant donné un arbre à \(n\) nœuds, chaque nœud ayant une valeur, trouver pour chaque nœud le nombre de nœuds dans son sous-arbre dont la valeur est supérieure à la sienne, \(n \le 10^5\).
Le nombre de nœuds supérieurs à une certaine valeur peut évidemment être maintenu avec un arbre de Fenwick, le défi étant de calculer précisément dans un seul sous-arbre.
Si nous mettons à jour l'arbre de Fenwick pendant le parcours DFS, nous maintenons le nombre d'occurrences de chaque valeur jusqu'au point actuel du parcours, ce qui n'est pas nécessairement le cas d'un seul sous-arbre.
Considérez que pendant le parcours DFS, un nœud entre (récursion) et sort (retour) une fois. En réalité, lorsque nous entrons dans un nœud, les informations de son sous-arbre ne sont pas encore mises à jour dans l'arbre de Fenwick, et lorsque nous sortons, les informations de son sous-arbre sont déjà ajoutées. Par conséquent, la différence entre ces deux points de temps est la contribution de ce sous-arbre. Cette idée est appelée différence sur les sous-arbres.
Exemple de différence sur les sous-arbres : https://www.luogu.com.cn/problem/P1600
popcount(a^b)=popcount(a|b)-popcount(a&b)=
popcount(a)+popcount(b)-2popcount(a&b)
https://www.luogu.com.cn/problem/P3051https://www.luogu.com.cn/article/sb4oa22b
Un trick que l'on devrait connaître.
Transformer un cycle en une chaîne !
Problème classique : une chaîne, donnant plusieurs segments, question : pour couvrir complètement cette chaîne, quel est le nombre minimum de segments à sélectionner ?
Triez tous les candidats segments par leur point gauche \(l_i\) en ordre croissant. Si les points gauches sont les mêmes, triez par le point droit \(r_i\) en ordre décroissant.
Supposons que l'intervalle sélectionné actuel couvre déjà les premiers \(x\) points. Pour couvrir le point \(x+1\), nous devons sélectionner un intervalle dont le point gauche est inférieur ou égal à \(x+1\). Nous ajoutons alors un intervalle dont le point gauche est inférieur ou égal à \(x+1\) et dont le point droit est maximal, afin de couvrir le plus de points possible, ce qui est optimal.
Mettons à jour \(x\) avec ce point droit. Initialement, posons \(x=0\), et répétons ce processus de sélection d'intervalles jusqu'à ce que \(x=n\). Si à un moment donné, après avoir sélectionné un intervalle, \(x\) ne change pas, cela signifie que le point \(x+1\) ne peut pas être couvert, il n'y a donc pas de solution.
Pour chaque \(1 \le i \le n\), pré-traitons la position du point droit maximal parmi tous les intervalles dont le point gauche est inférieur ou égal à \(i\). Nous pouvons ainsi pré-traiter en \(O(n+k)\), sélectionner les intervalles en \(O(n)\), la complexité totale étant \(O(n+k)\) pour résoudre ce problème.
Pour un cycle, P6902 le décompose, mais nécessite une optimisation par doublement pour atteindre \(O(n \log n)\). https://www.luogu.com.cn/problem/P6902
https://www.luogu.com.cn/record/225195227
Risque de dépassemant de tableau : dans la boucle for(int j=0;j<=vec[i].size()-1;j++), si vec[i] est vide, vec[i].size()-1 devient la valeur maximale d'un entier non signé (car size() retourne un non signé), ce qui provoque une condition de boucle anormale. Il est recommandé de changer en for(int j=0;j<=(int)vec[i].size()-1;j++) ou d'utiliser un itérateur.
Skip2
P2519 https://www.luogu.com.cn/problem/P2519https://www.luogu.com.cn/article/jczkipeh
Cependant, si le nombre d'intervalles superposés dépasse la longueur de l'intervalle, il y a nécessairement des fausses déclarations.
Cela est facile à comprendre : si la longueur de l'intervalle est \(k\), cela signifie que \(k\) personnes ont des scores égaux, mais plus de \(k\) personnes prétendent être dans cet intervalle, ce qui est manifestement faux.
De nombreux problèmes bleus sont de ce type, ce sont tous des problèmes difficiles.
https://www.luogu.com.cn/problem/AT_dp_thttps://www.luogu.com.cn/problem/P2467https://www.luogu.com.cn/article/o0oht8bjhttps://www.luogu.com.cn/article/sg1fwhh5
Les équations de transfert sont similaires, utilisées pour traiter les formes d'onde. Soit \(f_{i,j}\) le nombre total de solutions après avoir considéré les \(i\) premières positions, et que la \(i\)-ème position soit remplie par le \(j\)-ème plus petit nombre. (Puisqu'il s'agit d'une permutation, le \(j\)-ème plus petit équivaut à ce que cette position soit remplie par \(j\)).
P1070 J'ai enfin trouvé la solution correcte !!!
https://www.luogu.com.cn/article/5p3x7ruk
Traitement divin : il faut d'abord penser à fixer le robot tournant vers l'usine et les pièces. Ensuite, une transformation intelligente du transfert.
P6647 https://www.luogu.com.cn/record/225529688
P3188 Un DP très intéressant.
Méthode de recherche du chemin le plus long dans un graphe connexe : tri topologique plus DP.
- Tri topologique pour déterminer l'ordre de traitement des nœuds.
- Définir \(dp_i\) comme la longueur du chemin le plus long se terminant au nœud \(i\).
- Récurrence : \(dp_i=max(dp_j+w_{j,i})\), pour toutes les entrées \(j\rightarrow i\).
Skip 3
P1600 https://www.luogu.com.cn/problem/P1600 .
Solution : https://www.luogu.com.cn/article/nkwnx1ti .
Discuter en deux parties du chemin \(s \rightarrow lca\) et \(lca \rightarrow t\), dériver les conditions qui peuvent être observées, et utiliser la différence sur les sous-arbres.
https://www.luogu.com.cn/record/226182410
Les nœuds d'un sous-arbre forment un intervalle continu dans l'ordre DFS, on peut donc les parcourir directement.
Le nombre de nœuds dans l'arbre rond-carré est inférieur à \(2n\), car le nombre de points d'articulation est inférieur à \(n\), donc veuillez doubler la taille de tous les tableaux.
Pseudo-code pour le chemin d'Euler.
void dfs(int now)
{
for(int i=del[now];i<G[i].size();i=del[now])
{
del[now]=i+1;
dfs(G[now][i])
}
st.push(now);
}
// où del[now] indique que G[now][1,2,…,del[now]-1]
// a déjà été marqué, la prochaine fois on doit commencer par G[now][del[now]].
L'algorithme SPFA permet à une arête d'être traversée plusieurs fois, tandis que l'algorithme Dijkstra ne l'autorise pas.
CF609E : \(n\) nœuds, \(m\) arêtes, si pour un arbre couvrant minimal on doit inclure la \(i\)-ème arête (\(1 \le i \le m\)), quel est le poids minimal total de l'arbre couvrant minimal ? \(1 \le n \le 2 \times 10^5\), \(n-1 \le m\le 2 \times 10^5\).
Trouvez l'arbre couvrant minimal, ajoutez la \(i\)-ème arête, puis un cycle apparaît. Supprimez simplement l'arête de poids maximal dans ce cycle. Bien sûr, on ne peut pas se supprimer soi-même, donc on supprime l'arête de poids maximal sur le chemin \(u\rightarrow v\) dans l'arbre couvrant minimal original. Faites une décomposition en arbre pour le maintenir.
Plus court chemin avec congruence.
https://www.luogu.com.cn/problem/P3403 .
https://www.luogu.com.cn/problem/P2371 .
Minimisation du plus court chemin multi-points en plus court chemin entre deux points.
https://www.luogu.com.cn/problem/P5304 .
Divisez en deux ensembles, en s'assurant que les points entre les ensembles ne forment pas le plus court chemin minimal, puis connectez le point de départ \(s\) à l'ensemble 1 (poids 0), le point d'arrivée \(t\) à l'ensemble 2, et connectez les ensembles 1 et 2. Le problème original devient alors le plus court chemin de \(s\rightarrow t\).
Le point clé est comment diviser les ensembles de points. https://www.luogu.com.cn/problem/solution/P5304?page=1 .
https://www.luogu.com.cn/problem/P3199 .
Soit \(ans\) la moyenne minimale de tous les cycles dans un graphe orienté pondéré. Pour tout graphe orienté \(G\), ajoutez un point \(s\).
[ans=\min_{v \in V,F_n(v)\ne \infty }\max_{0 \le k \le n-1}[\frac{F_n(v)-F_k(v)}{n-k} ] ]où \(F_k(v)\) est le plus court chemin de \(s \rightarrow v\) avec exactement \(k\) arêtes (\(\infty\) s'il n'existe pas).
Planification fractionnaire 01 : https://blog.csdn.net/niiick/article/details/80925267 .
Skip 4
https://www.luogu.com.cn/problem/P3430 .
Étant donné deux tableaux, il ne doit pas y avoir de nombres identiques dans chaque tableau. Les nombres aux mêmes positions dans les deux tableaux peuvent être échangés, quel est le nombre minimum d'échanges pour satisfaire les conditions ci-dessus ?
Si deux nombres identiques ne sont pas dans la même ligne, connectez les numéros de colonnes des deux nombres avec une arête de poids 0, sinon connectez-les avec une arête de poids 1.
Coloriez en noir et blanc chaque composante connexe des points (les points connectés par une arête de poids 1 ont des couleurs opposées, ceux connectés par une arête de poids 0 ont la même couleur), ajoutez à chaque fois la valeur minimale du nombre de points noirs et blancs dans chaque composante connexe à la réponse.
https://www.luogu.com.cn/article/rfudqj2s .
La solution n'est pas tout à fait claire, merci à VainSylphid du groupe pour sa réponse. Voici les propos originaux :
Vous remarquez qu'une arête de poids 1 équivaut à vouloir qu'une colonne sur les deux soit échangée. Une arête de poids 0 équivaut à ce que si l'une des deux colonnes est échangée, l'autre le soit aussi.
En colorant comme dans la solution, cela équivaut à ce que toutes les cases d'une même couleur doivent être échangées ou toutes ne pas être échangées.
Et une couleur est entièrement échangée, l'autre ne l'est pas.
Il est alors évident de prendre la valeur minimale.
2025.7.28-7.29 Thème sur l'optimisation par pente
Aujourd'hui, thème sur l'optimisation par pente. https://www.bilibili.com/video/BV1dKSJY5Ew5 .
P2365 https://www.luogu.com.cn/article/367gcax3
Le calcul des coûts à l'avance, génial. Il suffit d'ajouter l'impact de \(s\) sur \(j+1\) dans les coûts. Le coût du nouveau segment est déjà ajouté dans \(f\).
https://www.luogu.com.cn/record/227393110
Les principes de réarrangement sont :
- Traitez les expressions contenant \(function(i)\times functon(j)\) comme \(kx\).
- Les termes contenant \(dp_i\) doivent être dans l'expression \(b\).
- Les termes contenant \(function(j)\) doivent être dans l'expression \(y\).
- Si l'expression de l'inconnue \(x\) est décroissante, il vaut mieux multiplier les deux côtés par \(−1\) pour la rendre croissante.
Version simplifiée à mémoriser :
- Terme croisé \(kx\).
- \(dp_i \rightarrow b\).
- \(fuc_j \rightarrow y\).
Utilisez une file monotone pour maintenir l'ensemble de points de l'enveloppe convexe, les opérations se font en trois étapes :
- Lors de la sélection optimale, trouvez le point de décision optimal \(j\) sur l'enveloppe convexe.
- Mettez à jour \(dp_i\) avec le point de décision optimal \(j\) .
- Ajoutez \(i\) comme point de décision au graphique et mettez à jour l'enveloppe convexe (si le point \(i\) est également l'un des points de décision pour \(dp_i\), alors l'étape 3 doit être placée en premier).
Skip 5
https://www.luogu.com.cn/problem/P5677 .
Un excellent problème.
:::info Triez, traitez toutes les bonnes paires. Hors ligne, triez par point gauche croissant, ajoutez continuellement les segments avec un point gauche inférieur ou égal au point droit actuel, puis retirez les segments avant \(l\) pour la contribution actuelle. :::
https://www.luogu.com.cn/record/228032569 .
P7706 https://www.luogu.com.cn/problem/P7706 .
Je ne savais pas, après 10 minutes de réflexion sans résultat, j'ai explosé. Un problème difficile, en réalité très standard, je ne connaissais juste pas ce trick. https://www.luogu.com.cn/article/oj2vo7sx . Explication très claire, inutile de s'étandre.
https://www.luogu.com.cn/problem/P3792https://www.luogu.com.cn/problem/P5278
"Double expérience", https://www.luogu.com.cn/article/itudyc23 Apprendre la méthode de pensée.
Dans le problème Luogu P5278, maintenir la valeur maximale du prédécesseur (c'est-à-dire la valeur maximale de la position de la dernière occurrence de chaque élément dans l'intervalle) a pour objectif principal de détecter rapidement la duplication des éléments. Si cette valeur maximale est supérieure ou égale au point gauche de l'intervalle, cela indique qu'au moins un élément apparaît en double dans l'intervalle.
Cycles de permutation https://www.cnblogs.com/TTS-TTS/p/17047104.html .
- Algorithme LCA avec ordre d'Euler
Complexité de prétraitement : \(O(n + n \log n) = O(n\log n)\).
Complexité de requête : \(O(1)\).
Méthode d'implémentation : Transformer le problème LCA en un problème RMQ, résolu avec une table ST.
- Algorithme LCA par doublement
Complexité de prétraitement : \(O(n\log n)\).
Complexité de requête : $O(\log n) $.
Méthode d'implémentation : Prétraiter le \(2^k\)-ième ancêtre de chaque nœud, utiliser la méthode de doublement pour la requête.
Dans l'arbre virtuel, on peut voir que chaque bleu correspond à une composante connexe, et la taille de la composante est la taille du sous-arbre du bleu dans l'arbre original moins la taille du sous-arbre de son fils bleu.
Skip 6
Supposons que \(G=(X,Y,E)\) soit un graphe biparti, et \(\left | X \right | \le \left | Y \right |\). Pour tout \(W\subseteq X\), notons \(V(W)\) l'ensemble des sommets adjacents à \(W\) dans \(G\). Alors il existe un appariement \(M\) dans le graphe \(G\) tel que tous les points de \(X\) soient appariés si et seulement si \(\left | W \right | \le \left | V(W) \right |\) pour tout \(W\subseteq X\).
Tous les graphes biparti réguliers ont un appariement parfait. (Dans un graphe biparti régulier, tous les sommets ont le même degré).
L'opération de suppression peut être traitée hors ligne en inversant le temps pour devenir une opération d'ajout.
Il y a une matrice \(n\times m\) \(A\). Chaque élément de \(A\) est un entier dans \([0,10^5]\). Formellement, on a
[E_{i,j}=\sum_{1\le x\le n}\sum_{1\le y\le m}(|x-i|+|y-j|)A_{x,y} ]On doit maintenant utiliser la matrice \(E\) pour reconstruire une matrice entière \(A\) satisfaisant les conditions ci-dessus. Les éléments de la matrice reconstruite \(A\) appartiennent simplement à \([0,10^{16}]\).
La complexité temporelle unique doit être \(O(nm)\).
Quel problème génial !
Soit :
[C_i=\sum_{j=1}^{m}A_{i,j} ][E_{i,j}=\sum_{1\le x\le n}\sum_{1\le y\le m}(|x-i|+|y-j|)A_{x,y} ]De cette formule, on remarque :
[E_{i,j}=\sum_{x=1}^{n}\left |x-i \right |\times C_x+\sum_{x=1}^{m}\left |x-j \right |\times R_x ]De plus :
[E_{i-1,j}+E_{i+1,j}-2\times E_{i,j}=2\times C_i ]où \(2 \le i \le n-1\).
De même, on peut résoudre pour \(R_j\).
[R_j=\sum_{i=1}^{n}A_{i,j} ]Cela signifie que seuls \(C_1,C_n,R_1,R_m\) restent indéterminés.
Considérons une approche gourmande, nous traitons chaque \(A_{i,j}\) en le définissant comme \(\min(R_i,C_i)\), puis soustrayons \(A_{i,j}\) de \(R_i\) et \(C_i\), et continuons. S'il existe une solution, cette approche construira toujours une solution avec \(A_{i,j}\) non négatif.
Ainsi, ce problème divin est terminé (ou pas ?).
:::info Notez qu'il faut traiter spécifiquement les cas \(n=1\) et \(m=1\) ! Ces deux cas nécessitent une solution spéciale !:::
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define For(i,l,r) for(int i=l;i<=r;i++)
int n,m;
void solve(){
cin>>n>>m;
vector<vector<int> >E(n+1),A(n+1);
vector<int>C(n+1),R(m+1);
For(i,1,n){
E[i].resize(m+1);
A[i].resize(m+1);
}
For(i,1,n)For(j,1,m)cin>>E[i][j];
For(i,2,n-1)C[i]=(E[i-1][1]+E[i+1][1]-2*E[i][1])/2;
For(i,2,m-1)R[i]=(E[1][i-1]+E[1][i+1]-2*E[1][i])/2;
if(n==1&&m==1){cout<<E[1][1]<<"\n";return ;}
if(n==1){
R[1]=E[1][m];
For(i,2,m-1)R[1]-=(m-i)*R[i];
R[m]=E[1][1];
For(i,2,m-1)R[m]-=(i-1)*R[i];
R[1]/=m-1,R[m]/=m-1;
For(i,1,m)cout<<R[i]<<" ";
cout<<"\n";
return;
}
if(m==1){
C[1]=E[n][1];
For(i,2,n-1)C[1]-=(n-i)*C[i];
C[n]=E[1][1];
For(i,2,n-1)C[n]-=(i-1)*C[i];
C[1]/=n-1,C[n]/=n-1;
For(i,1,n)cout<<C[i]<<"\n";
return;
}
int X=E[1][1];
int Y=E[1][m];
int Z=E[n][1];
For(i,2,n-1){
X-=(i-1)*C[i];
Y-=(i-1)*C[i];
Z-=(n-i)*C[i];
}
For(i,2,m-1){
X-=(i-1)*R[i];
Y-=(m-i)*R[i];
Z-=(i-1)*R[i];
}
int W=0;
For(i,2,m-1)W+=R[i];
For(i,2,n-1)W-=C[i];
W=W*(n-1)*(m-1);
W-=(m-1)*Z-(n+m-2)*X-(n-1)*Y;
W/=n-1,W/=2*n+2*m-4;
C[n]=W;
C[1]=(Z-X)/(n-1)+C[n];
R[1]=(Y-(n-1)*C[n])/(m-1);
R[m]=(X-(n-1)*C[n])/(m-1);
For(i,1,n){
For(j,1,m){
A[i][j]=min(C[i],R[j]);
C[i]-=A[i][j];
R[j]-=A[i][j];
}
}
For(i,1,n){
For(j,1,m){
cout<<A[i][j]<<" ";
}
cout<<"\n";
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int T;cin>>T;
while(T--)solve();
return 0;
}
Skip 7
Deux piles, chacune contenant \(n\times K\) éléments, où les nombres \(1,2,\cdots, n\) apparaissent chacun exactement \(K\) fois.
Continuez les opérations suivantes jusqu'à ce qu'une pile soit vide :
- Si les éléments en haut des deux piles sont identiques, retirez les deux éléments en haut des deux piles et obtenez 1 point.
- Si les éléments en haut des deux piles sont différents, retirez l'élément en haut d'une pile, sans obtenir de point.
Calculez, par des opérations appropriées, le score maximum possible.
Pour toutes les données, on garantit \(1\le n\le 10^4,1\le K\le 16\).
Considérons tous les moments où des points sont obtenus, marquons les positions des éléments appariés dans les piles d'origine, nous obtenons ainsi deux séquences strictement croissantes \(x,y\). Où \(a_{x_i}=b_{y_i}\).
Inversement, si deux séquences satisfont aux conditions ci-dessus, alors on peut obtenir des points par certaines opérations. L'objectif devient donc de maximiser la longueur de la séquence sous les contraintes.
Prenez toutes les paires possibles \((x_i,y_i)\), définissez une relation totale \(i < j\) quand \((x_i,y_i)<(x_j,y_j)\). (Ici le plus petit est inférieur dans les deux dimensions). Il y a \(nK^2\) paires au total.
:::info Pourquoi \(nK^2\) paires ? Il y a \(n\) nombres différents, chaque nombre apparaissant \(K\) fois dans la première pile et \(K\) fois dans la seconde. :::
Trouvez la plus longue sous-séquence croissante. Ne vous laissez pas avoir peur.
#include<bits/stdc++.h>
using namespace std;
#define For(i,l,r) for(int i=l;i<=r;i++)
const int N=2e5+10;
int n,k,a[N],ans;
int t[N],p[N][20],cnt[N];
inline int qry(int x){
int res=0;
for(;x;x-=x&(-x))res=max(res,t[x]);
return res;
}
inline void upd(int x,int v){
for(;x<=n*k;x+=x&(-x))t[x]=max(t[x],v);
}
int main(){
cin>>n>>k;
For(i,1,n*k)cin>>a[i];
For(i,1,n*k){int x;cin>>x;p[x][++cnt[x]]=i;}
For(i,1,n*k){
for(int j=k;j>=1;j--){
int res=qry(p[a[i]][j]-1)+1;
ans=max(ans,res);
upd(p[a[i]][j],res);
}
}
cout<<ans;
return 0;
}
Skip 8
Vérifiez que parmi \(k\) nombres, chaque valeur de 1 à \(k\) apparaît exactement une fois
Attribuons aux nombres de 1 à \(k\) des entiers non signés de 64 bits aléatoires \(p_i\). Prétraitement \(s_i\) pour chaque \(i (1\le i\le k)\) la somme de OU exclusif de 1 à \(i\). Vérifiez si la somme de OU exclusif des poids des \(k\) nombres est égale à \(s_k\).
\(\max(p,q)-\min(p,q)=\left |p-q \right |\).
Trouver \(mex=i \rightarrow\) trouver \(mex \geq i\).
Trouver des sous-ensembles sans chevauchement : for(int i=u;i;i=(i-1)&u)f[u]+=f[i];//i est un sous-ensemble de u.
Pour n'importe quel nœud \(u\) dans l'arbre, le nombre de chaînes lourdes sur son chemin vers la racine ne dépasse pas le nombre de chaînes légères \(-1\).
Pour n'importe quel nœud \(u\) dans l'arbre, le nombre de chaînes lourdes sur son chemin vers la racine ne dépasse pas \(O(\log n)\), et le nombre de chaînes légères ne dépasse pas \(O(\log n)\).
Skip 9
Une séquence \(a\) de longueur \(n\) satisfait\(0\le a_i < 2^m\) et les nombres de la séquence sont deux à deux distincts. On définit \(F(x)\) comme le nombre de paires inverses dans la séquence après avoir appliqué \(\forall a_i, a_i \rightarrow a_i \oplus x\).
Nous devons maintenant trouver le \(k\)-ième plus petit \(x\). On dit \(x_i<x_j\) si et seulement si \(F(x_i)<F(x_j)\), ou \(F(x_i)=F(x_j)\) et \(x_i<x_j\).
Pour 100% des données, \(1\le T\le 10\), \(1\le n,\sum n\le 10^6\), \(1\le m\le 30\), \(0\le a_i < 2^{m}\), \(1\le k\le 2^m\). On garantit que les \(a_i\) sont distincts.
Pour comparer après OU exclusif, on peut considérer bit par bit. Soit \(L\) le bit le plus significatif où deux nombres diffèrent, alors la relation de taille change si et seulement si le \(L\)-ème bit de \(x\) est 1.
:::info C'est parce que les \(L-1\) premiers bits sont les mêmes, le OU exclusif avec le même nombre n'affecte pas. Peu importe la valeur du bit \(L\) de \(x\), les deux nombres auront des bits différents à cette position, donc les bits suivants n'affectent pas la relation de taille.
Alors on peut facilement déduire que le bit \(L\) de \(x\) étant 1 peut changer la relation de taille.
\(0 \oplus 1=1,1\oplus 1=0;0 \oplus 0=0,1\oplus 0=1\) :::
Ainsi, chaque bit binaire est indépendant. Considérons de trouver le nombre initial de paires inverses, ainsi que le changement de nombre de paires inverses lorsque chaque bit binaire est mis à 1. Le premier peut être facilement trouvé par tri fusion ou arbre de Fenwick.
:::info Le changement de nombre de paires inverses signifie : regrouper les nombres avec les mêmes bits précédents, et trouver les paires inverses dans chaque groupe. :::
Pour le second, énumérons les bits binaires du plus significatif au moins significatif, trouvons les paires inverses pour les nombres avec des bits différents (seulement 0/1), puis divisons la séquence en deux sous-séquences selon ce bit, et continuons récursivement pour chaque sous-séquence. La complexité temporelle de cette partie est \(O(nm)\).
Le problème devient alors : il y a \(m\) nombres, on en choisit certains et on calcule leur somme, on doit trouver le \(k\)-ième plus petit somme. D'abord, divisons les \(m\) nombres en deux groupes de \(\frac{m}{2}\) nombres, puis pour chaque groupe, trouvons toutes les sommes possibles des sous-ensembles choisis, et trions-les. La complexité temporelle est \(O(m2^{\frac{m}{2}})\).
Le problème devient alors de choisir un élément de chaque séquence et de les combiner. On peut alors utiliser une recherche binaire sur la somme \(s\), et calculer combien de combinaisons ont une somme inférieure ou égale à \(s\). Ici, on peut utiliser deux pointeurs pour balayer les deux séquences. La complexité de cette partie est \(O(2^{\frac{m}{2}}\log n)\).
Skip 10
Quand on rencontre une suppression, on remonte le temps pour faire une addition.
"Deux points \(u,v\) ont deux chemins sans arêtes communes" et "\(u,v\) appartiennent à la même composante 2-connexe" sont des conditions nécessaires et suffisantes l'une de l'autre.
:::info Théorème de Menger : dans un graphe non orienté, le nombre maximal de chemins/disjoints en arêtes/entre deux sommets distincts \(u\) et \(v\) est égal au nombre minimal d'arêtes à supprimer pour séparer \(u\) et \(v\). :::
Problème.
La version simplifiée du problème est LeetCode 253, voici la solution de la version simplifiée.
Les concerts de chaque groupe ne peuvent pas se chevaucher, ce qui équivaut à "attribuer une couleur à chaque intervalle, et les intervalles qui se chevauchent doivent avoir des couleurs différentes". Nous avons besoin du nombre minimal de couleurs, c'est-à-dire le nombre chromatique minimal du graphe d'intervalles.
Pour tout ensemble d'intervalles, le nombre chromatique minimal = le nombre maximum de chevauchements à tout instant
Les étapes sont les suivantes. Note : quels que soient les contenus ou non des intervalles, cet algorithme est correct. Considérons que les éléments dans le tas, s'ils peuvent être utilisés maintenant, pourront aussi être utilisés plus tard, utiliser maintenant est toujours optimal. Et cela n'affectera pas les choix futurs à cause du tri, car tous les intervalles avec le même point gauche sont groupés ensemble, et quand on arrive au suivant, ils sont déjà tous entrés dans le tas.
- D'abord, triez les intervalles par point gauche croissant.
- Ensuite, utilisez une file de priorité minimale (tas), pour calculer le nombre maximum de chevauchements.
- Pour l'intervalle actuel \([l_i, r_i]\), vérifiez d'abord l'élément en haut du tas (l'heure de fin du concert le plus tôt \(top_r\)).
- Si \(top_r < l_i\), c'est-à-dire que le concert qui se termine le plus tôt se termine avant le début du concert actuel, il n'y a pas de chevauchement. Alors on retire l'élément en haut du tas. Ce groupe peut prendre le concert actuel, sans besoin de nouveau groupe.
- Ajoutez le point droit de l'intervalle actuel \(r_i\) au tas, ce qui indique qu'un nouveau concert est en cours. Si la taille du tas augmente, cela peut nécessiter plus de groupes.
- La taille du tas est le nombre de concerts en cours simultanément, ce qui correspond au nombre de groupes nécessaires à cet instant, et la valeur maximale est la réponse.
Revenons au problème original.
Considérons comment calculer le nombre de groupes pour un intervalle de temps. De gauche à droite, l'approche gourmande est correcte, hériter maintenant est toujours optimal, enregistrons les points droits qui sont encore dans le tas. Si le plus à gauche \(\le l\), on le retire et on ajoute \(r\), le coût est 0. Sinon, on ajoute directement \(r\), le coût est 1.
Considérons le nombre de couvertures à chaque instant \(t_i\), selon l'analyse ci-dessus, la réponse est \(\max t_i\).
Faisons directement du DP sur \(t_i\), posons \(t_0=t_{n+1}=0\). On remarque que la séquence \(t\) est valide si et seulement si \(\left | t_{i+1}-t_i \right |\le 1\).
On doit aussi considérer combien d'ensembles d'intervalles correspondent à \(t_i\). Si \(t_i=t_{i+1}\), considérons chaque intervalle couvrant \(i\), soit il reste, soit le point gauche le plus à gauche se termine en \(i\) et un nouvel intervalle commence en \(i+1\). Il y a au total 2 schémas.
Notons \(k=\sum_i[t_i \ne 0 \ \land \ t_i=t_{i+1}]\), alors la contribution est \(2^k\). Les schémas ici affectent indépendamment les autres positions, car on ne considère que la correspondance entre positions adjacentes, donc la contribution est 2. Les autres cas de correspondance sont uniques.
Parce qu'un ensemble d'intervalles valide et une séquence de couvertures \(t\) satisfaisant \(|t_{i+1}-t_i| \leq 1\) sont en correspondance bijective, et la relation entre les positions adjacentes \(t_i\) et \(t_{i+1}\) détermine directement l'augmentation ou la diminution des intervalles entre \(i\) et \(i+1\) (correspondant au début ou à la fin d'un intervalle), on peut uniquement déterminer la structure de l'ensemble d'intervalles par les positions adjacentes de \(t\), et ainsi calculer sa contribution, sans considérer les positions non adjacentes.
Un DP direct suffit, avec une complexité \(O(n^3)\).
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define For(i,l,r) for(int i=l;i<=r;i++)
const int p=998244353;
int n;
/*Programme dynamique pour calculer le nombre d'ensembles valides
quand on utilise au plus
k groupes
Définition de conflit :
deux concerts ont des intervalles de temps qui se chevauchent
y compris les chevauchements aux extrémités*/
ll dp(int k){
/*f[i] représente, après avoir traité tous les instants,
le nombre d'ensembles valides parmi les concerts sélectionnés
avec une profondeur de conflit maximale de i
f[i] compte tous les ensembles où les concerts sélectionnés sont complètement disjoints
par exemple, des intervalles de temps comme [1,2], [3,4], [5,6],
tout couple ne se chevauche pas, au plus un concert en même temps*/
vector<ll>f(n+1),g(n+1);
f[0]=1;
For(i,0,n-1){
fill(g.begin(),g.end(),0);
For(j,0,k){
/*Cas 1: ne pas sélectionner l'instant actuel
ou sélectionné mais sans augmentation de la profondeur de conflit
(j=0 signifie pas de conflit*/
g[j]=(g[j]+f[j]*(j?2:1))%p;
//Cas 2: de la profondeur j+1 à j
if(j+1<=k){
g[j]=(g[j]+f[j+1])%p;
}
//Cas 3: de la profondeur j-1 à j
if(j-1>=0){
g[j]=(g[j]+f[j-1])%p;
}
}
swap(f,g);
//le nouvel état devient l'ancien, l'ancien est directement écrasé
}
//retourne le total d'ensembles valides quand on utilise au plus k groupes
return (f[0]+f[1])%p;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
For(k,1,n)cout<<dp(k)<<" ";
return 0;
}
L'algorithme de Tarjan nous dit : si \(y\) est un fils de \(x\) et \(low(y)≥dfn(x)\), alors \(x\) est un point d'articulation. Si la racine \(x\) a deux arbres ou plus, alors \(x\) est un point d'articulation.
La résolution des contraintes différentielles pour le plus long chemin donne la solution minimale dans l'ordre lexicographique en présence de contraintes inférieures.
Si un chemin a son LCA sur un autre chemin, alors ces deux chemins ont une intersection, sinon non.
Le LCA d'un ensemble de points est le LCA du point avec la plus grande dfn et du point avec la plus petite dfn dans cet ensemble.
La valeur minimale des valeurs maximales sur les chemins entre deux points est la valeur du nœud LCA de ces deux points dans l'arbre de reconstruction de Kruskal.
\(\operatorname {mex}\) est égal au minimum du complément.
Pour chaque point qui n'est pas sur le plus court chemin, le plus court chemin de 1 à \(u\) utilise nécessairement un préfixe du plus court chemin.
Entre deux points, il existe un chemin simple de longueur impaire si et seulement si le chemin dans l'arbre généré entre ces deux points contient une arête appartenant à un cycle simple impair.
Une arête appartient à un cycle simple impair si et seulement si sa composante 2-connexe n'est pas un graphe biparti.