算法基础

标签：frac gcd int sum 基础 times 算法 now

语言基础

取地址符

我们可以用 & 读取变量的地址。

特别的，对于数组，使用 "数组名+元素" 可以获得该变量的地址。

例如 \(f+1\) 就是 \(f\) 数组第 \(1\) 个元素的地址。

在 C/C++ 中，指针变量的类型为类型名后加上一个 *，例如 int 类型的指针为 int*。

要想访问指针变量地址所对应的空间（又称指针所 指向 的空间），需要对指针变量进行 解引用（dereference），使用 * 符号。

示例代码：

int x=9;
int *p=&x;  //定义一个整型指针，指向变量x
*p=10;  //此处的作用是把x的值改成10

结构体

结构体（struct），是自定义的数据类型，可以看做是一系列称为成员元素的组合体。

struct 在定义类型时不能赋值。

如果要对自定义数据类型进行排序，则要自定义比较规则，例如：

sort(a+1,a+1+n,cmp);

三元表达式

三元表达式类似于一个 if...else... 结构，格式：X?A:B，其中 \(X\) 为判断条件，如果 \(X\) 为 true 则调用 \(A\)，否则调用 \(B\)。

基础算法

自带函数

头文件中会自带许多基础函数

如 \(cmath\) 库中有许多数学函数，例如 \(floor,ceil,sqrt,pow\) 等。

使用 \(pow\) 函数时要注意，\(pow\) 函数返回值为浮点数，有时要类型转换。

可以使用万能头文件 bits/stdc++.h，其中整合了绝大部分常用头文件。

STL

STL提供了大约 \(100\) 个实现算法的模板函数，基本包含在 alogrithnm 中。具体信息见此。

递归

递归的基本思想是某个函数直接或者间接地调用自身，这样原问题的求解就转换为了许多性质相同但是规模更小的子问题。求解时只需要关注如何把原问题划分成符合条件的子问题，而不需要过分关注这个子问题是如何被解决的。

如求解斐波那契数列，除了使用递推，也可使用递归：

long long fibo(int x){
	if(x==1||x==2)  return 1;
	else  return fibo(x-1)+fibo(x-2);
}

排序

排序算法的目的是将一个无序序列变成有序序列，从大到小、从小到大均可，以下介绍中默认从小到大排序。

排序算法有很多种，如冒泡排序、插入排序、选择排序、归并排序、快速排序等。

我们定义一个排序算法是稳定的，仅当排序后，原先数值相同的数字的相对位置不变。

冒泡排序

冒泡排序是最基础的排序算法之一。

冒泡排序共进行 \(n\) 次循环，每次两两比较相邻数字，如果编号小的数值大，则将两个数字交换。容易证明，第 \(1\) 次确定第 \(1\) 大数字，第 \(2\) 次确定第 \(2\) 大数字。以此类推。

该算法是稳定的，时间复杂度为 \(O(n^2)\)，空间复杂度为 \(O(1)\)。

示例代码：

for(int i=1;i<=n;i++){
	for(int j=1;j<i;j++){
		if(a[j]>a[j+1])  swap(a[j],a[j+1]);
	}
}

选择排序

选择排序进行 \(n\) 次循环，第 \(i\) 次找出 \(a_{i,i+1,...,n}\) 中最小的数，与 \(a_i\) 交换。

该算法是不稳定的，时间复杂度为 \(O(n^2)\)，空间复杂度为 \(O(1)\)。

示例代码：

for(int i=1;i<=n;i++){
	int x=i;
	for(int j=i+1;j<=n;j++){
		if(a[j]<a[x])  x=j;
	}
	swap(a[i],a[x]);
}

或可以用 min_element 减少码量，但不能优化复杂度。

插入排序

插入排序将将数组分为“无序”和“有序”两个部分，每次从无序中找到一个数字，插入“有序”序列的恰当位置。

该算法是稳定的，时间复杂度为 \(O(n^2)\)，空间复杂度为 \(O(1)\)。

理论上，可以用二分查找将该算法优化为 \(O(n\log n)\)，但在数组中没法实现，需要一种可以在常数时间内随机插入的数据结构。

for(int i=1;i<=n;i++){
	int j=i-1;
	while(j>=1&&a[j]>a[j+1]){
		swap(a[j],a[j+1]);
		j--;
	}
}

STL sort 与 stable_sort

sort 函数是 STL 自带的排序函数，内部由快速排序实现，时间复杂度为 \(O(n\log n)\)，实现也非常方便，只有 \(1\) 行：

sort(a+1,a+1+n);

stable_sort 与 sort 类似，但内部使用归并排序实现：

stable_sort(a+1,a+1+n);

数论

基础符号

\(\sum\)，用于表示几个数的和，如 \(\sum^n_{i=1}i\) 表示 \(1\) 到 \(n\) 的和。

\(\prod\)，用于表示几个数的积，如 \(\prod^n_{i=1}i\) 表示 \(n !\)，即 \(n\) 的阶乘。

\(!\)，即阶乘。

\(\lfloor \rfloor\)，\(\lceil \rceil\)，表示向下/向上取整。

\((^x_y)\)，即组合数。

数位分离

数位分离是一种很基础的处理方法，可以删除或取出一个数中特定几位的数字，一般使用 / 和 % 来实现，例如：

• 取出 \(x\) 的百位数字：x/100%10。
• 删除 \(x\) 的最后 \(3\) 位数字：x/=1000。
• 取出 \(x\) 的最后三位数字：x%1000。

整除

基本概念：

1. 整数集合：\(Z= \{...,-2,-1,0,1,2,...\}\)
2. 自然数集合： \(N= \{ 0,1,2,... \}\)
3. 整除：对于整数 \(a,b,k\)，若 \(a=bk\)，则称 \(b\) 整除 \(a\)，记作 \(b|a\)，否则记作 \(b∤a\)。
4. 约数：如果 \(b|a\) 且\(b \geq 0\)，则称 \(b\) 是 \(a\) 的约数。而 \(a\) 是 \(b\) 的倍数。

\(1\) 整除任何数，任何非零数都整除 \(0\)。

可以得到以下性质：

1. 若 \(a|b,a|c\)，那么 \(a|(b+c)\),\(a|(b-c)\)。
2. 若 \(a|b,b|c\)，那么 \(a|c\)。
3. 若 \(a|b\)，那么对于任意整数 \(c\)，\(a|(bc)\)。
4. 若 \(a|b,a|c\)，那么对于任意整数 \(x,y\)，\(a|(bx + cy)\)。

素数与合数

基本概念：

因子：对于任意正整数 \(a\)，除 \(1\) 和 \(a\) 外的 \(a\) 的约数称为 \(a\) 的因子。

