# 【排序 + 状态压缩背包】掷出重围 ## 关键性质 对于已经选定的一组球，投掷顺序不会改变最终被占据的位置集合。 考虑交换两个相邻且落点逆序的球，它们的初始落点分别为 $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...

# Miller-Rabin 与 Pollard-Rho 这两个算法通常配合使用，用来处理较大的整数： - **Miller-Rabin**：快速判断一个数是不是质数。 - **Pollard-Rho**：快速找到一个合数的非平凡因子。 - 找到因子后递归分解，就能求出一个大整数的全部质因数。 它们适合处理 $10^{18}$ 范围内的整数。 --- ##...

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

# P1850 [NOIP 2016 提高组] 换教室 ## 知识点 Floyd 最短路 + 概率期望 + 动态规划 ## 题意概括 牛牛每节课原本在教室 $c_i$，可以申请换到教室 $d_i$。第 $i$ 节课申请成功的概率为 $k_i$，最多申请 $m$ 节课。 需要选择申请哪些课程，使相邻课程教室之间最短路长度总和的期望最小。 ## 解题思路...

```cpp #include using namespace std; using ll = long long; const int N = 100005; int n, rt, tot; int ch[N][2], sz[N], va[N]; unsigned ky[N], sd = 71236721; unsigned rd() { sd ^= sd...

```cpp // Problem: P3391 【模板】文艺平衡树 // Contest: Luogu // URL: https://www.luogu.com.cn/problem/P3391 // Memory Limit: 125 MB // Time Limit: 1000 ms // by 1zhio2 // // Powered by CP...

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