算法模板
算法可视化：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
万能头文件 #include <bits/stdc++.h>
笔记
1. 数据读入
scanf比cin更快，尽量用scanf读入数据（百万级以上数据）
scanf("%d", &n);
如果用cin读入，使用以下代码加速
ios::sync_with_stdio(false);
cin.tie(0);
2. C语言中scanf函数%s和%c以及回车对缓冲区的作用
scanf遇到空格就停止,无法继续读取
%s为输入字符串，在输入时以非空白字符开始，以第一个非空白字符结束。字符串会自动以'\0'为最后一个字符。
格式为：
char s[2]; // 至少两个字符，有一个用来存放\0
scanf("%s",s);//注意s为数组变量不带取值符
%c为输入单个字符，包括空白字符。
格式为：
scanf("%c",&c);//需要取值符
空白字符：空格，回车，制表符等。
因此要注意，%c会将这三种空白字符吸入；而%s则不会吸入这些空白字符，而会跳过他们自动吸入有效字符串。
3. 求质数
// 求大于 x 的第一个质数
int prime(int x){
for (int i = x; ; i++) {
bool flag = true;
// 关键 j * j <= i
for (int j = 2; j * j <= i; j++) {
// 能整除就不是质数
if (i % j == 0) {
flag = false;
break;
}
}
if (flag) return i;
}
}
4. 字符串转化为数字
#include <string>
string str = "12345";
int index = atoi(str.substr(1).c_str());
// int atoi(const char* str) 将 char 转换为整数
// int stoi(const string& str, ...) 将 string 转换为整数
在示例中，str 变量的值为 "12345"。
str.substr(1)函数返回字符串str从第二个字符开始的子字符串，即 "2345"。c_str()函数将字符串 "2345" 转换为一个以 null 结尾的char数组。atoi()函数将char数组 "2345" 转换为一个int类型的值，即 2345。
最终，index 变量的值为 2345。
5. 字符串拼接
当碰到这种每个数字间都带空格的输入时
2 3 4 1 5 x 7 6 8
想要将每个数字不带空格地存储在一个字符串中，可以用字符串拼接的形式：
string s, c;
for (int i = 0; i < 8; i++) {
cin >> c;
s += c; // 每次拼接都会忽略中间的 \0，只会在拼接的字符串最后加上 \0
}
6. 函数内更改外部变量
需要注意，在以下代码中：
struct Node {
int index;
int w;
int pw; // 它和所有后代权重之和
int dw;
vector<int> son;
}node[N];
int cal(int ui) {
if (st[ui]) return 0;
Node u = node[ui]; // 这是错的，实际上只改了u，未改变node[ui]
// Node& u = node[ui]; // 改为这行引用即可更改node[ui]！！！
u.pw = u.w;
// ...
}
常用代码模板1——基础算法
1. 排序
(1) 快速排序
模板题 AcWing 785. 快速排序
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
注意：
x = q[l + r >> 1] 时，两个递归取 j 和 j+1；x = q[l + r + 1 >> 1] 时，两个递归取 i - 1 和 i
x 最好不要取两端，特殊情况会超时！
(2) 归并排序
模板题 AcWing 787. 归并排序
void merge_sort(int q[], int l, int r)
{
if (l >= r) return;
int mid = l + r >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
else tmp[k ++ ] = q[j ++ ];
while (i <= mid) tmp[k ++ ] = q[i ++ ];
while (j <= r) tmp[k ++ ] = q[j ++ ];
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
...
// 额外全局变量
TYPE tmp[N];
// 初次调用
merge_sort(q, 0, n-1);
2. 二分查找
(1) 整数二分查找
模板题 AcWing 789. 数的范围
bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
解释：
如果更新方式为 l = mid (r = mid - 1)，则 mid 取 (l + r + 1) / 2（模板2）。因为如果 mid = (l + r) / 2，且 l 与 r 只相差 1 ，那么更新之后，l 还是 l ，值没有变，会导致下次循环的区间仍是[l, r]，会造成死循环
(2) 浮点数二分查找
bool check(double x) {/* ... */} // 检查x是否满足某种性质
double bsearch_3(double l, double r)
{
const double eps = 1e-6; // eps 表示精度，取决于题目对精度的要求
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
3. 高精度算法
(1) 高精度加法
// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
if (A.size() < B.size()) return add(B, A);
vector<int> C;
int t = 0;
for (int i = 0; i < A.size(); i ++ )
{
t += A[i];
if (i < B.size()) t += B[i];
C.push_back(t % 10);
t /= 10;
}
if (t) C.push_back(t);
return C;
}
(2) 高精度减法
// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
vector<int> C;
for (int i = 0, t = 0; i < A.size(); i ++ )
{
t = A[i] - t;
if (i < B.size()) t -= B[i];
C.push_back((t + 10) % 10);
if (t < 0) t = 1;
else t = 0;
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
(3) 高精度乘低精度
// C = A * b, A >= 0, b >= 0
vector<int> mul(vector<int> &A, int b)
{
vector<int> C;
int t = 0;
for (int i = 0; i < A.size() || t; i ++ )
{
if (i < A.size()) t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
(4) 高精度除以低精度
// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{
vector<int> C;
r = 0;
for (int i = A.size() - 1; i >= 0; i -- )
{
r = r * 10 + A[i];
C.push_back(r / b);
r %= b;
}
reverse(C.begin(), C.end());
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
4. 前缀和与差分
设 b[n] 是 a[n] 的前缀和，则 a[n] 是 b[n] 的差分。
(1) 一维前缀和
模板题 AcWing 795. 前缀和
b[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = b[r] - b[l - 1]
(2) 二维前缀和
b[i, j] = 第i行j列格子左上部分所有元素的和
// 以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
b[x2, y2] - b[x1 - 1, y2] - b[x2, y1 - 1] + b[x1 - 1, y1 - 1]
(3) 一维差分
模板题 AcWing 797. 差分
// 给b的区间[l, r]中的每个数加上c
void insert(int l, int r, int c)
{
a[l] += c;
a[r + 1] -= c;
}
(4) 二维差分
模板题 AcWing 798. 差分矩阵
// 给b中以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
void insert(int x1, int y1, int x2, int y2, int c)
{
a[x1][y1] += c;
a[x2 + 1][y1] -= c;
a[x1][y2 + 1] -= c;
a[x2 + 1][y2 + 1] += c;
}
5. 位运算
求n的第k位数字: n >> k & 1
返回n的最后一位1：lowbit(n) = n & -n
6. 双指针算法
模板题 AcWing 799. 最长连续不重复子序列，AcWing 800. 数组元素的目标和
for (int i = 0, j = 0; i < n; i ++ )
{
while (j < i && check(i, j)) j ++ ;
// 具体问题的逻辑
}
常见问题分类：
(1) 对于一个序列，用两个指针维护一段区间
(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作
7. 离散化
模板题 AcWing 802. 区间和
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素
// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
int l = 0, r = alls.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1; // 映射到1, 2, ...n
}
8. 区间合并
模板题 AcWing 803. 区间合并
// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
vector<PII> res;
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;
for (auto seg : segs)
if (ed < seg.first)
{
if (st != -2e9) res.push_back({st, ed});
st = seg.first, ed = seg.second;
}
else ed = max(ed, seg.second);
if (st != -2e9) res.push_back({st, ed});
segs = res;
// segs = res 改写成 swap(res, segs) 应该效率更高一些，容器交换的时间复杂度是 O(1)，不用再拷贝一次了。
}
链接：https://www.acwing.com/blog/content/277/
来源：AcWing
常用代码模板2——数据结构
1. 链表
(1) 单链表
模板题 AcWing 826. 单链表
// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;
// 初始化
void init()
{
head = -1;
idx = 0;
}
// 在链表头插入一个数a
void insert(int a)
{
e[idx] = a, ne[idx] = head, head = idx ++ ;
}
// 将头结点删除，需要保证头结点存在
void remove()
{
head = ne[head];
}
(2) 双链表
模板题 AcWing 827. 双链表
// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;
// 初始化
void init()
{
//0是左端点，1是右端点
r[0] = 1, l[1] = 0;
idx = 2;
}
// 在节点a的右边插入一个数x
void insert(int a, int x)
{
e[idx] = x;
l[idx] = a, r[idx] = r[a];
l[r[a]] = idx, r[a] = idx ++ ;
}
// 删除节点a
void remove(int a)
{
l[r[a]] = l[a];
r[l[a]] = r[a];
}
2. 栈与队列
(1) 栈
模板题 AcWing 828. 模拟栈
// tt表示栈顶
int stk[N], tt = 0;
// 向栈顶插入一个数
stk[ ++ tt] = x;
// 从栈顶弹出一个数
tt -- ;
// 栈顶的值
stk[tt];
// 判断栈是否为空，如果 tt > 0，则表示不为空
if (tt > 0)
{
}
(2) 队列
模板题 AcWing 829. 模拟队列
- 普通队列：
// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;
// 向队尾插入一个数
q[ ++ tt] = x;
// 从队头弹出一个数
hh ++ ;
// 队头的值
q[hh];
// 判断队列是否为空，如果 hh <= tt，则表示不为空
if (hh <= tt)
{
}
- 循环队列
// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;
// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;
// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;
// 队头的值
q[hh];
// 判断队列是否为空，如果hh != tt，则表示不为空
if (hh != tt)
{
}
(3) 单调栈
模板题 AcWing 830. 单调栈
常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
while (tt && check(stk[tt], i)) tt -- ;
stk[ ++ tt] = i;
}
(4) 单调队列
模板题 AcWing 154. 滑动窗口
常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
while (hh <= tt && check_out(q[hh])) hh ++ ; // 判断队头是否滑出窗口
while (hh <= tt && check(q[tt], i)) tt -- ;
q[ ++ tt] = i;
}
3. KMP
// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
// 求模式串的Next数组
for (int i = 2, j = 0; i <= m; 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 <= n; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == m)
{
j = ne[j];
// 匹配成功后的逻辑
}
}
4. Trie 树
int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量
// 插入一个字符串
void insert(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if (!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
cnt[p] ++ ;
}
// 查询字符串出现的次数
int query(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if (!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}
5. 并查集
模板题 AcWing 836. 合并集合，AcWing 837. 连通块中点的数量
(1) 朴素并查集
int p[N]; //存储每个点的祖宗节点
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;
// 合并a和b所在的两个集合：
p[find(a)] = find(b);
(2) 维护size的并查集
int p[N], size[N];
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
size[i] = 1;
}
// 合并a和b所在的两个集合：
size[find(b)] += size[find(a)];
p[find(a)] = find(b);
(3) 维护到祖宗节点距离的并查集
int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x)
{
int u = find(p[x]);
d[x] += d[p[x]];
p[x] = u;
}
return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
d[i] = 0;
}
// 合并a和b所在的两个集合：
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量
6. 堆
模板题 AcWing 838. 堆排序，AcWing 839. 模拟堆
// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;
// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);
}
void down(int u)
{
int t = u;
if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t)
{
heap_swap(u, t);
down(t);
}
}
void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
heap_swap(u, u / 2);
u >>= 1;
}
}
// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);
7. 哈希表
(1) 一般哈希
a. 拉链法
int h[N], e[N], ne[N], idx;
// 向哈希表中插入一个数
void insert(int x)
{
int k = (x % N + N) % N;
e[idx] = x;
ne[idx] = h[k];
h[k] = idx ++ ;
}
// 在哈希表中查询某个数是否存在
bool find(int x)
{
int k = (x % N + N) % N;
for (int i = h[k]; i != -1; i = ne[i])
if (e[i] == x)
return true;
return false;
}
b. 开放寻址法
int h[N];
// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
int find(int x)
{
int t = (x % N + N) % N;
while (h[t] != null && h[t] != x)
{
t ++ ;
if (t == N) t = 0;
}
return t;
}
(2) 字符串哈希
核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果
typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}
// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}
8. C++ STL简介
(1) vector：变长数组，倍增的思想
size() 返回元素个数
empty() 返回是否为空，为空则true
clear() 清空
front()/back()
push_back()/pop_back()
begin()/end()
[]
支持比较运算，按字典序
(2) pair<T, T>
first, 第一个元素
second, 第二个元素
支持比较运算，以first为第一关键字，以second为第二关键字（字典序）
(3) string：字符串
size()/length() 返回字符串长度
empty()
clear()
substr(起始下标，(子串长度)) 返回子串
c_str() 返回字符串所在字符数组的起始地址
(4) queue / priority_queue：队列 / 优先队列（默认是大根堆）
size()
empty()
push() 插入一个元素
top() 返回priority_queue的首个元素 / front() 返回queue的的首个元素
pop() 弹出堆顶元素
定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;
(5) stack：栈
size()
empty()
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素
(6) deque：双端队列
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]
(7) set, map, multiset, multimap：集合和映射
基于平衡二叉树（红黑树），动态维护有序序列
共有方法：
size()
empty()
clear()
begin()/end()
++, -- 返回前驱和后继，时间复杂度 O(logn)
set/multiset
insert() 插入一个数
find(k) 查找一个数k
count(k) 返回某一个数k的个数
erase()
(1) 输入是一个数x，删除所有x O(k + logn)
(2) 输入一个迭代器，删除这个迭代器
lower_bound()/upper_bound()
lower_bound(x) 返回大于等于x的最小的数的迭代器
upper_bound(x) 返回大于x的最小的数的迭代器
map/multimap
insert() 插入的数是一个pair
erase() 输入的参数是pair或者迭代器
find(k) 在容器中寻找值为k的元素，返回该元素的迭代器。否则，返回 map.end()
[] 注意multimap不支持此操作。 时间复杂度是 O(logn)
lower_bound()/upper_bound()
unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
和上面类似，增删改查的时间复杂度是 O(1)
不支持 lower_bound()/upper_bound()， 迭代器的++，--
(8) bitset：压位
bitset<10000> s; // 定义一个空间为 10000 比特的压位 s
~, &, |, ^
>>, <<
==, !=
[]
count() 返回有多少个1
any() 判断是否至少有一个1
none() 判断是否全为0
set() 把所有位置成1
set(k, v) 将第k位变成v
reset() 把所有位变成0
flip() 等价于~
flip(k) 把第k位取反
链接：https://www.acwing.com/blog/content/404/
来源：AcWing
常用代码模板3——搜索与图论
1. 树与图的存储
树是一种特殊的图，与图的存储方式相同。
对于无向图中的边 ab，存储两条有向边 a->b , b->a。
因此我们可以只考虑有向图的存储。
(1) 邻接矩阵
g[a][b] 存储边 a->b
(2) 邻接表
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;
// 添加一条边a->b
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
// 初始化
idx = 0;
memset(h, -1, sizeof h);
2. 树与图的遍历
时间复杂度 O(n+m)，n 表示点数，m 表示边数
(1) 深度优先遍历 (DFS)
模板题 AcWing 846. 树的重心
int dfs(int u)
{
st[u] = true; // st[u] 表示点u已经被遍历过
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j]) dfs(j);
}
}
例题：八皇后
const int N = 20;
char m[N][N];
bool col[N], dg[N], udg[N];
int n;
void dfs(int x) {
if (x == n + 1) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << m[i][j];
}
cout << endl;
}
cout << endl;
return;
}
for (int y = 1; y <= n; y++) {
if (!col[y] && !dg[x + y] && !udg[y - x + n]) {
col[y] = dg[x + y] = udg[y - x + n] = true;
m[x][y] = 'Q';
dfs(x + 1);
// 回溯
col[y] = dg[x + y] = udg[y - x + n] = false;
m[x][y] = '.';
}
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
m[i][j] = '.';
}
}
dfs(1);
return 0;
}
(2) 宽度优先遍历 (BFS)
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);
while (q.size())
{
int t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = true; // 表示点j已经被遍历过
q.push(j);
}
}
}
例题：八数码
queue<string> q; // 保存当前到达的字符串形态
unordered_map<string, int> d; // 保存到达每个字符串形态时对应的步数
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int bfs(string s) {
q.push(s);
d[s] = 0;
while (q.size()) {
auto t = q.front();
q.pop();
int dis = d[t];
if (t == "12345678x") return dis; // 终点对应的字符串形态
int co = 0, coa;
while (t[co] != 'x') co++;
int x = co / 3, y = co % 3;
for (int i = 0; i < 4; i++) {
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && b >= 0 && a < 3 && b < 3) {
coa = a * 3 + b;
swap(t[co], t[coa]);
if (!d.count(t)) {
q.push(t);
d[t] = dis + 1;
}
swap(t[co], t[coa]);
}
}
}
return -1;
}
int main() {
string s;
for (int i = 0; i < 9; i++) {
string c;
cin >> c;
s += c;
}
cout << bfs(s);
return 0;
}
3. 拓扑排序
时间复杂度 O(n+m)，n 表示点数，m 表示边数
bool topsort()
{
int hh = 0, tt = -1;
// d[i] 存储点i的入度
for (int i = 1; i <= n; i ++ )
if (!d[i])
q[ ++ tt] = i;
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (-- d[j] == 0)
q[ ++ tt] = j;
}
}
// 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
return tt == n - 1;
}
4. 最短路算法
(1) 单源最短路：所有边权都是正数
朴素和堆优化版的区别
连线很多的时候，对应的就是稠密图，显然易见，稠密图的路径太多了，所以就用点来找，也就是抓重点。
点很多，但是连线不是很多的时候，对应的就是稀疏图，稀疏图的路径不多，所以按照连接路径找最短路，这个过程运用优先队列，能确保每一次查找保留到更新到队列里的都是最小的，同时还解决了两个点多条路选择最短路的问题。
Dijkstra 算法步骤
- 初始化各点离源点距离：1 号点距离为 0，其他点距离为 ∞ (0x3f3f3f3f)
- 循环 n 次，每一次将集合 S 之外 (用
st[]标记)，且**距离最短 (可用小根堆)**的点 x 加入到 S 中去，然后将st[x]标记为true - 用点 x 更新 x 的所有邻接点的距离
a. 朴素 Dijkstra 算法（稠密图 m ~ n^2）
图为稠密图时使用，即 n^2 和 m 一个量级。
注意：如果有重边，需要对重边进行处理（选取最短的边作为这两个点的边）。
模板题 AcWing 849. Dijkstra 求最短路 I
时间复杂是 O(n^2+m)，n 表示点数，m 表示边数
int g[N][N]; // 存储每条边
int dist[N]; // 存储1号点到每个点的最短距离
bool st[N]; // 存储每个点的最短路是否已经确定
// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 1; i <= n; i ++ )
{
// 每次遍历从还未确定最短路的点中，寻找距离源点最近的点t
int t = -1;
for (int j = 1; j <= n; j ++ )
// j未确定最短路且j的dist比t更小时，将 t 更新为 j
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
st[t] = true;
// 用t更新其他点的距离
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
b. 堆优化版 Dijkstra（稀疏图 m ~ n）
图为稀疏图时使用，即 n 和 m 一个量级。
由于是邻接表存储，故不需要对重边进行处理。
模板题 AcWing 850. Dijkstra求最短路 II
时间复杂度 O(mlogn)，n 表示点数，m 表示边数
typedef pair<int, int> PII;
int n; // 点的数量
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储所有点到1号点的距离
bool st[N]; // 存储每个点的最短距离是否已确定
// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap; // 创建小根堆
heap.push({0, 1}); // first存储距离，second存储节点编号
while (heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
// 有重边也不要紧，假设1->2有权重为2和3的边，再遍历到点1的时候2号点的距离会更新两次放入堆中
// 虽然这样堆中会有很多冗余的点，
// 但是，在弹出的时候还是会弹出最小值2+x（x为之前确定的最短路径），
// 并标记st为true，所以下一次弹出3+x会continue不会向下执行。
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({dist[j], j});
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
(2) 单源最短路：存在负权边
a. Bellman-Ford 算法（求不超过k条边的最短路）
简介
Bellman - ford 算法是求含负权图的单源最短路径的一种算法，效率较低，代码难度较小。
Dijkstra 算法更关注于遍历顶点，而 Bellman-Ford 算法更注重于遍历边。
假设 1 号点到 n 号点是可达的，每一个点同时向指向的方向出发，更新相邻的点的最短距离，通过循环 n-1 次操作，若图中不存在负环，则 1 号点一定会到达 n 号点，若图中存在负环，则在 n-1 次松弛后一定还会更新。
需要求不超过k条边的最短路时使用，否则一般用 SPFA 算法。
时间复杂度 O(nm)，n 表示点数，m 表示边数
注意在模板题中需要对下面的模板稍作修改，加上备份数组，详情见模板题。
int n, m; // n表示点数，m表示边数
int dist[N]; // dist[x]存储1到x的最短路距离
int backup[N]; // 备份数组防止串联
struct Edge // 边，a表示出点，b表示入点，w表示边的权重
{
int a, b, w;
}edges[M];
// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
for (int i = 0; i < n; i ++ )
{
memcpy(backup, dist, sizeof dist);
for (int j = 0; j < m; j ++ )
{
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
// 使用backup: 避免给a更新后立马更新b, 这样b一次性最短路径就多了两条边出来
dist[b] = min(dist[b], back[a] + w);
}
}
if (dist[n] > 0x3f3f3f3f / 2) return -1;
return dist[n];
}
b. SPFA 算法（队列优化的Bellman-Ford算法）
如果没有边数限制，一般用 SPFA 算法。并且在大部分情况下，SPFA 算法也可以直接替代 Dijkstra 算法用来求正权图。
SPFA 算法求最短路
时间复杂度 平均情况下 O(m)，最坏情况下 O(nm)，n 表示点数，m 表示边数
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储每个点到1号点的最短距离
bool st[N]; // 存储每个点是否在队列中
// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while (q.size())
{
auto t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j]) // 如果队列中已存在j，则不需要将j重复插入
{
q.push(j);
st[j] = true;
}
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
SPFA 判断图中是否存在负环
时间复杂度是 O(nm)，n 表示点数，m 表示边数
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N], cnt[N]; // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N]; // 存储每个点是否在队列中
// 如果存在负环，则返回true，否则返回false。
bool spfa()
{
// 不需要初始化dist数组
// 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。
queue<int> q;
for (int i = 1; i <= n; i ++ )
{
q.push(i);
st[i] = true;
}
while (q.size())
{
auto t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true; // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
if (!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
(3) 多源汇最短路
a. Floyd 算法
时间复杂度是 O(n^3)，n 表示点数
// 初始化：
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (i == j) d[i][j] = 0;
else d[i][j] = INF;
// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
推导过程
参考：https://blog.csdn.net/wjw7869/article/details/126459282
假设只允许经过 1 号城市和 2 号城市，求任意两点之间的最短路程，应该如何求呢？
我们需要在只允许经过 1 号顶点时任意两点的最短路程的结果下，再判断如果经过 2 号顶点是否可以使得 i 号顶点到 j 号顶点之间的路程变得更短，即判断 d[i][2] + d[2][j] 是否要比 d[i][j] 要小。
注意，允许经过某个点，不代表 i 和 j 之间的最短路一定经过该点！
//经过一号顶点
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
d[i][j] = min(d[i][j], d[i][1] + d[1][j]);
//经过二号顶点
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
d[i][j] = min(d[i][j], d[i][2] + d[2][j]);
因此以此类推：当允许通过所有顶点中转，代码将变成 Floyd 算法。
5. 最小生成树
(1) 朴素版 Prim 算法
时间复杂度是 O(n^2+m)，n 表示点数，m 表示边数
int n; // n表示点数
int g[N][N]; // 邻接矩阵，存储所有边
int dist[N]; // 存储其他点到当前最小生成树的距离
bool st[N]; // 存储每个点是否已经在 生成树中
// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{
memset(dist, 0x3f, sizeof dist);
int res = 0;
for (int i = 0; i < n; i ++ )
{
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
if (i && dist[t] == INF) return INF;
if (i) res += dist[t];
st[t] = true;
for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
}
return res;
}
(2) Kruskal 算法
模板题 AcWing 859. Kruskal 算法求最小生成树
时间复杂度是 O(mlogm)，n 表示点数，m 表示边数
int n, m; // n是点数，m是边数
int p[N]; // 并查集的父节点数组
struct Edge // 存储边
{
int a, b, w;
bool operator< (const Edge &E)const
{
return w < E.w;
}
}edges[M];
int find(int x) // 并查集核心操作
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int kruskal()
{
sort(edges, edges + m);
for (int i = 1; i <= n; i ++ ) p[i] = i; // 初始化并查集
int res = 0, cnt = 0;
for (int i = 0; i < m; i ++ )
{
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
pa = find(a), pb = find(b);
if (pa != pb) // 如果两个连通块不连通，则将这两个连通块合并
{
p[pa] = pb;
res += w;
cnt ++ ;
}
}
if (cnt < n - 1) return INF;
return res;
}
6. 二分图
(1) 染色法判别二分图
时间复杂度是 O(n+m)，n 表示点数，m 表示边数
int n; // n表示点数
int h[N], e[M], ne[M], idx; // 邻接表存储图
int color[N]; // 表示每个点的颜色，0表示未染色，1表示白色，2表示黑色
// 参数：u表示当前节点，c表示当前点的颜色
bool dfs(int u, int c)
{
color[u] = c; // 先给自己染上
// 遍历所有相邻的点
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!color[j])
{
// 如果之后遍历的点返回冲突则连锁冲突
if (!dfs(j, 3 - c)) return false;
}
// 如果两个相邻的点同色则冲突
else if (color[j] == c) return false;
}
return true;
}
bool check()
{
bool flag = true;
// Q: 为什么这里一定要遍历所有的点呢？
// A: 二分图的点不一定都是连通的
// 比如：如果有三个点另外成环，整个环是一个孤立环，其他都满足二分图，但是这个孤立环不满足二分图
for (int i = 1; i <= n; i ++ )
if (!color[i])
if (!dfs(i, 1))
{
flag = false;
break;
}
return flag;
}
(2) 匈牙利算法
时间复杂度是 O(nm)，n 表示点数，m 表示边数
int n1, n2; // n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx; // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int match[N]; // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N]; // 表示第二个集合中的每个点是否已经被遍历过
bool find(int x)
{
for (int i = h[x]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = true;
if (match[j] == 0 || find(match[j]))
{
match[j] = x;
return true;
}
}
}
return false;
}
// 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0;
for (int i = 1; i <= n1; i ++ )
{
memset(st, false, sizeof st);
if (find(i)) res ++ ;
}
链接：https://www.acwing.com/blog/content/405/
来源：AcWing
常用代码模板4——数学知识
1. 质数
(1) 试除法判定质数
bool is_prime(int x)
{
if (x < 2) return false;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
return false;
return true;
}
(2) 试除法分解质因数
void divide(int x)
{
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
int s = 0;
while (x % i == 0) x /= i, s ++ ;
cout << i << ' ' << s << endl;
}
if (x > 1) cout << x << ' ' << 1 << endl;
cout << endl;
}
(3) 朴素筛法求素数
模板题 AcWing 868. 筛质数
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (st[i]) continue;
primes[cnt ++ ] = i;
for (int j = i + i; j <= n; j += i)
st[j] = true;
}
}
(4) 线性筛法求素数
模板题 AcWing 868. 筛质数
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
2. 约数
(1) 试除法求所有约数
vector<int> get_divisors(int x)
{
vector<int> res;
for (int i = 1; i <= x / i; i ++ )
if (x % i == 0)
{
res.push_back(i);
if (i != x / i) res.push_back(x / i);
}
sort(res.begin(), res.end());
return res;
}
(2) 约数个数和约数之和
模板题 AcWing 870. 约数个数，AcWing 871. 约数之和
如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)
(3) 欧几里得算法
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
3. 欧拉函数
(1) 求欧拉函数
模板题 AcWing 873. 欧拉函数
int phi(int x)
{
int res = x;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
if (x > 1) res = res / x * (x - 1);
return res;
}
(2) 筛法求欧拉函数
int primes[N], cnt; // primes[]存储所有素数
int euler[N]; // 存储每个数的欧拉函数
bool st[N]; // st[x]存储x是否被筛掉
void get_eulers(int n)
{
euler[1] = 1;
for (int i = 2; i <= n; i ++ )
{
if (!st[i])
{
primes[cnt ++ ] = i;
euler[i] = i - 1;
}
for (int j = 0; primes[j] <= n / i; j ++ )
{
int t = primes[j] * i;
st[t] = true;
if (i % primes[j] == 0)
{
euler[t] = euler[i] * primes[j];
break;
}
euler[t] = euler[i] * (primes[j] - 1);
}
}
}
4. 快速幂
模板题 AcWing 875. 快速幂
求 m^k mod p，时间复杂度 O(logk)。
int qmi(int m, int k, int p)
{
int res = 1 % p, t = m;
while (k)
{
if (k&1) res = res * t % p;
t = t * t % p;
k >>= 1;
}
return res;
}
5. 扩展欧几里得算法
// 求x, y，使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y)
{
if (!b)
{
x = 1; y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= (a/b) * x;
return d;
}
6. 高斯消元
// a[N][N]是增广矩阵
int gauss()
{
int c, r;
for (c = 0, r = 0; c < n; c ++ )
{
int t = r;
for (int i = r; i < n; i ++ ) // 找到绝对值最大的行
if (fabs(a[i][c]) > fabs(a[t][c]))
t = i;
if (fabs(a[t][c]) < eps) continue;
for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]); // 将绝对值最大的行换到最顶端
for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c]; // 将当前行的首位变成1
for (int i = r + 1; i < n; i ++ ) // 用当前行将下面所有的列消成0
if (fabs(a[i][c]) > eps)
for (int j = n; j >= c; j -- )
a[i][j] -= a[r][j] * a[i][c];
r ++ ;
}
if (r < n)
{
for (int i = r; i < n; i ++ )
if (fabs(a[i][n]) > eps)
return 2; // 无解
return 1; // 有无穷多组解
}
for (int i = n - 1; i >= 0; i -- )
for (int j = i + 1; j < n; j ++ )
a[i][n] -= a[i][j] * a[j][n];
return 0; // 有唯一解
}
7. 组合计数
(1) 递推法求组合数
// c[a][b] 表示从a个苹果中选b个的方案数
for (int i = 0; i < N; i ++ )
for (int j = 0; j <= i; j ++ )
if (!j) c[i][j] = 1;
else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
(2) 通过预处理逆元的方式求组合数
首先预处理出所有阶乘取模的余数 fact[N]，以及所有阶乘取模的逆元 infact[N]
如果取模的数是质数，可以用费马小定理求逆元
int qmi(int a, int k, int p) // 快速幂模板
{
int res = 1;
while (k)
{
if (k & 1) res = (LL)res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}
// 预处理阶乘的余数和阶乘逆元的余数
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i ++ )
{
fact[i] = (LL)fact[i - 1] * i % mod;
infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}
(3) Lucas定理
若p是质数，则对于任意整数 1 <= m <= n，有：
C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p)
int qmi(int a, int k, int p) // 快速幂模板
{
int res = 1 % p;
while (k)
{
if (k & 1) res = (LL)res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}
int C(int a, int b, int p) // 通过定理求组合数C(a, b)
{
if (a < b) return 0;
LL x = 1, y = 1; // x是分子，y是分母
for (int i = a, j = 1; j <= b; i --, j ++ )
{
x = (LL)x * i % p;
y = (LL) y * j % p;
}
return x * (LL)qmi(y, p - 2, p) % p;
}
int lucas(LL a, LL b, int p)
{
if (a < p && b < p) return C(a, b, p);
return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}
(4) 分解质因数法求组合数
当我们需要求出组合数的真实值，而非对某个数的余数时，分解质因数的方式比较好用：
- 筛法求出范围内的所有质数
- 通过 C(a, b) = a! / b! / (a - b)! 这个公式求出每个质因子的次数。 n! 中p的次数是 n / p + n / p^2 + n / p^3 + ...
- 用高精度乘法将所有质因子相乘
int primes[N], cnt; // 存储所有质数
int sum[N]; // 存储每个质数的次数
bool st[N]; // 存储每个数是否已被筛掉
void get_primes(int n) // 线性筛法求素数
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
int get(int n, int p) // 求n！中的次数
{
int res = 0;
while (n)
{
res += n / p;
n /= p;
}
return res;
}
vector<int> mul(vector<int> a, int b) // 高精度乘低精度模板
{
vector<int> c;
int t = 0;
for (int i = 0; i < a.size(); i ++ )
{
t += a[i] * b;
c.push_back(t % 10);
t /= 10;
}
while (t)
{
c.push_back(t % 10);
t /= 10;
}
return c;
}
get_primes(a); // 预处理范围内的所有质数
for (int i = 0; i < cnt; i ++ ) // 求每个质因数的次数
{
int p = primes[i];
sum[i] = get(a, p) - get(b, p) - get(a - b, p);
}
vector<int> res;
res.push_back(1);
for (int i = 0; i < cnt; i ++ ) // 用高精度乘法将所有质因子相乘
for (int j = 0; j < sum[i]; j ++ )
res = mul(res, primes[i]);
8. 卡特兰数
给定 n 个 0 和 n 个 1，它们按照某种顺序排成长度为 2n 的序列，满足任意前缀中 0 的个数都不少于 1 的个数的序列的数量为： Cat(n) = C(2n, n) / (n + 1)
9. 简单博弈论
(1) NIM 游戏
给定N堆物品，第i堆物品有Ai个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取最优策略，问先手是否必胜。
我们把这种游戏称为NIM博弈。把游戏过程中面临的状态称为局面。整局游戏第一个行动的称为先手，第二个行动的称为后手。若在某一局面下无论采取何种行动，都会输掉游戏，则称该局面必败。
所谓采取最优策略是指，若在某一局面下存在某种行动，使得行动后对面面临必败局面，则优先采取该行动。同时，这样的局面被称为必胜。我们讨论的博弈问题一般都只考虑理想情况，即两人均无失误，都采取最优策略行动时游戏的结果。
NIM博弈不存在平局，只有先手必胜和先手必败两种情况。
定理： NIM博弈先手必胜，当且仅当 A1 ^ A2 ^ … ^ An != 0
(2) 公平组合游戏 ICG
若一个游戏满足：
- 由两名玩家交替行动；
- 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；
- 不能行动的玩家判负；
则称该游戏为一个公平组合游戏。
NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件2和条件3。
(3) 有向图游戏
给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。
任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。
(4) Mex运算
设 S 表示一个非负整数集合。定义 mex(S) 为求出不属于集合S的最小非负整数的运算，即：
mex(S) = min{x}, x 属于自然数，且 x 不属于 S
(5) SG函数
在有向图游戏中，对于每个节点x，设从x出发共有k条有向边，分别到达节点y1, y2, …, yk，定义SG(x)为x的后继节点 y1, y2, …, yk 的SG函数值构成的集合再执行 mex(S) 运算的结果，即：
SG(x) = mex({SG(y1), SG(y2), …, SG(yk)})
特别地，整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值，即SG(G) = SG(s)。
(6) 有向图游戏的和
设 G1, G2, …, Gm 是 m 个有向图游戏。定义有向图游戏 G，它的行动规则是任选某个有向图游戏 Gi，并在 Gi 上行动一步。G被称为有向图游戏 G1, G2, …, Gm的和。
有向图游戏的和的 SG 函数值等于它包含的各个子游戏 SG 函数值的异或和，即：
SG(G) = SG(G1) ^ SG(G2) ^ … ^ SG(Gm)
定理
有向图游戏的某个局面必胜，当且仅当该局面对应节点的SG函数值大于0。
有向图游戏的某个局面必败，当且仅当该局面对应节点的SG函数值等于0。
链接：https://www.acwing.com/blog/content/406/
来源：AcWing