素数：\(a>1\) 且只能被 \(1\) 与 \(a\) 整数的正整数。

合数：\(a>1\) 且不是素数的正整数为合数。

\(0,1\) 与负整数既不是素数也不是合数。

素数的判定：对于正整数 \(a\)，如果 \([2,\sqrt{n}]\) 中有 \(a\) 的因数，则 \(a\) 是素数，否则 \(a\) 是合数。

如果整数 \(n\geq 2\)，那么 \(n\) 一定可以唯一表示为若干素数的乘积，形如 \(n={p_1}^{r_1}{p_2}^{r_2}...{p_m}^{r_m}\)。

因此还可以有以下推论：

1. \(n\) 的正约数个数为 \(\displaystyle\prod_{i=1}^k(r_i+1)\)。
2. 除完全平方数以外，约数总是成对出现，即对于正整数 \(n\)，如果其中一个约数为 \(r\)，那么必定有一个约数为 \(\frac{n}{r}\)。
3. \(n\) 的约数个数的上界为 \(2\sqrt{n}\)。
4. \(n\) 的正约数的和为 \(\displaystyle\prod^k_{i+1}(\displaystyle\sum_{j=0}^{r_i}(p_j)^i)\)。

对第 \(1\) 条推论的证明：

对于正整数 \(n\)，其任意一个正约数必定是由它的几个质因数相乘得到的（可以是 \(0\) 个，那这个约数就是 \(1\)），第 \(i\) 个质因数可以取 \(0,1,...,r_i\) 个，共 \(r_i+1\) 种取法，那么根据排列原理，一共有 \(\displaystyle\prod_{i=1}^k(r_i+1)\) 个约数。

还可以 \(O(n)\) 求解前 \(n\) 个数的约数之和：\(1\)的贡献为 \(n\)，\(2\) 的贡献为 \(\lfloor \frac{n}{2} \rfloor\)，以此类推，\(n\) 的贡献为 \(1\)，因此答案为 \(\displaystyle\sum^n_{i=1}\lfloor \frac{n}{i} \rfloor\)。

筛素数

1.Eratosthenes筛法

算法思想：求 \([2,n]\) 之内的素数，从小到大枚举 \(i\)，如果 \(i\) 标记为素数，则枚举倍数 \(x\)，把 \(x \times i\) 标记为合数。

可以做一个优化：对于素数 \(p\)，只筛倍数 \(x \geq p\) 即可，因为 \(x<p\) 的数肯定会在前面被筛出。

该算法的时间复杂度约为 \(O(n \log \log n)\)

2.欧氏筛法

埃氏筛法的复杂度中还有一个 \(\log \log n\) 的复杂度，有可能会导致超时，有没有 \(O(n)\) 时间复杂度的筛法？

如果能保证每个数只被它的最小素因数筛除，那么每个数最多被筛一次，这就是欧氏筛法。

欧氏筛法的流程如下：

枚举 \(2 - n\) 中的每一个数 \(i\) ，如果 \(i\) 是素数则保存到素数表，并利用 \(i\) 和素数表中的每一个素数 \(j\)，去筛除 \(i \times j\)。

为了确保 \(i \times j\) 只被 \(j\) 筛除过一次，要球包 \(i\) 中不能有比 \(j\) 还小的素因子，如果有则说明肯定被更小的素数筛除过，\(break\)。

最大公约数

设 \(a,b\) 均为不为 \(0\) 的整数，整数 \(c\) 为满足 \(c|a\) 且 \(c|b\) 的最大整数，则称 \(c\) 为 \(a,b\) 的最大公约数，记作 \(gcd(a,b)\)。

最大公约数的性质：

1. \(gcd(a,b)=gcd(b,a)\)
2. \(gcd(a,b)=gcd(-a,b)\)
3. \(gcd(a,0)=a\)
4. \(gcd(a,ka)=a\)
5. \(gcd(a,b)=gcd(|a|,|b|)\)
6. \(gcd(ab,bn)=n \times gcd(a,b)\)
7. 如果 \(d|a,d|b\)，则 \(d|gcd(a,b)\)
8. \(gcd(a,b)=gcd(a,ka+b)\)

欧几里得算法

设 \(d\) 为 \(a\) 和 \(b\) 的公约数，则由 \(a=ld\)，\(b=md\)。

将 \(a=ld\) 代入 \(a=bq+r\) 得到 \(ld=bq+r\)。再将 \(b=md\) 代入，得到 \(ld=mdq+r\)。

整理可得 \(r=(l-mq)d\)，因此 \(d\) 为 \(r\) 的约数，所以 \(d\) 是 \(r\) 和 \(b\) 的公约数。

因此 \(a\) 和 \(b\) 的最大公约数等于 \(b\) 和 \(r\) 的最大约数（\(r\) 为 $a \bmod b $），当 \(a\) 是 \(b\) 的倍数时，答案即为 \(b\)。

该算法即为欧几里得算法（辗转相除法），时间复杂度为 \(O(\log(a+b))\)。

最小公倍数

\(a\) 和 \(b\) 的最小正公倍数即为 \(a\) 和 \(b\) 的最小公倍数，记作 \(lcm(a,b)\)。

$lcm(a,b)=\frac{a \times b}{gcd(a,b)} $。

\(lcm\) 还有如下性质：

1. 若 \(a|m\) 且 \(b|m\)，则 \(lcm(a,b)|m\)
2. \(lcm(ma,mb)=m \times lcm(a,b)\)

计算 \(a_1,a_2,...,a_n\) 的最小公倍数可以这样做：

计算 \(a_1\) 和 \(a_2\) 的最小公倍数 \(s_1\)，再计算 \(s_1\) 和 \(a_3\) 的最小公倍数 \(s_2\)，以此类推，计算 \(s_{n-2}\) 和 \(a_n\) 的最小公倍数 \(s_{n-1}\)，\(s_{n-1}\) 即为这 \(n\) 个数的最小公倍数。

欧拉函数

若 \((a,b)=1\)，则称 \(a,b\) 互素，记作 \(a \bot b\)。

欧拉函数 \(φ(n)\)，定义为 \([1,n]\) 中与 \(n\) 互素的数的个数。

若 \(p\) 是质数，则 \(φ(p)=p-1\)。

可以利用容斥原理求欧拉函数：

将 \(N\) 分解为 \({p_1}^{r_1}{p_2}^{r_2}...{p_m}^{r_m}\)。

设 \(1\) 到 \(n\) 个数中 \(p_i\) 的倍数的集合为 \(A_i\)，则 \(|A_i|=\lfloor\frac{N}{p_i}\rfloor\)。

