OI常见题型汇总

· · 算法·理论

逆序对问题

P1908 逆序对

前置知识

P3374 【模板】树状数组1

B3694 数列离散化

思路

离散化 a 后桶排序，用树状数组维护桶 s。
第 i 个数产生的逆序对数量为：

i-\sum_{j=1}^{a_i}s_j

时间复杂度：O(n \log n)。

注意事项

注意是否要开 long long。
注意当下标从 0 开始，要 +1。

NIM游戏

P2197 NIM游戏

P1247 取火柴游戏

前置知识

博弈论

先手必胜/必败问题，无后继即为失败。

几乎所有的博弈论问题都可以归纳到NIM游戏。

发现另一类博弈问题：巴什博弈。

核心：奇数次操作先手必胜，偶数次操作先手必败。

SG 定理

博弈论的唯一定理。

假设有一个 SG 局面 x，y_1,y_2,y_3 是 x 的后继局面，则：

其中，$\text{mex}\{a,b,c\}$ 的值为最小的 $x\in \N$ 满足 $x\notin {a,b,c}$。

对于游戏的某一个状态：

思路

不妨设有三堆石子，个数分别为 a,b,c。
易知如果轮到后手时 a=b=c=0 则后手失败。
观察到如果轮到先手时 a\oplus b\oplus c\neq 0，则先手可以经过一次次操作把 a\oplus b\oplus c 变成 0。证明见后文。
所以，只要先手每次都把异或值为 0 的局面留给后手，后手就一定会领到 a=b=c=0 的无后继局面，然后失败。

在NIM游戏中，每个子局面的 SG值 为这个子局面对应石堆的石头数量。

结论

NIM游戏中，总SG值为每堆石子石头个数的异或和。

解释

为什么是异或？

\Huge\sum 待补充

矩阵加速

P1939 矩阵加速（数列）

前置知识

P3390 矩阵加速幂

思路

线性递推时间复杂度为 O(n)，而矩阵加速幂的时间复杂度能达到 O(\log n)。

所以我们要把线性递推转化为矩阵的乘方。

举例：

P1962 斐波那契数列

\begin{bmatrix}F_n & F_{n-1}\end{bmatrix} = \begin{bmatrix}F_{n-1} & F_{n-2}\end{bmatrix} \cdot \begin{bmatrix}1 & 1\\1 & 0\end{bmatrix} (n\ge 3) \begin{bmatrix}F_n & F_{n-1}\end{bmatrix} = \begin{bmatrix}1 & 1\end{bmatrix} \cdot \begin{bmatrix}1 & 1\\1 & 0\end{bmatrix} ^{n-2} (n\ge 2)

容斥问题

通过一堆集合中特定集合的交集/交集的补集，求出集合中的某些特定子集。

（给一些大面积，求出一些小面积）

可以用类似状压的方法求出，但注意如果分母可能越界，需要临时将分母提到 __int128，从而忽略过大的分母。

也可以递归求解，用子集枚举的思想，返回“这一位选”的值和“这一位不选”的值，注意容斥系数（符号位）。

递归求解也是求容斥最好的写法，因为可以提前剪枝，舍弃值过大的情况。

SOS DP

Sum over subset 动态规划。

把二进制下标看作集合，求每个母集的子集之和。

S_{101}=A_{000}+A_{001}+A_{100}+A_{101}

容斥问题的逆。

朴素算法为 O(4^n)，可以用位运算优化为 O(3^n)（快速枚举所有子集）。

进一步优化（又名 FWT 变换）：

S_{01|10}=A_{0110}+A_{0100}

求和：前缀固定为 01，后缀需要是 \{1,0\} 的子集。

S_{111}=S_{|111}=S_{1|11}+S_{0|11}

时间复杂度 O(n\cdot 2^n)，适用于 n \le 20 的数据。

可以省略至一个数组。