给定 1~n 的排列，每次只能交换下标相差 2 的元素（即同奇偶位置内任意重排），判断能否变成「山形」。关键结构刻画：值 ≥ v 的位置必须构成连续区间。区间 DP 的转移只依赖区间长度与左端奇偶性，故按平移 2 格不变性坍缩成 n 层 × 2 状态，O(n) 判定；文中附「前 m 大值奇偶计数始终不失衡」的等价闭式证明，与官方扫描解法完全等价。

将 1~N 的排列依次分配到两个变量上，最大化"当前值小于新值"的计数。核心结论：前缀最大值必贡献，剩余元素的最大贡献数为其 LIS 长度，答案 = 前缀最大值个数 + LIS(剩余序列)，时间复杂度 O(N log N)。

给定长度为 $N$ 的序列，求满足 $i < j < k$ 且 $a[i] < a[j] < a[k]$ 的三元组个数。$N \le 10^5$，$a_i \le 10^9$。通过枚举中间位置 $j$，利用权值树状数组分别统计左右两侧的可行元素个数，$O(N \log N)$ 解决。

本题给出 $m \times n$ 网格，每个格子有入口代价和罚金。从 $(0,0)$ 出发，第 $k$ 步移动方向由 $k$ 的奇偶性决定（奇数步只能右/下，偶数步只能左/上），违反规则或原地等待需支付罚金。分析指出朴素 DFS 因方向奇偶交替导致搜索空间巨大，进而将「位置 + 步数奇偶性」纳入状态，转化为 $2mn$ 个节点的隐式图，每条合法移动（含等待）建有权边，跑 Dijkstra 即可求解。文章详细推导了状态设计、转移规则，给出了 C++ 参考实现，并总结了 vis 标记时机、罚金归属、整数溢出等避坑要点。

利用康托展开 + 可重集排列计数，在 O(n·26·log n) 内求回文串所有不同排列按字典序排序后的第 k 个，通过剪枝提前判断无解情况。

每个人有一种语言，每部电影有语音与字幕两种语言，选择「语音听懂人数最多、并列时字幕听懂人数最多」的电影。先离散化语言编号，用数组统计各语言人数后线性比较，O(n+m) 解决。

NOI 2015 约束满足问题，利用并查集维护相等关系的传递性，离散化压缩变量编号后判定不等约束是否冲突，时间复杂度 O(n α(n))。

给定序列，求所有连续子段平均值的总和。把「子段和 ÷ 长度」按每个元素的贡献拆分，转化为带模逆元的系数求和，O(n) 一次扫描即可统计全部子段。

统计满足给定约束的有效序列数目。按位置依赖关系逐位确定取值，配合组合计数与贪心构造，一次线性扫描完成计数。

CSP-S 反悔贪心题：按「当前选择收益」排序后贪心选取，若后续出现更优解则用堆回退之前的决策，修正为全局最优，时间复杂度 O(n log n)。