对于 \(p_i \neq p_j\)，\(|A_i ∩ A_j|\) 表示 \(p_i\) 与 \(p_j\) 的公倍数，可以得到 \(|A_i ∩ A_j|=\lfloor\frac{N}{p_i \times p_j}\rfloor\)。

在去除 \(|A_i|\) 和 \(|A_j|\) 的时候会把 \(|A_i ∩ A_j|\) 去除 \(2\) 次，需要加回来。

因此 \(φ(n)=|A_1 ∩ A_2 ∩ ... \space ∩ A_k|\)

\(=N(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})\)

时间复杂度为 \(O(\sqrt{n})\)。

还有另外一种方法：

定理 \(1\)：\(φ(a)=a-1\)（\(a\) 为质数）。

定理 \(2\)：\(φ(p^k)=p^k-p^{k-1}\)（ \(p\) 为质数）。

定理 \(3\)：\(φ\) 是一个积性函数，即\(φ(x\times y)=φ(x)\times φ(y)\)，当且仅当 \(gcd(x,y)=1\)。

对定理 \(2\) 的证明：

因为 \(p\) 为质数，所以 \(1,2,...,p-1\) 中与 \(p\) 不互质的数一定可以表示为 \(t \times p\) 的形式，而 \(t\) 的范围为 \(1,2,...,p^{k-1}\)，因此得证。

想要求 \(φ(n)\)，把 \(n\) 分解质因数可以得到 \(n={p_1}^{r_1}{p_2}^{r_2}...{p_m}^{r_m}\)。

分解质因数后的每一项必定两两互质，因此由定理 \(3\) 得 \(φ(n)=φ(p_1^{r_1}) \times φ(p_2^{r_2}) \times ... \times φ(p_k^{r_k})\)。

同时把定理 \(2\) 变形得 \(φ(p^k) = p^k -p^{k-1}=p^k \times (1-\frac{1}{p})\)。

那么 \(φ(a)=p_1^{r_1} \times (1-\frac{1}{p_1}) \times ...\space \times p_k^{r_k} \times (1-\frac{1}{p_k})\)。

化简得 \(φ(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})\)

同时利用埃氏筛法，每次发现素因子就把它的倍数的欧拉函数乘上 \(\frac{p-1}{p}\)，可以求出 \(1-n\) 的欧拉函数表。

同余

余数：把 \(a\) 除以 \(m\) 的余数 \(r\) 记作 \(r=a\bmod m\)。

除法定理：对于整数 \(a\)，正整数 \(m\)，存在唯一整数 \(q,r\)（\(q=\frac{a}{m}\)，\(r=a\bmod m\)）满足 \(0 \leq r < m\) 且 \(a=qm+r\)。

同余：如果 \(a \bmod m=b\bmod m\)，那么我们称 \(a\) 和 \(b\) 除以 \(m\) 的余数相等，记作 \(a \equiv b \pmod m\)。

剩余系：指模正整数 \(n\) 所组成的余数的集合。

如果与各剩余系中包含了 \(n\) 所有可能的余数，那我们称这个剩余系是模 \(n\) 的完全剩余系，记作 \(Z_n\)。

化简剩余系指的是完全剩余系中与 \(n\) 互素的数，记作 \(Z^*_n\)。

\(Z_n\) 中的每一个元素实际上代表所有与它模 \(n\) 同余的整数，我们把所有满足同余关系的整数看作一个同于等价类。

自然地，在 \(Z_n\) 中的运算也要在模 \(n\) 的意义下面。

如果 \(a \equiv b \pmod m\) 且 \(c \equiv d \pmod m\)，那么下面的模运算成立：

\[a+c \equiv b+d \pmod m \]

\[a-c \equiv b-d \pmod m \]

\[a \times c \equiv b \times d \pmod m \]

还有以下 \(3\) 条：

\[a+b \bmod m=(a \bmod m + b \bmod m) \bmod m \]

\[a-b \bmod m=(a \bmod m - b \bmod m) \bmod m \]

\[a \times b \bmod m=(a \bmod m \times b \bmod m) \bmod m \]

快速幂取模

可以在 \(O(\log n)\) 的时间内计算 \(a^n \bmod m\) 的值。

\[pow(a,n,m)=\begin{cases} 1 \space (n=0)\\ pow(x^2,\frac{n}{2}) \bmod m \times x \bmod m \space (n \bmod 2 =1 )\\ pow(x^2,\frac{n}{2}) \bmod m \space (n \bmod 2 = 0) \end{cases} \]

费马小定理

若 \(p\) 为素数，\(a\) 与 \(p\) 互素，可以得到：

\[a^{p-1} \equiv 1 \pmod p \]

证明：

\(p-1\) 个整数 \({a,2a,3a,...,(p-1)a}\) 中没有 \(p\) 的倍数，且任意 \(2\) 个数都模 \(p\) 不同余，因此这 \(p-1\) 个数对模 \(p\) 的同余式 \(1,2,3,...,p-1\) 的排列。

可得 \(a \times 2a \times 3a \times ... \times (p-1)a \equiv 1 \times 2 \times 3 \times ... \times p-1 \pmod p\)

化简得 \(a^{p-1} \equiv 1 \pmod p\)

费马小定理的应用：\(p\) 是素数，\(a,p\) 互素，则 \(a^b \equiv a^{b \bmod (p-1)} \pmod p\)

欧拉定理

在 \(m\) 不是素数的情况下，对于 \(m\) 和与 \(m\) 互素的\(a\)，有：

\[a^{φ(m)}\equiv 1 \pmod m \]

当 \(m\) 是素数的时候就是费马小定理。

从欧拉定理还能有如下推论：

如 \(a,m\) 互素，可得 \(a^b \equiv a^{b \bmod φ(m)} \pmod m\)。

证明：

设 \(b=q\times φ(m)+r \space(0 \leq r < φ(m))\)，即 \(r=b \bmod φ(m)\)，则：

\[a^b \equiv a^{qφ(m)+r} \equiv (a^{φ(m)})^qa^r\equiv 1^qa^r \equiv a^r \equiv a^{b \bmod φ(m)} \pmod m \]

扩展欧几里得算法

裴蜀定理

裴蜀等式：对于整数 \(a,b\)，未知数 \(x,y\) 的线性不定方程：

\[ax+by=c \]

裴蜀定理：\(ax+by=c\) 有解的充分必要条件为 \(gcd(a,b)|c\)，且一旦有解，必定有无穷多个解。

一定存在 \(x,y\) 满足 \(ax+by=gcd(a,b)\)。

推论：\(a,b\) 互素等价于 \(ax+by=1\) 有解。

对裴蜀定理的证明

