# 【排序 + 状态压缩背包】掷出重围 ## 关键性质 对于已经选定的一组球，投掷顺序不会改变最终被占据的位置集合。 考虑交换两个相邻且落点逆序的球，它们的初始落点分别为 $a>b$。设从 $b$ 开始的第一个空位置为 $u$。 - 若 $u\0$：上一个球的最终位置为 $ w\_i+k-1. $...

# 【独立计数，快速幂】P6075 子集选取 ## 题意概括 在一个边长为 $ k $ 的三角形中放置若干个集合 $ A\_{i,j} $。 每个集合都必须是 $ S={1,2,\ldots,n} $ 的子集，并满足向左和向上包含： $ A\_{i,j}\subseteq A\_{i,j-1}, \qquad A\_{i,j}\subseteq...

# ABC468F Chmax 核心结论是： > 删除所有“前缀最大值”，剩余序列记为 $Q$。\ > 答案等于“前缀最大值个数”加上 $Q$ 的最长上升子序列长度。 官方题目给出的范围是 $N\le 5\times 10^5$，因此需要使用 $O(N\log N)$...

```cpp /* 题意：求所有线段子集的并集连通块数量之和。 思路：每个连通块由左端点最小的线段唯一代表。扫描端点，当遇到第 k 个左端点时， 已有 c 条线段完全结束。让当前线段成为新连通块起点的方案数为 2^(c+n-k)。 */ #include using namespace std; using ll=long long; const int...

# 【最大笛卡尔树，倍增 LCA】传送 ## 题意概括 有 $n$ 个星球按照编号排成一行。每个星球 $i$ 有两个传送门： - 一个传送到左侧第一个满足 $p\_j>p\_i$ 的星球。 - 一个传送到右侧第一个满足 $p\_j>p\_i$ 的星球。 - 如果对应方向不存在更大的星球，这个传送门会传回星球 $i$ 自身。 每次任务会在 $k$...

```cpp /* 题意：在 5*7 棋盘上进行 n 次横向移动，每次移动后模拟下落与连锁消除，求字典序最小通关方案。 思路：n<=5，直接 DFS。每步按 x、y、方向 1/-1 枚举；移动后反复执行下落和同时消除，并用颜色数量小于 3 的剪枝。 */ #include using namespace std; using ll=long long;...

# 【树状数组，区间最值】P2880 [USACO07JAN] Balanced Lineup G ## 题意概括 给定 $n$ 头牛的身高 $h_1,h_2,\dots,h_n$，有 $q$ 次询问。 每次询问给出区间 $[l,r]$，要求输出这个区间内最高牛和最低牛的身高差，也就是： $$...

# 【广度优先搜索，枚举】假期计划 # 题意概括 给定一张 $N$ 个点、$M$ 条边的无向连通图，点 1 代表家。需要挑选 4 个互不相同的景点，依次记为 A、B、C、D。要求在 $1 \to A \to B \to C \to D \to 1$ 的 5 段行程中，每段行程经过的最短边数不能超过 $K+1$。每个景点都有一个固定的分数，求 A、B、C、D...

# 【区间DP】算式 # 题意概括 给出 $n$ 个相对位置固定的非负整数，要求在这些数字之间填入 $k$ 个乘号和 $(n-k-1)$ 个加号。你可以通过任意添加括号来改变运算顺序，目标是找到一种运算安排，使得最终计算出的表达式结果最大。 数据保证 $2 \le n \le 15$，$0 \le k < n$，给定数字都在 $0$ 到 $9$...