网络流学习笔记
网络流是一个图论中很大的知识点，这里只涉及部分内容。本篇只涉及最大流、最小割和费用流的相关知识。
概念
一张有向图 \(G = (V, E)\)，对于每条边 \((u， v) \in E\) 都有一个权值 \(c(u, v) > 0\)，称为边的 容量。且对于图上没有的边 \((u， v) \notin E\)，\(c(u, v) = 0\)，则这张图叫做一个 网络，图中有两个特殊的点 \(s \in V\) 和 \(t \in V\)，这两个点称为 源点 和 汇点。
0%
「LibreOJ #10243」移棋子游戏 - 图论 + 博弈论 + SG 函数
题意描述
给定一个有 \(n (n \le 2000)\) 个节点的有向无环图，图中某些节点上有棋子，两名玩家交替移动棋子。
玩家每一步可将任意一颗棋子沿一条有向边移动到另一个点，无法移动者输掉游戏。
对于给定的图和棋子初始位置，双方都会采取最优的行动，询问先手必胜还是先手必败。
SG 函数学习笔记
SG 函数是解决博弈论问题的一种方法。
博弈论概念
公平组合游戏
首先我们需要了解以下几个概念。
公平组合游戏指的是一类满足下列条件的游戏：
- 有两名玩家交替操作；
- 每名玩家可用的操作与玩家的先后无关；
- 无法移动的玩家判负。
「Codeforces 1747D」Yet Another Problem - 构造 + 二分
题意描述
你有一个长度为 \(n (1 \le n \le 2 \times 10^5)\) 的整数序列 \(a\)。
你需要回答 \(q (1 \le q \le 2 \times 10^5)\) 个独立的问题，每次询问如下：
给定 \(l\) 和 \(r\)，你可以对序列做若干次操作（也可以不做），每次操作，你需要选择两个数 \(L\) 与 \(R\)，其中必须满足 \(l\le L\le R\le r\) 且 \(R-L+1\) 为奇数。然后将 \(a_L\sim a_R\) 的所有数改为 \(a_L\sim a_R\) 的异或和，即 \(a_L\oplus a_{L+1}\oplus \sim \oplus a_R\)。
你的目标是将 \(a_l\sim a_r\) 的所有数变为 \(0\)。每次询问完后，序列复原。
询问的答案即为最小操作数。如果总是不能达到目标，则答案为 \(-1\)。
「Codeforces 808G」Anthem of Berland - KMP + DP
题意描述
给定 \(s\) 串和 \(t\) 串，其中 \(s\) 串包含小写字母和问号，\(t\) 串只包含小写字母。
假设共有 \(k\) 个问号。
你需要给把每个问号变成一个小写字母，共有 \(26^k\) 种可能。
对于每种可能，设 \(t\) 匹配 \(s\) 的次数为 \(f_i\)，请输出 \(\max(f_i)\) 。
\(1\leq |s|,|t|\leq 10^5,|s|\cdot |t|\leq 10^7\)
Splay 学习笔记
一文概括 Splay
长文预警
平衡树
Splay 是一种平衡树，可以解决很多序列问题。而平衡树是一种二叉搜索树。
二叉搜索树则是一种数据结构，对于每一个节点，权值满足左儿子小于根节点小于右儿子，且整棵树的中序遍历是排序后的序列。这样二叉搜索树就可以解决很多问题，其时间复杂度取决于树的深度。
于是这里可以引出一种调试平衡树的常见方法：输出这棵树的中序遍历，看中序遍历是否为排序后序列。
然而在特殊数据下，二叉搜索树很容易退化成一颗链，于是就有了一种优化版本：平衡树。平衡树可以让二叉搜索树随时变化，以求深度保持相对较小，即“平衡”。而 Splay 就是一种平衡树。