- 总结一些自己容易遗忘但挺重要的算法。
手撕经典算法
快速排序
核心代码：
void qsort(int ll, int rr)
{
if(ll>=rr) return;
int x=a[ll+rr>>1], l=ll-1, r=rr+1;
while(l<r)
{
do l++; while(a[l]<x);
do r--; while(a[r]>x);
if(l<r) swap(a[l], a[r]);
}
qsort(ll, r);
qsort(r+1, rr);
}
理解点1：如果，l++的时候加到 r 的位置。由上一轮知，r 的位置a[r]一定>=x，那么l++最多到 l==r 的时候停止。此时 a[r-1] < x，所以 r循环后为r-1。此时l=r+1。不满足if(l<r)的条件。同理r–的时候减到l的位置，也不会满足交换条件。
理解点2：若x是中间位置，这些情况不太可能发生，因为肯定会在 x的位置停下来。
如下代码（while比do while简洁）看似等价，实则会陷入死循环。如在某个点 x=5, l 当前的位置值是5, r 当前的位置也是5。但是 r>l。此时会不断进行 while(l<r) 这个循环。（相同的5交换了位置还是不变）
void qsort(int ll, int rr)
{
if(ll>=rr) return;
int x=a[ll+rr>>1], l=ll, r=rr;
while(l<r)
{
while(l<r && a[l]<x) l++;
while(l<r && a[r]>x) r--;
if(l<r) swap(a[l], a[r]);
}
qsort(ll, r);
qsort(r+1, rr);
}上面的代码改成 while(l<r && a[r]>=x) r–; 也不行，>=x 会让一侧略过=x的点，造成失败。
案例
x=133
第一轮：128 90 83 67 98 8 67 6 116 164 11 60 238 133 153 241 248 232 175 233 196 260 181 160 133 160 216 291 a[l]=116 a[r]=241
第二轮：128 90 83 67 98 8 67 6 116 60 11 164 238 133 153 241 248 232 175 233 196 260 181 160 133 160 216 291 a[l]=60 a[r]=164
上面第一个案例中，运行完之后，a[l]=116的位置，a[r]=241的位置，r 往前走，因为 是 >= x，则会跳过133的位置，最终走到 60 的位置，l走到164的位置，然后交换得到第二轮的结果，显然：不满足要求（238>133）。
总体分析
1.划分情况：以r为划分时，x不能选q[rr]。若以l为划分,则x不能选q[ll]
假设 x = q[rr]
关键句子quick_sort(q, ll, r), quick_sort(q, r + 1, rr);
由于 r 的最小值是 ll, 所以 q[r+1..rr] 不会造成无限划分
但q[ll..r](即quick_sort(q, ll, r))却可能造成无限划分，因为 r 可能取到 rr。
举例：若x选为q[rr]，数组中q[ll..rr-1] < x, 那么这一轮循环结束时 l = rr, r= rr，显然会造成无限划分。
2.while(a[l]<x)的循环不能用<=，a[r] > x 也不能用>=。举例：如果 a 数组全是相同的数，则会越界造成各种错误。
Trie树
这个树比较奇特。即便是复习，也不太清楚p是怎么走的了。p不是序列长度，而是子节点。
模板题：Trie字符串统计
最大连续子序和
模板题：最大子序和
题解：贪心/动态规划
最长上升子序列篇
方法1：dp，复杂度 $O(n^2)$ 且只能得到长度。最长上升子序列 I
方法2：维护后缀最小的上升序列。每次二分插入。（可输出最长序列）最长上升子序列 II
最长公共子序列
dp过程会有集合重叠，但是不影响结果，因为状态函数是取MAX。
$f[i][j]=max(f[i-1][j], f[i][j-1])$ 这里有重叠，两者都可以是 $s[i]$ 和 $s[j]$ 不取，从而两者都可以退化成 $f[i-1][j-1]$
模板题：最长公共子序列
最长公共上升子序列
- $O(n^3)优化到O(n^2)$
模板题：最长公共上升子序列
状态表示：$f[i][j]$：考虑a的前 $i$ 个字母和b的前 $j-1$ 个字母且以 $j$ 结尾的最长公共上升子序列
原始代码
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
f[i][j]=f[i-1][j]; //不选
if(a[i] == b[j])
{
int maxv=1; //长度为1
for(int k=1;k<j;k++) //长度至少为2
{
if(a[i]==b[k]) maxv=max(maxv, f[i-1][k] + 1);
}
f[i][j]=max(f[i][j], maxv);
}
}
}优化后代码
for(int i=1;i<=n;i++)
{
int maxv=1; //长度为1 maxv维护a[i] > b[k] 的下的f[i][k]的最大值就行了
for(int j=1;j<=n;j++)
{
f[i][j]=f[i-1][j]; //不选
if(a[i] == b[j])
{
f[i][j]=max(f[i][j], maxv); //找一个前面的最大值选
}
if(a[i] > b[j]) maxv=max(maxv, f[i-1][j] + 1);
}
}最大上升子序列
- 从最长上升子序列换一个集合属性就行了。长度max改为加和max
模板题：最大上升子序列
最长回文子串
区间DP，每次枚举区间长度。注意奇数和偶数要分开处理一下。
模板题：最长回文子串 – 力扣
最长连续不重复子序列
- 哈希表+双指针
模板题：最长连续不重复子序列
01背包
模板题：01背包
完全背包
- 每个物品可以取无限次
- 原始代码枚举次数，但是可优化。复杂度任然是 $O(nm)$
模板题：完全背包问题
多重背包
- 物品最多只能取特定次数
简单版本：多重背包问题 I
二进制优化版本：多重背包问题 II
分组背包
- 同一组的物品最多只能选1个，复杂度 $O(nms)$
模板题：分组背包问题
KMP
模板题：KMP字符串
核心代码
//求next数组
for(int i=2, j=0;i<=n;i++)
{
while(j && p[i]!=p[j+1]) j=ne[j];
if(p[i]==p[j+1]) j++;
ne[i]=j;
}
//匹配过程
for(int i=1, j=0; i<=m; i++)
{
while(j && s[i]!=p[j+1]) j=ne[j];
if(s[i]==p[j+1]) j++;
if(j==n)
{
cout<<i-n<<' ';
j=ne[j];
}
}单调栈
- 可以求每个数前面比它小的数的最近的数
模板题：单调栈
单调队列
- 单调队列相对用处大一些
- 可以求滑动窗口最大最小值
模板题：滑动窗口，滑动窗口最大值 – 力扣
acwing简单题，到了leetcode变成困难题，2333😀
核心代码
int hh=0,tt=-1;
for(int i=1;i<=n;i++) //单调递增队列 维度最小值
{
while(hh<=tt && a[q[tt]] >= a[i]) tt--;
q[++tt]=i;
if(i-q[hh]+1 > m) hh++; //注意这里是q[hh]，不是hh
if(i>=m) printf("%d ", a[q[hh]]);
}
puts("");
hh=0,tt=-1;
for(int i=1;i<=n;i++) //单调递减队列 维护最大值
{
while(hh<=tt && a[q[tt]] <= a[i]) tt--;
q[++tt]=i;
if(i-q[hh]+1 > m) hh++;
if(i>=m) printf("%d ", a[q[hh]]);
}二分图最大匹配
- 匈牙利算法，复杂度最高 $O(mn)$，实际很难达到。
模板题：二分图的最大匹配
核心代码
int n1,n2,m;
int match[N];
bool st[N]; //让左边的男生都继续去考虑右边连线的所有女生，
//如果不重置st，那么这个男生将尝试都不会尝试。
//只有st=false才会继续尝试，让自己心系的女生尝试绿了她现在的男生。
//温馨提示：这个匹配说法来自yxc！
bool find(int u)
{
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(!st[j])
{
st[j]=true;
if(!match[j] || find(match[j]))
{
match[j]=u;
return true;
}
}
}
return false;
}区间问题
区间选点：https://www.acwing.com/problem/content/907/
最大不相交区间数量：https://www.acwing.com/problem/content/910/
区间分组：https://www.acwing.com/problem/content/908/
区间覆盖：https://www.acwing.com/problem/content/909/
数论（latex修好再写）
筛质数
- 埃拉托色尼筛法 复杂度 $O(nlog(log(n)))$
- 欧拉筛，每个合数只会被最小质因子筛去 $O(n)$
欧拉筛核心代码：
int euler(int n)//欧拉筛法
{
int cnt=0;
for(int i=2;i<=n;i++)
{
if(!st[i]) primes[cnt++]=i;
for(int j=0;primes[j]<=n/i;j++) //primes[j] * i <= n 好理解些，但是防止溢出
{
st[primes[j]*i]=true;
if(i%primes[j]==0) break;
}
}
return cnt;
}快速幂
- 本质上跟多重背包的二进制优化相似，都是二进制优化。还有树状数组也是这类思想
模板题：快速幂
求组合数
- 数据范围 $2000$ 左右，直接递推，复杂度 $O(n^2)$
- 数据范围 $1e6$ 左右，前缀和递推，模数为质数用费马小定理求逆元。最后用数学上的组合数方法直接求
- 数据范围 $1e18$，无法直接算，但是在取模的条件下有卢卡斯定理。$$C^{n}_{m}=C^{n\%p}_{m\%p} \cdot C^{\lfloor \frac{n}{p} \rfloor}_{\lfloor \frac{m}{p} \rfloor} \% p$$
模板题：
博弈论
- 范围很广，不限于记忆化搜索+思维
暂时不做描述
约数个数
设一个数 $N = (p_1^{x_1})(p_2^{x_2})(p_3^{x_3})…(p_k^{x_k})$，其中 $p_i$ 为质数。
则 $N$ 的
- 约数个数为：$(x_1+1)(x_2+1)(x_3+1)…(x_k+1)$，
- 约数之和为：$(p_1^0+p_1^1+…+p_1^{x_1})∗…∗(p_k^0+p_k^1+…+p_k^{c_k})$
模板题：约数个数
unordered_map<int,int>primes;
while(n--)
{
int x; cin>>x;
for(int i=2;i<=x/i;i++)//分解质因子
{
while(x%i==0)
{
primes[i]++;
x/=i;
}
}
if(x>1) primes[x]++;
}
long long res=1;
for(auto prime:primes) res=res*(prime.second+1)%mod;
约数之和
模板题：约数之和
欧拉函数
模板题：欧拉函数
定义：对于正整数 $n$，欧拉函数是小于或等于 $n$ 的正整数中与 $n$ 互质的数的数目，记作 $varphi n， \varphi(1)=1$
欧拉函数 $\phi(n)$ 是积性函数，即当 $m$ 与 $n$ 互质时：$\varphi(mn) = \varphi(m) \cdot \varphi(n)$
根据唯一分解定理知 $n = p_1^{a_1} p_2^{a_2} \cdots p_x^{a_x}$
因此：$\varphi(n) = \varphi(p_1^{a_1}) \cdot \varphi(p_2^{a_2}) \cdots \varphi(p_x^{a_x})$
素数幂的欧拉函数
对于素数幂（素数的正整数次幂） $p_k^{a_k}$：
$$
\varphi(p_k^{a_k}) = p_k^{a_k} – p_k^{a_k-1} = p_k^{a_k}(1 – \frac{1}{p_k})
$$
一般公式
最终欧拉函数公式为：
$$
\varphi(n) = n \cdot \prod_{i=1}^{x} {(1 – \frac{1}{p_i})}
$$
筛法求欧拉函数 筛法求欧拉函数
- 事实上欧拉筛可以求很多东西，不只是欧拉函数
暂时略…
概率与数学期望
- 本质上是概率dp
模板题：绿豆蛙的归宿
博弈论
公平组合游戏ICG
若一个游戏满足：
- 由两名玩家交替行动；
- 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；
- 不能行动的玩家判负；
则称该游戏为一个公平组合游戏。
举例说明
- NIM博弈属于公平组合游戏。
- 围棋等城建棋类游戏不属于公平组合游戏，因为围棋交战双方分别只能落黑子和白子（行动受限），且胜负判定复杂。
先手必胜状态（先手拿完以后让剩下的状态是先手必败状态，那就就是必胜状态）
先手必败状态（不管怎么操作，都是输）
证明过程：
若$a_1, a_2, … ,a_n$ 都为 $0$，则输掉比赛，且其异或和也为0。
必胜态：异或和不为0，然后在第 $i$ 堆取 $a_i-(a_i \oplus x)$个石子，转为必败态留给对手
必败态：异或和为0，随机抽取一个必然转为必胜态留给对手
证明1：必胜态必然可以转为必变态。设目前的异或和为 $x$，则 $x>0$ 且必然有x的最高位为 $1$，设为 $i$。那么在 $a_{1\sim n}$ 中必然存在某一个堆，其第 $i$ 位为 $1$。则 $a_i \oplus x<a_i$，然后在这一堆里取走 $a_i-(a_i \oplus x)$ 个石子，这一堆就变成 $a_i \oplus x$。现在的异或和更新为 $a_1\oplus a_2 \oplus … \oplus (a_i \oplus x) \oplus …\oplus a_n=0$ （相当于原先的异或和 $x$ 多异或了一个 $x$，变为 $0$）。
证明2：必败态随机取一个必然变成必败态。这个显然易见。从异或和为 $0$ 的石子堆中随机取数，必然导致现在的异或和为 $0$ 异或上取出的数。则必然不为 $0$。此时转为必胜态。
模板题：Nim游戏
若$a_1\oplus a_2 \oplus … \oplus a_n=0$，为先手必败状态，反之为先手必胜
游戏代码（和别人对战）：
#include <bits/stdc++.h>
#define x first
#define y second
#define all(x) x.begin(),x.end()
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<LL,int> PLI;
const int INF=0x3f3f3f3f,MOD=998244353,P=131,N=15, M=110;
int e[M],h[N],ne[M],idx;
void add(int a, int b)
{
e[idx]=b, ne[idx]=h[a], h[a]=idx++;
}
int a[N], n;
bool check()
{
rep(i,1,n) if(a[i]) return true;
return false;
}
void get()
{
int x=0;
rep(i,1,n) x ^= a[i];
if(x==0)
{
cout<<"当前处于必败态"<<endl;
rep(i,1,n)
{
if(a[i])
{
a[i]--;
printf("解答：第%d堆拿出1个石子\n", i);
return;
}
}
}
else cout<<"当前处于必胜态"<<endl;
for(int i=31;i>=0;i--)
{
if(x>>i&1)
{
rep(j,1,n) if(a[j] >> i & 1)
{
printf("解答：第%d堆拿出%d个石子\n", j, a[j] - (a[j] ^ x));
a[j] ^= x;
break;
}
break;
}
}
}
void adver()
{
cout<<"请输入对方操作的《堆编号》和《取走的数量》：";
int kk, cnt; cin>>kk>>cnt;
a[kk]-=cnt;
}
int main()
{
cout<<"请输入石子《堆数》：";
cin>>n;
cout<<"请输入《每一堆石子的数量》，以空格分开：";
rep(i,1,n) cin>>a[i];
cout<<"我是先手，输入《1》，否则输入《0》"<<endl;
int t; cin>>t;
if(!t) adver();
while(check())
{
cout<<"-------------------------------------------"<<endl;
cout<<"现在的石子数量信息："<<endl;
rep(i,1,n) cout<<a[i]<<' '; cout<<endl;
get();
if(!check())
{
cout<<"拿完此次，对手输了"<<endl;
break;
}
adver();
if(!check())
{
cout<<"对手拿完此次，我输了"<<endl;
}
}
return 0;
}