裴蜀定理的必要性证明：如果 \(ax+by=c\) 有解，则 \(c\) 是 \(gcd(a,b)\) 的倍数。

令 \(d=gcd(a,b)\),则：

\[a=a'd \]

\[b=b'd \]

\[gcd(a',b')=1 \]

\[c=ax+by=a'dx+b'dy=d(a'x+b'y) \]

因此 \(c\) 显然为 \(d\) 的倍数。

裴蜀定理充分性证明：如果 \(c\) 是 \(gcd(a,b)\) 的倍数，则 \(ax+by=c\) 有解。

\(gcd(a,b)\) 的最后一步为 \(gcd(d,0)\)，对于 \((d,0)\) 来说是存在 \(dx+0y=c\) 有解，此时 \(x=\frac{c}{d},y\) 取任意实数。

辗转相除法的核心为 \(gcd(a,b)=gcd(b,a \bmod b)\)，假设 \(gcd(b,a \bmod b)\) 存在 \((x_1,y_1)\) 使得 \(bx_1+(a \bmod b)y_1=c\)，则

\[ax+by \]

\[=bx_1+(a \bmod b)y_1 \]

\[=bx_1+(a-\lfloor\frac{a}{b}\rfloor b)y_1 \]

\[=bx_1+ay_1-\lfloor\frac{a}{b}\rfloor b \space y_1 \]

\[=ay_1+b(x_1-\lfloor\frac{a}{b}\rfloor y_1) \]

可得

\[x=y_1,y=x_1-\lfloor\frac{a}{b}\rfloor y_1 \]

即当 \(c\) 为 \(gcd(a,b)\) 的倍数时，必定存在整数解满足 \((x,y)\) 满足 \(ax+by=c\)，充分性得证。

扩展欧几里得算法

\[ax+by=gcd(a,b)=gcd(b,a \bmod b)=bx'+(a \bmod b)y' \]

其中 \(a \bmod b=a-\lfloor \frac{a}{b} \rfloor b\)，代入得：

\[ax+by=gcd(a,b)=gcd(b,a-\lfloor \frac{a}{b} \rfloor b)=bx'+(a \bmod b)y' \]

可以得出 \(x\) 和 \(x'\)，\(y\) 和 \(y'\) 的关系：

\[x=y',y=x'-\lfloor \frac{a}{b} \rfloor y' \]

边界情况分析：\(ax'+by'=d(d=gcd(a,b))\)，当 \(b\) 等于 \(0\) 时，\(a\) 为 \(gcd(a,b)\)，此时 \(x'\) 当且仅当等于 \(1\) 时才成立，\(y'\) 可以取任意数值，为方便起见，设 \(y'=0\)

根据

\[x=y',y=x'-\lfloor \frac{a}{b} \rfloor y' \]

可以倒推出 \(ax+by=c\) 的多组解。

求出 \(ax+by=c\) 的其它解

\(ax+by=1\) 的一组特解为 \((x_0,y_0)\)，下一组特解是 \((x_1,y_1)\) 可以表示为 \((x_0+d_0,y_0+d_1)\)，满足：

\(a(x_0+d_0)+b(y_0+d_1)=c\)，因为 \(ax_0+by_0=c\)，所以 \(ad_0+bd_1=0\)，因此：

\[\frac{d_0}{d_1}=-\frac{b}{a}=-\frac{\frac{b}{gcd(a,b)}}{\frac{a}{gcd(a,b)}} \]

可得 \(x_1=x_0+k(\frac{b}{gcd(a,b)}),y_1=y_0+k(\frac{a}{gcd(a,b)})\)，其中 \(k ∈Z\)。

集合

容斥原理

集合：由一个或多个确定的元素所构成的整体。

集合大小：集合的元素个数，记作 \(|A|\)。

补集：对于集合 \(S\) 和它的子集 \(A\) ， \(A\) 的补集就是 \(S\) 中所有不属于 \(A\) 的元素的集合。

交集：对于两个集合 \(A\) 和 \(B\) ，他们的交集就是同时在 \(A\) 和 \(B\) 中的元素，记作 \(A∩B\)。

并集：对于两个集合 \(A\) 和 \(B\)，把他们所有的元素合并在一起组成的集合就是他们的并集，记作 \(A∪B\)。

容易发现， \(|A∪B|=|A|+|B|-|A∩B|\)。

进一步的，对于一个集合 \(S\) 和它的三个自己 \(A,B,C\)，则：

\(|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|B∩C|-|A∩C|-|A∩B∩C|\)，其补集的大小为 \(|S|-|A∪B∪C|\)。

更多个集合的并集也可以以此类推。

容斥原理：具有性质 \(A\) 或性质 \(B\) 的元素个数，等于具有性质 \(A\) 的元素个数与具有性质 \(B\) 的元素个数的和，减去同时具有性质 \(A\) 和 \(B\) 的元素的个数，使得计算个数既无遗漏又无重复。

概率与数学期望

概率论

样本点：一个随机试验的某种可能的结果。

样本空间 \(Ω\)：所有可能结果构成的集合

随机事件 \(A\)：在一个给定的样本空间中，样本空间的子集，即由多个样本点构成的集合。

随机变量 \(P(A)\)：把样本点映射为实数的函数，分为离散型、连续型。离散型随机变量的取值为有限或实数。

我们称 \(P(A)\) 为随机事件 \(A\) 发生的概率，概率是对随机事件发生可能性的一个度量方式，是 \([0,1]\) 之间的一个实数。需要满足以下条件：

1. \(P(A) \geq 0\)
2. \(P(Ω) = 1\)
3. 对于两两互斥的事件 \(A_1,A_2,...\) 有 \(\sum P(A_i)=P(\cup A_i)\)

数学期望

简而言之：它是概率和随机变量取值乘积之和。

若随机变量 \(X\) 的取值有 \(x_1,x_2,...\) ，一个随机事件可以表示为 \(X=X_i\) 其概率为 \(P(X=X_i)=p_i\)，则它的数学期望为 \(E(x)=\sum p_i \times x_i\)

例如投掷 \(2\) 枚骰子的实验，两个骰子为 \(x\) 和 \(y\)。

样本空间：共有 \(36\) 个样本点，每个样本点可以写作 \((x,y)\) \(1\leq x,y \leq 6\)

随机变量，取值范围为 \([2,12]\)，\(x+y=X\) 的样本点 \((x,y)\) 构成的子集。

两个骰子掷出的点数的数学期望为 \(7\)

数学期望的线性

满足 \(E(aX+bY)=a \times E(X) + b \times E(Y)\)

因此可以对数学期望进行递推求解

用随机变量 \(X\) 表示掷出一个骰子的点数，显然期望值为 \(E(X)= (1+2+3+4+5+6) \div 6=3.5\)，而 \(2\) 枚骰子的期望为 \(2X=7\)。

字符串

基础函数

.size()：计算字符串的长度，.length() 的效果与其类似。

.substr()：用于提取字符串中的一段子串。

• s.substr(x)：从字符串 \(s\) 中提取从第 $x $ 个开始的字符。
• s.substr(x,L)：从字符串 \(s\) 中提取第 \(x \sim x+L-1\) 个字符。

.substr() 并不会改变原字符串的内容。

s.insert(p,t)：在字符串 \(s\) 中 \(p\) 号位置插入字符串 \(t\)。

.erase()：用于删除字符串中的一段子串。

• s.erase(p)：删除字符串 \(s\) 中从第 \(p\) 个开始的字符。
• s.erase(p,L)：删除字符串 \(s\) 中第 \(p \sim p+L-1\) 个字符。

.find()：用于查找子串

• s.find(t)：查找字符串 \(t\) 在字符串 \(s\) 中第一次出现的位置，没有则返回 \(-1\)
• s.find(t,p)：查找字符串 \(t\) 在字符串 \(s\) 的第 \(p\) 个字符起第一次出现的位置，没有则返回 \(-1\)。

使用以上函数时要注意字符串编号从 \(0\) 开始的问题。

KMP

KMP算法，是一种能在 \(O(n+m)\) 的时间内求出模式串 \(A\)（长度为 \(m\)）在文本串 \(B\)（长度为 \(n\)） 中出现的次数及位置的字符串匹配算法。

KMP算法共分为 \(2\) 步：

第 \(1\) 步，对 \(A\) 串进行自我匹配，求出 \(nxt\) 数组，\(nxt[i]=max\{j\}\)，其中 \(j<i\) 且 \(A[i-j+1 \sim j]=A[1 \sim j]\)。

第 \(2\) 步，用 \(A\) 串去匹配 \(B\) 串，求出 \(f\) 数组，其中 \(f[i]=max\{j\}\)，其中 \(j \leq i\) 并且 \(B[i-j+1 \sim i]=A[1 \sim j]\)。

如何快速计算 \(nxt\) 数组？

若 \(j_0\) 是 \(nxt[i]\) 满足条件的选项（以下称为“候选项”），那小于 \(j_0\) 中最大的候选项是 \(nxt[j_0]\)。

在计算 \(nxt[i]\) 时，只要把 \(nxt[i-1]+1\)，\(nxt[nxt[i-1]]+1\)，\(...\) 作为候选项即可。

\(f\) 数组可以用相同方法计算。

#include<iostream>
#include<cstring>
#define MAXN 1000005
using namespace std;
int Next[MAXN];
int len_a,len_b; 
char a[MAXN],b[MAXN];
int main(){
    cin >> a+1;
    cin >> b+1;
    len_a = strlen(a+1);
    len_b = strlen(b+1);
    Next[1] = 0;
    for (int i = 2,j = 0; i <= len_b; i++){     
        while(j > 0 && b[i] != b[j+1]) j = Next[j];
        if(b[i] == b[j+1]) j++;    
        Next[i] = j;
    }
    for (int i = 1, j = 0; i <= len_a; i++){
        while(j > 0 && b[j+1] != a[i]) j = Next[j];
        if (b[j+1] == a[i]) j++;
        //输出匹配位置，然后继续匹配
        if (j == len_b) { cout << i-len_b + 1 << endl; j = Next[j];}
       }
    for (int i = 1; i <= len_b; i++)
    cout << Next[i] << " ";
    return 0;
}

动态规划

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

由于动态规划并不是某种具体的算法，而是一种解决特定问题的方法，因此它会出现在各式各样的数据结构中，与之相关的题目种类也更为繁杂。

在 OI 中，计数等非最优化问题的递推解法也常被不规范地称作 DP。

能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。

（以上摘自 OI wiki）

在动态规划的问题中常常会要求取模，此时要注意每步计算都要取模，避免中间步骤溢出。

线性动态规划

例题：小明共有 \(n\) 级楼梯要走，每一步可以向上走 \(1\) 级或 \(2\) 级，请问一共有多少种不同的方法。

令 \(f[i]\) 代表走到第 \(i\) 级共有几种走法，则

\[f[i]=f[i-1]+f[i-2](i \geq 3) \]

初始条件：\(f[1]=1,f[2]=2\)。

这是最简单的一种线性动态规划。

卡特兰数

卡特兰数可以用递推求解，递推式为：

\[f[i]=f[i-1] \times \frac{4i-2}{i+1}(i\geq2) \]

初始条件：\(f[1]=1\)

卡特兰数的应用：

1. 有一排山共 \(n\) 次上坡和 \(n\) 次下坡，求山的形状有多少种可能性
2. 有 \(2n\) 个人排成一行进入剧场。入场费 \(5\) 元。其中只有 \(n\) 个人有一张 \(5\) 元钞票，另外 \(n\) 人只有 \(10\) 元钞票，剧院无其它钞票，问有多少种方法使得只要有 \(10\) 元的人买票，售票处就有 \(5\) 元的钞票找零？
3. 共 \(n\) 个物品编号 \(1 \sim n\)，依次入栈，求出站顺序共几种可能性。
4. 对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数？

关于卡特兰数的更多信息参考此处。

数据结构

线段树

线段树是用于在区间上进行信息统计的二叉树。

线段树的性质

1. 每个节点都代表一个区间。
2. 有唯一的根节点，代表整体区间
3. 每个夜间点代表长度为 \(1\) 的单位区间
4. 出叶节点和根节点之外的内部节点 \([l,r]\)，取 \(mid=\lfloor\frac{1+r}{2}\rfloor\)，左子节点为 \([l,mid]\)，右子节点为 \([mid+1,r]\)。
5. 除最后一层，线段树为完全二叉树，深度为 \(\log n\)。
6. 如果用数组来保存线段树，长度需要 \(4n\)，故会有空间上的浪费。

线段树的建立

对于区间 \([p,l,r]\)，\(p\) 表示节点编号，\(l\) 为区间左端点，\(r\) 为区间右端点。

如果 \(l=r\)，说明已经递归到了叶子节点，直接把对应的区间值放进去即可，然后返回。

否则，将区间分成左右两部分进行递归。取 \(mid=\lfloor\frac{1+r}{2}\rfloor\)，左子节点为 \([l,mid]\)，右子节点为 \([mid+1,r]\)。在左右子节点都完成递归之后，按照题意对该节点的数值进行维护，然后返回。

void build(int p,int l,int r){
	t[p].l=l,tree[p].r=r;
	if(l==r){
		t[p].num=a[l];
		return ;
	}
	int mid=l+(r-l)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	t[p].dat=max(t[p*2].dat,t[p*2+1].dat);  
    //注意对于不同的题目维护的值会不一样，在此处为维护区间最大值
	return ;
}

线段树的单点修改

线段树的单点修改遵循以下步骤：

假设修改第 \(x\) 个节点，从根节点出发，递归找到区间 \([x,x]\) 的节点，更新值。

从下往上，依次更新父节点的信息，维护线段树的性质。

void modify(int p,int k,int val){
	int l=t[p].l,r=t[p].r;
	if(l==r){
		t[p].dat=val;
		return ;
	}
	int mid=l+(r-l)/2;
	if(k<=mid)  modify(p*2,k,val);
	else  modify(p*2+1,k,val);
	t[p].dat=max(t[p*2].dat,t[p*2+1].dat);  //此处维护区间最大值
	return ;
}

线段树的区间查询

对于一个区间 \([L,R]\) 的查询，必定能分成不超过 \(\log n\) 个子区间进行分别查询。

如果现在查到了区间 \([l,r]\)，如果 \(L \leq l \leq r \leq R\)，则直接返回该区间的值，否则对该区间进行分治查询。时间复杂度为 \(O(\log n)\)。

int query(int p,int L,int R){
	int l=t[p].l,r=t[p].r;
	if(l>=L&&r<=R)  return t[p].dat;
	int mid=l+(r-l)/2;
	int res=-(1<<30);
	if(L<=mid)  val=max(res,query(p*2,L,R));
	if(R>mid)  val=max(res,query(p*2+1,L,R));
	return res;
}

线段树的区间修改

在区间修改时，如果某个节点 \(P\)，被修改区间 \([l,r]\) 全部覆盖，那么 \(P\) 和 \(P\) 的子树全部要修改，时间复杂度最高位 \(O(n)\)。

而且，如果 \(P\) 修改了之后没有被查询到，那么修改 \(P\) 就是徒劳的。

lazy tag

lazy tag 给 \(P\) 节点增加标记，代表“此节点有更新，但子节点尚未被更新”。

如果在后续指令中，需要从节点 \(P\) 向下递归，那么：

1. 检查标记状态，根据标记更新 \(P\) 的子节点。
2. 给 \(P\) 的子节点更新标记状态。
3. 删除 \(P\) 的标记状态。

这样做，区间修改的复杂度就降至 \(O(\log n)\)

void pushdown(int p){
	if(t[p].tag){
		t[p*2].sum+=t[p].tag*(t[p*2].r-t[p*2].l+1);
		t[p*2+1].sum+=t[p].tag*(t[p*2+1].r-t[p*2+1].l+1);
		t[p*2].tag=t[p].tag;
		t[p*2+1].tag=t[p].tag;
		t[p].tag=0;
	}
	return ;
}

在 \(modify\) 和 \(query\) 时都需要 \(pushdown\)。

例题 \(1\) SP1716

本题在每个节点中，除了维护区间端点外，还要维护以下 \(4\) 个值：

区间和 \(sum\)，区间最大连续字段和 \(ans\)，靠左端的最大连续字段和 \(lmax\)，靠右端的最大连续字段和 \(rmax\)。

此外需要在 \(build\) 和 \(modify\) 函数中从下往上传递：

t[p].sum=t[p*2].sum+t[p*2+1].sum;
t[p].lmax=max(t[p*2].lmax,t[p*2].sum+t[p*2+1].lmax);
t[p].rmax=max(t[p*2+1].rmax,t[p*2+1].sum+t[p*2].rmax);
t[p].ans=max(t[p*2].ans,max(t[p*2+1].ans,t[p*2].rmax+t[p*2+1].lmax));

对于叶子节点，\(sum,lmax,rmax,ans\) 均为 \(a[l]\)。

例题 \(2\) P3373

本题维护两个 \(tag\)：乘法 \(tag\) 和加法 \(tag\)。但要注意运算的优先级，在更新加法 \(tag\) 之前需要把乘法 \(tag\) 先 \(pushdown\)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct tree{
	ll sum,tag1,tag2;
}t[400009];
ll n,m,p,a[100009];
void build(ll now,ll l,ll r){
	t[now].tag1=1;
	t[now].tag2=0;
	if(l==r){
		t[now].sum=a[l];
		return ;
	}
	ll mid=l+(r-l)/2;
	build(now*2,l,mid);
	build(now*2+1,mid+1,r);
	t[now].sum=(t[now*2].sum+t[now*2+1].sum)%p;
	return ;
}
void pushdown(ll now,ll l,ll r){
	ll mid=l+(r-l)/2;
	t[now*2].sum=(t[now*2].sum*t[now].tag1+t[now].tag2*(mid-l+1))%p;
	t[now*2+1].sum=(t[now*2+1].sum*t[now].tag1+t[now].tag2*(r-mid))%p;
	t[now*2].tag1=(t[now*2].tag1*t[now].tag1)%p;
	t[now*2+1].tag1=(t[now*2+1].tag1*t[now].tag1)%p;
	t[now*2].tag2=(t[now*2].tag2*t[now].tag1+t[now].tag2)%p;
	t[now*2+1].tag2=(t[now*2+1].tag2*t[now].tag1+t[now].tag2)%p;
	t[now].tag1=1;
	t[now].tag2=0;
	return ;
}
void modify1(ll now,ll L,ll R,ll l,ll r,ll k){
	if(r<L||l>R)  return ;
	if(L<=l&&R>=r){
		t[now].sum=(t[now].sum*k)%p;
		t[now].tag1=(t[now].tag1*k)%p;
		t[now].tag2=(t[now].tag2*k)%p;
		return ;
	}
	pushdown(now,l,r);
	ll mid=l+(r-l)/2;
	if(mid>=L)  modify1(now*2,L,R,l,mid,k); 
	if(mid+1<=R)  modify1(now*2+1,L,R,mid+1,r,k);
	t[now].sum=(t[now*2].sum+t[now*2+1].sum)%p;
	return ;
}
void modify2(ll now,ll L,ll R,ll l,ll r,ll k){
	if(r<L||l>R)  return ;
	if(L<=l&&R>=r){
		t[now].sum=(t[now].sum+(r-l+1)*k)%p;
		t[now].tag2=(t[now].tag2+k)%p;
		return ;
	}
	pushdown(now,l,r);
	ll mid=l+(r-l)/2;
	if(mid>=L)  modify2(now*2,L,R,l,mid,k); 
	if(mid+1<=R)  modify2(now*2+1,L,R,mid+1,r,k);
	t[now].sum=(t[now*2].sum+t[now*2+1].sum)%p;
	return ;
}
ll query(ll now,ll L,ll R,ll l,ll r){
	if(r<L||l>R)  return 0;
	if(L<=l&&R>=r)  return t[now].sum;
	pushdown(now,l,r);
	ll mid=l+(r-l)/2;
	ll res=0;
	if(mid>=L)  res=(res+query(now*2,L,R,l,mid))%p; 
	if(mid+1<=R)  res=(res+query(now*2+1,L,R,mid+1,r))%p;
	return res;
}
int main(){
	cin>>n>>m>>p;
	for(ll i=1;i<=n;i++)  cin>>a[i];
	build(1,1,n);
	for(ll i=1;i<=m;i++){
		ll op,x,y,k;
		cin>>op;
		if(op==1){
			cin>>x>>y>>k;
			modify1(1,x,y,1,n,k);
		}
		else if(op==2){
			cin>>x>>y>>k;
			modify2(1,x,y,1,n,k);
		}
		else if(op==3){
			cin>>x>>y;
			cout<<query(1,x,y,1,n)<<endl;
		}
	}
	return 0;
}

并查集

例题1 T312436 超市。

根据样例数据，推断：按照过期天数从小到大排列，枚举每一天，将当天价值最大的货物卖出。样例两组都可符合猜测。

但这是错的

1. 可能存在价值更大，但过期时间较晚的货物。
2. 同一天过期的同等价值商品，只要天数允许，都可以选，而不是只限 \(1\) 个

一个合理的贪心：每个商品尽量在它过期的前一天卖出，它能为其他商品让出的时间就越多，即更多的商品可以在它之前卖出。

题目要求每天只能卖出 \(1\) 个商品。那么为了价值最大，一定每天都会卖出商品。即 \(n\) 天一共卖出 \(n\) 个商品（如果有的物品 \(x\) 过期很久，但前一次卖出商品到 \(x\) 过期之间差很多天，也没有其他商品可以选，那就卖掉 \(x\) ，中间可以不空着，即连续的出售。所以，需要将天数和商品个数结合起来。

具体实现，需要用一个数据结构维护商品，按照过期时间来从小到大依次枚举每个商品。

按照过期时间排序，存放的是每个商品的利润。统计数据结构中的所有商品的利润，即得到答案。依次扫描每件商品，分以下 \(2\) 种情况：

1. 如果当前商品的过期天数 \(>\) 当前数据结构中的商品个数，那么直接加入数据结构。
2. 如果当前商品过期天数 \(=\) 当前数据结构中的商品个数。要查出其中最小的哪个商品，将其替换。

按照上述方式维护一个数据结构，最后统计数据结构内所有商品利润即可。

时间复杂度 \(\Theta(n\log n)\)

还有一个方式，用一个数据结构维护天数，按照利润来枚举每个商品。

用并查集维护天数，按照利润来枚举每个商品。

按照利润从高到低排序商品，查询每件商品最晚卖出的时间是哪天。

如果一件商品，在 \(m\) 天后过期，就在数组中查询，第 \(m\) 个元素是否为空，如果为空，就把这个商品的利润计入答案，如果不为空（意味着已经有利润更大的商品选择了这一天）当前这件商品只能往前选择，那么在第 \(m\) 个元素中应该存入前一个可用元素位置（父节点 \(fa[m]\)），将答案累加。多个商品要连续使用上述的算法，快速的查询方式。

使用带路径压缩的并查集，时间复杂度 \(\Theta(n)\)

AC代码：

#include<bits/stdc++.h>
using namespace std;
struct good{
	int p,d;
};
int n;
good g[10009];
bool vst[10009];
bool cmp(const good&a,const good&b){
	return a.p>b.p||a.p==b.p&&a.d<b.d;
}
int main(){
	while(cin>>n){
		int ans=0;
		memset(vst,0,sizeof(vst));
		for(int i=1;i<=n;i++)  cin>>g[i].p>>g[i].d;
		sort(g+1,g+1+n,cmp);
		for(int i=1;i<=n;i++){
			int j=g[i].d;
			for(;j>=1;j--){
				if(!vst[j]){
					vst[j]=1;
					ans+=g[i].p;
					break;
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

例题2 T312427 程序自动分析。

由于等式具有传递性（如 \(x_1=x_2,x_2=x_3,x_3=x_4\)，则 \(x_1=x_4\)），则可以从所有条件中找出一系列相等的集合，即把所有具有等于关系的变量并入同一个集合。显然使用带路径压缩的并查集。

可以先将所有具有等于关系的变量并入同一个集合，然后依次扫描每一条不等关系，如果具有不等关系的 \(2\) 个变量在同一个集合内，则不能满足。

注意到变量 \(x_i,x_j\) 的范围为 \(1\leq x_i,x_j \leq 10^9\)，则还需要离散化。

除并查集以外，本题也可以使用dfs求连通块。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct P{
	int i,j;
	bool e;
}p[N*4];
int fa[N*4],a[N*4],m;
int get(int x){
	if(x==fa[x])  return x;
	return fa[x]=get(fa[x]);
}
int find(int x){
	return lower_bound(a+1,a+m+1,x)-a;
}
void process(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>p[i].i>>p[i].j>>p[i].e;
		a[2*i-1]=p[i].i;
		a[i*2]=p[i].j;
	}
	sort(a+1,a+2*n+1);
	m=unique(a+1,a+2*n+1)-(a+1);
	for(int i=1;i<=m;i++)  fa[i]=i;
	for(int i=1;i<=n;i++){
		if(p[i].e)  fa[get(find(p[i].i))]=get(find(p[i].j));
	}
	for(int i=1;i<=n;i++){
		if(!p[i].e&&get(find(p[i].i))==get(find(p[i].j))){
			cout<<"NO"<<endl;
			return ;
		}
	}
	cout<<"YES"<<endl;
}
int main(){
	int t;
	cin>>t;
	while(t--)  process();
}

例题3 T312435 Parity Game。

\(S[l \sim r]\) 中有偶数个 \(1\)，等价于 \(sum[l-1]\) 和 \(sum[r]\) 奇偶性相同

\(S[l \sim r]\) 中有奇数个 \(1\)，等价于 \(sum[l-1]\) 和 \(sum[r]\) 奇偶性相反

不用去求前缀和，只需要判断奇偶性关系是否出现矛盾，因此可以使用并查集维护。

边权 \(d[x]=0\)，表示 \(x\) 与 \(fa[x]\) 的奇偶性相同，反之为 \(1\) 则不同

在路径压缩时，对 \(x\) 到树根路径上的所有边权进行异或运算，即可得到 \(x\) 与 \(root\) 之间的奇偶性关系。

先检查 \(x\) 和 \(y\) 是否在同一集合内（奇偶关系是否已知），\(get(x)\)，\(get(y)\) 都执行后，如果要求 \(x\) 和 \(y\) 的奇偶性关系，那么求 \(d[x] \space xor \space d[y]\)，记为 \(ans\)。如果 \(ans\) 与给定条件不符合，那么即为矛盾，反之进行下一步合并 \(x\) 和 \(y\) 所在的集合。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int n,m,in[100009],res[100009];
double ans[100009];
vector<int> to[100009];
vector<ll> dis[100009];
queue<int> q;
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		to[v].push_back(u);
		dis[v].push_back(w);
		in[u]++,res[u]++;
	}
	for(int i=1;i<=n;i++){
		if(!in[i])  q.push(i);
	}
	while(!q.empty()){
		int fnt=q.front();
		q.pop();
		for(int i=0;i<to[fnt].size();i++){
			int y=to[fnt][i];
			ans[y]+=(ans[fnt]+dis[fnt][i])*1.0/in[y];
			res[y]--;
			if(res[y]==0)  q.push(y);
		}
	}
	cout<<fixed<<setprecision(2)<<ans[1]<<endl;
	return 0;
}

例题4 T312448 天神和恶魔

\(p_1+p_2\) 两个集合，同类集合 \([1,p_1+p_2]\)，异类集合 \([p_1+p_2+1,2(p_1+p_2)]\)

1. 对于 \(a \space b \space yes\)，合并 \((a,b)\) 和 \((a+p_1+p_2,b+p_1+p_2)\)
2. 对于 \(a \space b \space no\)，合并 \((a,b+p_1+p_2)\) 和 \((a+p_1+p_2,b)\)

对于每个人，要么是天神要么是恶魔，那么对于每个人：

这个人 \(i\) 所在的集合全是天神，与 \(i+p_1+p_2\) 处于一个集合的都是恶魔

如果是恶魔，则反之。

\(fa_i\) 是天神还是恶魔，取值。

对于如果有多个集合，需要凑出恰好且仅有 \(1\) 种方式，满足给定人数

\(dp[i][j]\) 表示，满足前 \(i\) 个集合可凑出 \(j\) 个天神的方法数

对于前 \(i\) 个集合可凑出 \(j\) 个天神，那么转移：

dp[i][j]+=dp[i-1][j-集合的代表元是天神时，天神的人数]
dp[i][j]+=dp[i-1][j-集合的代表元是恶魔时，天神的人数]

只有当 \(i==1\) 时可满足题目要求

堆

例题1 T312437 序列

首先考虑最简单的情况：只有 \(2\) 个长度为 \(n\) 的序列。可以想到使用归并排序。从 \(2\) 个已经排好的序列中取数，不断地放到新的序列里。

例如两个有序数组 \(a\) 和 \(b\) 放进序列 \(c\) 中。最小的两个元素之和一定是 \(a_1+b_1\)，第二小的可能是 \(a_1+b_2\) 或 \(a_2+b_1\)。而第三小的是没被选中的第二小和 \(a_2+b_2\) 的较小值，以此类推。

可以找到规律，当第 \(k\) 小的数被确定为 \(a_i+b_j\)，候选集合内应加入 \(a_{i+1}+b_i\) 和 \(a_i+b_{1+1}\)。

有一个小细节，由于 \(a_1+b_2\) 和 \(a_2+b_1\) 都能产生 \(a_2+b_2\)，因此要确保备选方案的唯一性。

可以这么实现：如果本次 \(j\) 往后移动，则 \(j\) 就不能移动，只能移动 \(i\)。本次如果 \(i\) 移动则下次仍旧可以 \(i+1\) 或 \(j+1\)。

由于求最小值，则可以考虑使用小顶堆来实现，每个节点存储一个三元组 \((i,j,last)\)，\(i,j\) 为指针，而 \(last\) 为一个bool变量，用于记录上一次哪个指针移动。如果是 \(i\) 则为 \(1\)，反之则为 \(0\)

最初堆里只有 \((1,1,1)\)，每次取出堆顶，将其pop。接着先加入 \((i,j+1,false)\)，然后如果 \(last==true\)，再加入 \((i+1,j,true)\)

以上操作执行 \(n\) 次，则取出了 \(n\) 个堆顶节点，将 \(n\) 个答案输出即可

扩展到 \(m\) 个序列的做法，可以先取出前 \(2\) 个序列的最小值，再和第 \(3,4,...,m\) 个序列进行合并

时间复杂度为 \(\Theta(nm\log n)\)

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
struct node{
	int i,j,sum;
	bool last;
	bool operator<(const node&x)const{
		return sum>x.sum;
	}
};
ll t,n,m,a[1009][2009],ans[2009];
int main(){
	cin>>t;
	while(t--){
		cin>>m>>n;
		memset(ans,0,sizeof(ans));
		for(int i=1;i<=m;i++){
			for(int j=1;j<=n;j++)  cin>>a[i][j];
			sort(a[i]+1,a[i]+1+n);
		}
		for(int i=1;i<=n;i++)  ans[i]=a[1][i];
		for(int i=2;i<=m;i++){
			ll c[2009]={0};
			priority_queue<node> q;
			q.push((node){1,1,ans[1]+a[i][1],1});
			for(int j=1;j<=n;j++){
				node fnt=q.top();
				q.pop();
				c[j]=fnt.sum;
				q.push((node){fnt.i+1,fnt.j,ans[fnt.i+1]+a[i][fnt.j],0});
				if(fnt.last)  q.push((node){fnt.i,fnt.j+1,ans[fnt.i]+a[i][fnt.j+1],1});
			}
			for(int j=1;j<=n;j++)  ans[j]=c[j];
		}
		for(int i=1;i<=n;i++)  cout<<ans[i]<<" ";
		cout<<endl;
	}
	return 0;
}

例题2 T312424 数据备份。

显而易见的是，每个配对的办公楼一定是相邻的。

因此我们可以求出每个办公楼之间的距离 \(d_1,d_2,d_3,...,d_{n-1}\)

如果我们选择了 \(d_i\)，就不能选择 \(d_{i-1}\) 和 \(d_{i+1}\)

我们不妨先选择 \(d_i\) ，并删除 \(d_{i-1},d_i,d_{i+1}\)

接着加入 \(d_{i-1}+d_{i+1}-d_i\)

接着继续求 \(d\) 序列中最小的数，直到选满 \(k\) 个数

因此，我们使用优先队列维护 \(d\) 数组的大小，并用链表维护 \(d\) 数组的先后顺序。

标签：frac,gcd,int,sum,基础,times,算法,now
From： https://www.cnblogs.com/11jiang08/p/17300519.html