{{{2013-03-16-sgu-321.markdown}}}
(
贪心，深度优先遍历时，如果发现某个节点不满足条件，则修改根到它路径上的第一条黑边。
时间复杂度$O(N)$
{{{2013-03-17-sgu-305.markdown}}}
给出$N$个二元组$(A_i, B_i)$，表示集合$S_i = {A_i \cdot k + B_i : k \in \mathbb{N}}$和数字$M$。求序列$X_1, X_2, \ldots, X_N$，满足$1 \leq X_i \leq M$且任意$X_i \neq X_j$，使得满足$X_i \in S_i$的$i$值最多。
(
匹配，注意到每个点最多需要保存$N$个可行的值，二分图的节点数只有$N + N^2$。
{{{2013-03-17-sgu-337.markdown}}}
给出长度是$N$的循环串$S$和阙值$K$，求最长的子串，满足前半部分和后半部分对应位置至多$K$个不同。多解则输出字典序最小的。
(
枚举子串长度$2l$，设$a_i = 1$表示$S_{i} \neq S_{i + l}$，否则$a_i = 0$，只需要检查是否存在$i$，使得$a_i + a_{i + 1} + \cdot + a_{i + l - 1} \leq m$。 （下标运算都在$\bmod n$意义下）
方便起见，把$S$复制一份，预处理${a_i}$的后缀和${p_i}$，前式等价于$p_i - p_{i + l} \leq m$。时间复杂度是$O(N^2)$
之后利用std::sort得到字典序最小的解，复杂度是$O(N^2 \log N)$
{{{2013-03-18-codeforces-round-174.markdown}}}
维护数组$\Delta_i$，表示前缀$A_1, A_2, \ldots, A_i$的改变量，删除$i$的时候，把$\Delta_i$加到$\Delta_{i - 1}$，时间复杂度$O(N)$。
模拟，计算$1, 2, 4, \ldots, 2^{k - 1}$步可达的状态。注意如果程序终止，则最多进行$O(\log n)$步。时间复杂度$O(N \log N)$。
首先，有环则无解。因为入度出度至多是$1$，所以图的形态是若干条链。另一方面，题目等价于解方程$\sum_{i} a_i \cdot x_i = t$。假设要求$x_1 < x_2 < \cdots < x_k$，则作变量代换$\delta_i = x_i - x_{i - 1} > 0$，方程变为$\sum_{i} (\sum_{j \geq i} a_j)\cdot \delta_i = t$，背包计数。
如果$x$可以被表示成$y$个整数的和，即存在$a$，使得$(2a + y - 1) \cdot y = 2x$，解之得$2a - 1 = \frac{2x - y^2}{y}$，即要求$\frac{2x - y^2}{y}$是奇数。
设$x = 2^{p} \cdot q, y = 2^{p'} \cdot q'$，显然$q'$是$q$的约数。当$p' = 0$时，条件自然满足。否则要求$p' = p + 1$。之后可以$O(1)$判断，是否可以改变$A_{i + 1}, A_{i + 2}, \ldots, A_{j - 1}$，使得$A_i, A_j$不变。最后设$f(i)$表示保持$A_i$不动，最少需要改动的元素数量，转移时枚举保持不变的元素$j < i$，用$f(j) + i - j - 1$更新$f(i)$。时间复杂度$O(N^2)$。
观察到，如果某个三元组不是环，则必有一个牛打败了其他两个牛。所以设$W_i$表示$i$胜利的次数，答案就是$\binom{n}{3} - \sum_{i} \binom{W_i}{2}$，所以只需要求$W_i$。
按照能力从低到高处理每个牛，用线段树维护包含当前牛的区间数，实际上只需要维护覆盖奇数次和偶数次元素的数量，时间复杂度是$O(N \log N)$。
{{{2013-03-19-sgu-309.markdown}}}
给出平面上$N$个点，求最小的$d$，使得存在$3$个$d \times d$的正方形，可以覆盖所有点。
(
二分答案$d$，考虑最上最下最左最右$4$条边，各边上至少有$1$个矩形。因为只有$3$个矩形，所以必然有$1$个矩形在角上，枚举这个角，类似地处理$2$个矩形的情况。复杂度是$O(4^2 N \log M)$，其中$M$是坐标范围。
{{{2013-03-19-sgu-330.markdown}}}
对于数$a$，可以取约数$d$满足$1 < d < a$，把$a$变为$a + d$。给出$A, B$, 问是否可能从$A$变为$B$，并输出长度小于$500$的任一解。
(
如果$A, B$都是偶数，则有解。每次找最大的$2^k$满足$2^k | A$且$A + 2^k \leq B$，把$A$变为$A + 2^k$，就可以得到$O(\log B)$长度的解。
如果$A$是奇数，则找到$A$最小的奇因子$d$，把$A$变为$A + d$，对$B$也同理，化为前面的情况。
{{{2013-03-21-sgu-323.markdown}}}
给出$N$个点$K$条边的无向图，边有种颜色和权值（颜色总数$M$），可以选择一种颜色免费，求免费之后生成树的最小值。
(
枚举免费的颜色，之后收费的边一定是原图最小生成树的边，只有$n - 1$种可能。时间复杂度是$O(K \log K + NM)$
{{{2013-03-21-sgu-409.markdown}}}
构造一个$N^2 \times N^2$的方阵，使得每行，每列，$N^2$个$N \times N$的方阵，都恰好有$K$个星号。
(
构造，方法见Code
{{{2013-03-21-sgu-410.markdown}}}
给出数列${A_i}$，可以进行两种操作：
- 把所有$A_i$减$1$，保持$A_i \geq 0$
- 把某个$A_i$加倍
求把所有$A_i$变为$0$的最小步数，如果长度不超过$1000$则输出方案。
(
首先，操作1的次数就是$m = \max{A_i}$。对于某个$A_i$，操作$2$肯定是贪心地使用：如果加倍后不超过最大叔则加倍。由此计算出操作$2$的次数，累加就是答案。
输出方案的时候需要利用优先队列，维护当前的最小数字。
{{{2013-03-22-sgu-344.markdown}}}
(
Floodfill
{{{2013-03-22-sgu-352.markdown}}}
给出$N$个点，$M$条边的无向图，和一颗以$1$为根的最短路树，求$V_i$表示把树上到点$i$的最后一条边删除后，点$1$到点$i$的最短路。
(
设$d_i$表示树上点$1$到点$i$的路径长度，$T_i$表示以$i$为根的子树，则$V_i = \max_{u \in T_i, v \not\in T_i}{ d_u + w(u, v) + d_v }$
按照dfs顺序求$V_i$，每个节点维护子树内的值，之后合并到父亲。可以实现可并堆，或者直接用启发式合并，时间复杂度是$O(M \log M)$
{{{2013-03-22-sgu-361.markdown}}}
构造$N \times M$的红蓝矩阵，使得任意$2 \times 3$和$3 \times 2$的子矩形内都恰好有$2$个蓝色格子，且蓝色格子总量最少。
(
构造，方法见Code
{{{2013-03-22-sgu-367.markdown}}}
(
贪心，每次解决耗时最少的题目，有多个时选择拓扑序最小的。
{{{2013-03-22-sgu-372.markdown}}}
给出$N$个数，数有两类，求一个数的排列$P_1, P_2, \ldots, P_N$，满足不存在连续$3$个同类的数，使得$$\sum_{i = 1}^M P_i \cdot (M - i + 1)$$最小。
(
对于同一类数，肯定是从小到大选择。设$f_{i, j, mask}$表示两类数分别取了$i, j$，且最后两个数类型是$mask$的最小值，转移时枚举当前选择数的种类。时间复杂度是$O(N^2)$
{{{2013-03-22-sgu-389.markdown}}}
设$V = {0, 1}^n$, 给出$v_1, v_2, v_3 \in V$，统计$v \in V$，使得$|v - v_1| = |v - v_2| = |v - v_3|$，答案模$(10^9 + 7)$
其中，$|u - v| = \sum_{i = 1}^n |u^i - v^i|$
(
单独考虑每一位。设$c_x$表示$x$的出现次数，先忽略000和111，最后把答案乘以$2^{c_{000} + c_{111}}$. 观察到，$011$既可以给$|v - v_1|$增加$1$，也可以给$|v - v_2|$和$|v - v_3|$增加$1$，不妨把后者看做是把$|v - v_1|$减少$1$，在这个意义下$011$等价于$100$，所以可以枚举$|v - v_i|$的 净值
{{{2013-03-23-sgu-229.markdown}}}
(
先枚举旋转平移的方式，一共只有$4 \times 2N \times 2N$种变换。设$T(p)$表示$p$变换后的点，从$p$往$T(p)$连边，因为入度和出度都不超过$1$，所以图的形态是若干环和链，只要每个分量大小都是偶数即可。奇偶染色就能得到方案。
{{{2013-03-23-sgu-230.markdown}}}
求一个$1 \sim N$的排列$P_1, P_2, \ldots, P_N$，满足$M$个形如$P_{A_i} < P_{B_i}$的限制。
(
拓扑排序即可。
{{{2013-03-23-sgu-269.markdown}}}
给出$A_1, A_2, \ldots, A_N$和$M$，统计$x_1, x_2, \ldots, x_N$的数量，满足：
$-1 \leq x_i \leq A_i$ - 恰有$M$个$x_i \neq -1$
- 不存在$i \neq j$，使得$x_i = x_j \geq 0$
把$A_i$排序，设$f_{i, j}$表示前$i$个数中，有$j$个$x_k \neq -1$，则当前$x_i$有$(A_i - (j - 1)) + 1$种选法。时间复杂度是$O(NM)$
{{{2013-03-23-sgu-280.markdown}}}
给一颗$N$个点的树和常数$K$，一个点能够覆盖距离不超过$K$的所有点，选择最少的点覆盖所有点。
(
贪心，每次选择最深没被覆盖的点，选择它的$K$级父亲，复杂度是$O(NK)$
{{{2013-03-23-sgu-397.markdown}}}
实现一个文本编辑器，支持$N$次操作：
- 在光标位置插入一个字符
- 左右移动光标一个位置
(
以光标位置为分界，维护两个栈。
{{{2013-03-26-sgu-311.markdown}}}
维护一个集合，进行$q$次操作：
- 插入$n$个$c$
- 如果最小的$n$个数总和不超过$t$，则删除
(
普通的数据结构（我用了树状数组）。
{{{2013-03-26-sgu-342.markdown}}}
给出$n$和$b$，求$\sum_{i = 0}^{\infty} x_i \cdot b^i = n$，使得$\sum_{i = 0}^{\infty} |x_i|$最小。
(
最优解中$|x_i| < b$，而$n \equiv x_0 \pmod b$，则$x_0$只有$n \bmod b$和$n \bmod b - b$两种可能，唯一的区别是是否有进位，于是设$f_{i, j}$表示已经考虑了后$i$位，进位是$j$的最小绝对值和，注意到$j < 2$，所以复杂度是$O(\log_b n)$
{{{2013-03-26-sgu-384.markdown}}}
给出无向图$G$，满足任意$u \neq v$恰有一个共同的邻居，支持$2$种操作：
-
询问$u$到$v$的最短路
-
删除边$(u, v)$
(点数不超过$10^5$，询问不超过$2 \cdot 10^5$)
实际上图很特殊，由若干个共点的三角形组成，暴力即可。
{{{2013-03-28-sgu-318.markdown}}}
给出$M$个${1, 2, \ldots, N}$的子集$S_1, S_2, \ldots, S_M$，把${1, 2, \ldots, N}$划分成若干不相交的集合$P_1, P_2, \ldots, P_k$，满足对于任意$P_i$和$S_j$，$P_i \subset S_j$或$P_i \subset \bar{S_j}$成立，求$k$的最小值。
(
对于元素$x, y$，属于同一个划分等价于对于任意$i$，$x, y \in S_i$或者$x, y \in \bar{S_i}$，记为$x \sim y$。而$x \sim y$是等价关系（易证），所以只要看等价类数目即可。
复杂度是$O(N^2 M)$
{{{2013-03-30-sgu-212.markdown}}}
给出$N$个点，$M$条边的有向无环图，求阻塞流。阻塞流即不存在增广路（不考虑反向弧）的流。
(
使用了阻塞流的Karzanov算法，可以参考Combinatorial Optimization的定理8.20。时间复杂度是$O(N^2 + M)$
{{{2013-04-02-sgu-247.markdown}}}
数${1, 2, \ldots, 2p}$的$p$元子集的个数，其元素之和是$p$的倍数。
(
答案是$\frac{\binom{2p}{p} - 2}{p} + 2$，推导过程的提纲：
- 化为计算$\sum_{i = 1}^{k} x_i \equiv 0 \pmod p$的解数
- 任选$x_1, x_2, \ldots, x_{p - 1}$，之后$x_p$（不记重复）只有$2$种可能
- 重复的情况是$2 x_1 + \sum_{i = 2}^{k - 1} x_i \equiv 0 \pmod p$的解数，因为$Z_p$是域，所以$2$的因数没有意义，类似上面继续容斥
- 最后利用$\sum_{i = 0}^{n} (-1)^i \binom{n}{i} = 0$化出闭公式
{{{2013-04-10-sgu-327.markdown}}}
给出字符串$w_1, w_2, \ldots, w_n$，求最短的回文串包含它们作为子串。
(
不考虑回文串，去掉被包含的子串，使用状态是$2^n \cdot n$，转移是$n$的状态压缩动态规划。
考虑回文串，只需要包含$w_i$或者$\bar{w_i}$（$w_i$的回文），特殊处理一下首个串即可。
{{{2013-04-11-sgu-319.markdown}}}
给出$N$个平行于坐标轴的矩形（没有公共点），问联通块的面积。
(
扫描线，维护当前每个位置的矩形标号，矩形进入的时候读取当前标号，即包含该矩形的矩形标号，更新矩形标号，离开的时候覆盖为父亲的标号，线段树可以解决。
{{{2013-04-11-sgu-379.markdown}}}
(
首先，电梯一定以$0 \to i \to 0$的形式运行，设$x_i$表示$0 \to i \to 0$的循环数量，我们求把所有人都送到$0$层的最少时间，即要求对任意$i$，有$C \cdot \sum_{j \geq i}x_j \geq \sum_{j \geq i} A_j$，同时最小化$\sum i \cdot x_i$
从式子可以看出，越高楼层的代价越大，所以应该按照$i$递减进行贪心。复杂度是$O(N)$
之后注意到，最后取的人数，肯定是把$1, 2, \ldots, (i - 1)$的所有人，以及第$i$层的若干人送到$0$层，而第$i$层选取的人数可以二分，之后用贪心检查即可，总的复杂度是$O(N^2 \log A)$
{{{2013-04-22-tco-12-round-1a.markdown}}}
有A, B两类饮料，初始时都是$1$单位。$N$个人轮流喝，奇数轮喝$A$类，偶数轮$B$喝$B$类，每次喝剩余的一半，喝得（严格）最多的胜者。给出每个人喝的次数，问谁可能是胜者。
因为$\frac{1}{2} > \frac{1}{4} + \frac{1}{8} + \cdots$，所以喝的次数不少于$2$的都可能是胜者。
给出$N$，统计满足条件的$(x, y)$：
$x > y > 0$ $\gcd(x, y) = 1$ $x \cdot y = i!, 1 \leq i \leq N$
枚举$i$，设$1 \sim i$中的质数有$p$个，则$i!$有$p$个质因子，而每个质因子只能属于$x$或者$y$中的一个，共有$2^{p}$种方法，由于$x < y$的限制，共有$2^{p - 1}$种方法。
给出$N$个开关，$M$个灯泡，每个开关控制若干个灯泡，每个灯泡最多被$2$个开关控制，用最少的开关把所有灯关掉。
因为每个灯泡只连着两个开关，实际上就是要求两个开关的状态相同（或者相异），问题就是二分图染色，而对于一个联通块最多只有$2$个可行解，枚举取最小即可。
{{{2013-04-23-tco-12-round-1b.markdown}}}
有$N$根铅笔，长度给出，拼成$K \times K$的矩阵，每行要么是长度是$K$的铅笔，要么是长度之和是$K - 1$的两根铅笔，问$K$的最大值。
枚举$K$，统计长度是$K$和和是$K - 1$的配对数量，如果不小于$K$就是合法的。
有$N$个任务要做，给出需要的时间。初始时有$1$个狐狸，每个狐狸只愿意做$1$个任务，可以花费$\mathrm{splitCost}$时间使它分裂，问完成所有任务的最短时间。
动态规划，设$f(\mathrm{split}, \mathrm{fox}, \mathrm{work})$，表示已经分裂了$\mathrm{split}$轮，当前有$\mathrm{fox}$个狐狸，已经完成了耗时最长的$\mathrm{work}$个工作所需要的时间，转移时枚举当前这轮使用的狐狸数量，复杂度是$O(N^4)$
交换前排等价于交换后排，所以只考虑交换前排。动态规划，设$f(\mathrm{mask})$表示$\mathrm{mask}$中的人还没有确定位置，每次转移枚举谁跟当前最小的没配对的人配对，复杂度是$O(2^n \cdot n)$
{{{2013-04-24-tco-12-round-1c.markdown}}}
给出$N$个长度相同的数字，求有多少个数字，和每个数字恰有一位不同。
对于每个数字，枚举不同的数字。
给出$N \times M$的网格，边有长度，增加某些边的长度，使得$(0, 0) \to (N, M)$的所有路径长度相同，求长度的最小值。
答案就是最长路，动态规划。
给出字符串，每种字符至多出现$2$次，可以任意交换两个位置的字符，求变成回文串的最小交换次数。
不妨假设长度是偶数，否则出现恰好$1$次的字符一定要交换到中间，从而每个字符都出现$2$次。然后把字符出现的位置连一条边，连通分量的数量就是需要的交换次数。
{{{2013-05-24-tco-12-round-2a.markdown}}}
有$N$个开关和$N$个灯泡，开关和灯泡一一对应。有$M$个测试结果，形如：开关集合$A_i$控制灯泡集合$B_i$。求为了确定开关灯泡对应关系，需要进行测试的最小值。
如果开关$i$和灯泡$j$对应，要求在$M$组测试中，$i$和$j$的状态都相同（同为开或关）。只要求出对应的$M$位二进制数，对于每个二进制数，判断对应的开关，灯泡数量是否相等。
额外的测试采用二分法，每次选择一半进行测试，可以讲规模缩小一半。
数轴上有$x_1, x_2, \ldots, x_n$共$n$个点，你要按照$x_1 \to x_2 \to \cdots \to x_n$的顺序遍历。可以建立$k$个传送点，传送点之间可以瞬间移动，问遍历的最小代价。
因为目标函数是线性的，传送点一定在原有的$n$个点中。有传送点之后，设$f(k, i)$表示在$x_1, x_2, \ldots, x_i$中建立$k$个传送点的最小代价，转移时枚举下一个传送点的位置$j$，考虑$x_p \to x_{p + 1}$对答案的贡献，有$3$个情况：
-
$x_p, x_{p + 1}$ 不在区间$[x_i, x_j]$中，贡献为$0$ -
$x_p, x_{p + 1}$ 在区间中，贡献为$\min{|x_p - x_{p + 1}|, |x_i - x_j| - |x_p - x_{p + 1}|}$ -
$x_p, x_{p + 1}$ 恰有一个在区间中，贡献是到端点的最小距离，另外一段会在其他时候计入答案
为了实现简便，可以在无穷远处添加两个虚拟的传送点。
有向无环图$G$，最多$32$个点可能有障碍，问有多少种障碍的安排方式，使得点$0$到点$1$有偶数条路径。
折半，按照拓扑序把$32$个障碍分成前一半和后一半。分别暴力枚举一半的安排方式，dp算出以某点为终点和以某点为起点的路径（奇偶性）。注意到可能的中间点只有$17$个（实际上就是后一半的障碍，以及终点），所以合并可以用Fast Walsh–Hadamard transform做。
要注意常数，可以用位运算把动态规划优化到$O(N)$
{{{2013-05-25-tco-12-round-2b.markdown}}}
二分答案，如果射击已知的分值，则必是已知的最高分值。射击未知的位置，则尽量平均分配。枚举射击未知位置多出的部分，之后是线性函数直接取端点的最大值即可。
有$N$本书，重量已知。甲乙轮流操作，甲先选择$m_0$，乙把得到的书选$m_1$本给甲，如此轮流。两人都想最大化对方与自己的书本重量差，如果多解则最大化总重量，问两人最后的重量。
在甲第一轮选定之后，两人必定贪心地进行，每次选出自己最重的书给对方，可以通过模拟知道第$i$重的书最后的归属，之后就是简单的背包。
把$a + b, 2a + b, \ldots, na + b$写成二进制，问相邻两位不同的数量。
注意到每个数的最高位都是$1$，只要知道奇偶数的数量，就能算出跨越两个数的改变了。之后计算每个数的改变。
因为对答案贡献是线性的，可以考虑每一位的贡献，假设是第$i$位。注意到两件事：
-
$2^{i + 2}$ 是循环节长度 -
第i位要在$\Theta(2^i / a)$才会改变一次
于是对于每位，只要处理$\Theta(a)$次即可。
{{{2013-05-28-tco-12-round-2c.markdown}}}
每条边可能取值只有$2N$种，枚举模拟即可，复杂度是$O(N^4)$
给出$N$个点$(x_i, y_i)$，统计满足$x_i < x_j < x_k$且$y_i < y_k < y_j$的三元组$(i, j, k)$的数量。
经典题，$132 = 1?? - 123$，等式右边的两种情况都可以用树状数组处理。
给出序列$a_1, a_2, \ldots, a_n$，定义一次操作为，对于每个$a_i > 0$，把$a_i$减$1$，同时$a_{(i + 1) \bmod n}$加$1$，求$T$次操作后的序列。
模拟，把多次操作合并，每轮可以减少一个正数，或者减少一个非负数。当遇到以下$3$种情况：
-
全非正
-
全正
-
全部是$0$或$1$
终止模拟，直接得到最终结果。仔细分析可以得到模拟的轮数是$O(N^2)$级别的。
{{{2013-05-29-tco-12-round-3a.markdown}}}
给出$N$个点的无向图，每个点的度都不小于$N - 3$，问点色数。
考虑补图，补图的度都不超过$2$，即每个联通块是链或环。两个点可以同色，当且仅当补图里面有边相连，于是除了$3$元环外，$k$个点的联通块需要$\lceil \frac{k}{2} \rceil$种颜色。
本质是判断是否有$3$条不相交路径，拆点之后网络流。另外一个问题是棋盘太大，但是只要保留附近的几列即可。
如果牛的周期两两互质，根据CRT很容易算出最终答案。考虑到牛的周期不超过$50$，所以可能出现超过$1$次的质因子只有$2, 3, 5, 7$，那么不如按照$\bmod 2^5 \times 3^2 \times 5^2 \times 7^2$分类，这样周期中$2, 3, 5, 7$的因数都会消失，套用前面算法即可。不过这样有点太慢，可以把$\bmod 7^2$去掉，这样周期中可能有$7$和$49$，直接把$7$当$49$即可。
{{{2013-05-30-tco-12-round-3b.markdown}}}
有$N$个长条，长度不同，河有$W$宽，陆地有$L$宽，长条在河里会下沉$D$，问是否存在一个长条摆放方案，从左到右每次高度最多增加$1$
枚举，枚举河，陆地最左最优的高度，检查合法性即可。
给出$N$个数字片段，统计$N!$中拼接方式中，最终结果是$11$倍数的方案数。
先考虑奇数长度的片段，假设有$k$个，显然有$\lfloor \frac{k}{2} \rfloor$个是在$1$的，$\lceil \frac{k}{2} \rceil$个是在$-1$的，背包$f(i, j, k)$表示考虑了前$i$个，有$j$个取了$1$，模$11$是$k$的方案数。
最后再把偶数长度的插入，这样不会影响奇数的，利用原来的状态，稍微修改转移即可。
给出$N$个点，无三点共线，问有多少个子集，点集的凸包包含给定的$P, Q$两点。
只考虑包含$P$点的情况，补集成为不包含$P$点的，之后极角排序扫描即可。
之后去掉包含$P$，但是不包含$Q$的情况，按照$Q$和凸包的切点分类，枚举切点之后利用上面方法即可，复杂度是$O(N^2)$
{{{2013-06-02-tco-12-semifinal-1.markdown}}}
给$3$个长度是$2500$的01串$A, B, C$，定义$(i, j, k)$是白格子当且仅当$A_i = B_j = C_k$，求不和边界连通的白格子数量。
分开考虑01两种字符，再考虑每一个$i$，称为层，能想想每层都是一样的形状，$j, k$同理。所以只要该字符不在字符串头尾即可。
给出排列$P$的Burrows–Wheeler transform的前若干位，求字典序最小的结果。（注意不是原排列的字典序）
设结果是$Q$，从$i$往$Q_i$连边，得到的有向图应该是个环，在此基础上贪心即可。
求满足以下条件的序列$A_1, A_2, \ldots, A_n$的数量：
-
$1 \leq A_n \leq m$ -
$A_i, A_{i + 1}, \ldots, A_{i + k - 1}$ 线性相关
首先如果$k > \log(m + 1)$，则任意$k$个数都线性相关，答案是$m^n$。否则，考虑补集，有某$k$个线性无关的序列数量。设$ways(i, j)$表示$A_1, A_2, \ldots, A_i$中，最后$j$个线性无关的序列数量，有两种转移：
-
下一个元素和最后$j$个线性无关，转移到$f(i + 1, j + 1)$，有$m + 1 - 2^j$种方案
-
否则，枚举下一次最后$k$个线性无关，那么新元素一定在$A_{i - k + 1}, A_{i - k + 2}, \ldots, A_i$张成的空间内，有$2^{k - 1}$种方案
矩阵乘法加速即可。
{{{2013-06-03-tco-12-semifinal-2.markdown}}}
给出长度为奇数的，包含左右箭头的字符串，每次选择一个不在两端的字符，如果是左箭头，则删除它和它左边的字符，否则删除它和它右边的字符，问最后可能留下字符。
设$can(i, j)$表示能否把$i\ldots j$删完，转移时枚举最后删除的两个字符是$x, y$，则要求$can(i, x - 1), can(x + 1, y - 1), can(y + 1, j)$。
一个自然数集是独立的，当且仅当$2^n$个子集按位或值都不同。给出一个自然数集，求一个独立的子集，数字之和最大。
能够证明，一个集合是独立的，当且仅当对于每个数，都有一个二进制位只有他具有，成为标识位。
枚举标识位的集合$mask$，数$a$可以被标识，当且仅当$mask$和$a$的交恰为$1$，所以只需要贪心选取即可。
有$n$个四人队，每个队有$A_i$只兔子，每个兔子要给其他队的队员一个胡萝卜，每个队员最多收到一个胡萝卜，问不同的方案数。
容斥，需要计算至少$k$只兔子给了同队的人萝卜的方案数。设$ways(i, j)$表示前$i$队，已经有$j$只兔子给了同队萝卜，转移时枚举该队有多少兔子给了同队萝卜。最后对于$ways(i, j)$，还有$m -j$只兔子没有给出萝卜，这部分的方案数是$(4n - j) \cdot (4n - j - 1) \cdots (4n - m + 1)$，最后交错加到答案即可。
{{{2013-06-06-srm-581.markdown}}}
一共只有$N - L + 1$个可能的区间，计算它们各自包含黑格的数量。对于格子$i$：
-
如果可以被包含，则存在某个包含$i$的区间，其包含的黑格数量在输入中出现
-
如果可以不被包含，则输入的黑格数量集合，是不包含$i$的区间的黑格数量集合的子集
给出$2$颗$N$(
因为树上两点之间路径唯一，所以环一定由两颗树上的路径组成。预处理出$count_T(i)$表示树$T$上，长度恰好是$i$的路径数量。
由期望线性性，单独考虑每个环。枚举树$A$上的路径长度是$x$，则$B$上的路径长度是$K - 2 - x$，这样的环数量是$count_A(x) \cdot count_B(K - 2 - x) \cdot 2$，出现的概率是$\frac{(n - 2)!}{n!} = \frac{1}{n \cdot (n - 1)}$，累加即可。
如果只有一种操作，可以枚举第一行的状态，用位运算推倒一遍。加入新操作和限制之后，可以每一列使用的操作类型。粗看复杂度是$O(2^{n + m})$的，实际上每一行取反的格子都必须是个子集，总的枚举量只有$O(3^{m})$。
{{{2013-06-09-tco-13-round-3a.markdown}}}
给出长度为$N$(
当$K \geq 2$时，数组中的数都是原数组中$x (3 \leq x \leq 2^K)$个元素按位与的值。$O(2^N)$枚举原数组的所有子集即可。
注意$K = 1$的情况
给出$S (\leq 10^{18}) , T (\leq 10^5) , n (\leq 10^9) , m (\leq 100)$，统计满足条件的序列个数：
-
$x_i \geq 1$ -
$x_1, x_2, \ldots, x_n \leq T$ -
$x_1 + x_2 + \cdots + x_n + x_{n + 1} + \cdots + x_{n + m} \leq s$
答案模$(10^9 + 7)$,
因为$n \cdot t \leq s$，答案就是$$\sum_{x_1 = 1}^T \sum_{x_2 = 1}^T \cdots \sum_{x_n = 1}^T \binom{S - \sum_{i = 1}^n x_i}{m}$$
注意到$\binom{x}{m}$是$m$次多项式，可以$O(m^2)$求出$\binom{x}{m} = \sum_{i = 0}^m c_i \cdot x^i$
考虑$k$次项$(S - \sum_{i = 1}^n x_i)^k$，完全展开后每项具有形式$$x_1^{p_1}x_2^{p_2}\cdots x_n^{p_n} S^{p_{n + 1}}$$，其中$p_1 + p_2 + \cdots p_{n + 1} = k$
取遍所有$x_1, x_2, \ldots, x_n$求和，结果是$P(p_1) \cdot P(p_2) \cdots P(P_n) \cdot S^{p_{n + 1}}$，其中$P(k) = 1^k + 2^k + \cdots + t^k$，可以$O(Tm)$预处理。
之后解决展开项的系数，忽略$S$的部分，设$d(i, j)$表示已经有$i$个非零项，指数之和是$j$，考虑顺序，并计入$P(k)$的系数，即：
之后计算答案的时候，可以枚举$S$部分的指数$j$，以及非零指数的个数$i$, 即要在前面$n$个变量中选择$i$个，还要计入指数为$0$的项对答案的贡献，总之最后需要累和：
总的复杂度是$O(m^3)$
{{{2013-06-11-srm-580.markdown}}}
选中的点一定是区间的端点，$O(N^2)$枚举右端点，$O(N)$统计。时间复杂度是$O(N^3)$
只需单独考虑点$i$发送的消息。
广播的结果是一个区间，合法当且仅当它包含"最小的右端点"和"最大的左端点"即可。只要认为选择区间$i$不需要费用，从左到右贪心即可。复杂度是$O(N^2)$
两个重要的结论：
-
对于每行，乙放置的墙是连续的
-
如果下方无墙，甲一定会向下走
所以可以用$(x, y, l, r)$表示棋子在$(x, y)$, 墙的范围是$[l, r)$，最后的代价。
{{{2013-06-21-tco-13-round-1a.markdown}}}
-
$\max{B_{i, j}} - \min{B_{i, j}} \leq 1$ -
$\sum{|A_{i, j} - B_{i, j}|}$ 最小
枚举$\min{B_{i, j}}$，贪心
长度是$D$(
一定存在$k, i$，使得$k \cdot x = R_i$，枚举检查可行性，注意精度
当且仅当每个顶点的入度和出度都是$1$，对顶点拆点，建出二分图，最小费用最大流
{{{2013-06-21-tco-13-round-1b.markdown}}}
给$N$个数$A_1, A_2, \ldots, A_N$，将其两两配对，使得和的极差最小。
假设$A_1 \leq A_2 \leq \cdots A_N$，最优解一定是$A_i$与$A_{N - i + 1}$配对。
给出字符串集合$S$，每次可以对某个字符串操作，选择某个长度为偶数的前缀反转，相同的字符串可以消去，问进行若干次操作后集合大小的最小值。
字符串$A_1, A_2, \ldots, A_N$和$B_1, B_2, \ldots, B_N$等价，当且仅当集合${{A_1, A_2}, {A_3, A_4}, \ldots, }$和${{B_1, B_2}, {B_3, B_4}, \ldots, }$相等，是等价关系，只要求出每个等价类大小即可。
{{{2013-06-22-tco-13-round-1c.markdown}}}
数组$A_1, A_2, \ldots, A_N$满足：
-
$A_1 = \mathrm{first}$ -
$A_N = \mathrm{last}$ -
$|A_{i} - A_{i + 1}| \leq D$
求$\max{A_i}$
你参加TC比赛，有$N + 1$个房间，你在第$N + 1$号房间。你知道$A_1, A_2, \ldots, A_N$，表示第$i$号房间分数的和，求你最少需要的得分，保证分数比你高的人不超过$K$个。
二分答案贪心
由线性性，只需计算每个格子被支配的概率。而这个概率只和能支配他的格子数目有关，分类讨论求出$\mathrm{count}[x]$表示恰有$x$个格子可以支配它的格子数量，累加即可。
注意避免精度误差。
{{{2013-07-07-segment-tree.markdown}}}
区间修改，询问，标记的线段树。
树节点存储的信息分为两种：
-
标记flag
-
数据data
其中flag只用于懒标记，与题目要求的信息无关。
表示维护的值，支持Data merge(Data A, Data B)
修改节点$[l, r]$，同时更新flag和data，注意这时候data应可被访问（带有正确的，更新后的值）
撤消节点$[l, r]$的标记，并对儿子进行对应的change_node
就是data = merge(left_data, right_data)
其他函数对于一切题目都一样
def change(l, r, a, b, )
if (b < l) or (r < a) then return
if (a <= l) and (r <= a) then
change_node(l, r, )
else
push_down(l, r)
change(l, m, a, b, )
change(m + 1, r, a, b, )
update(l, r)
def query(l, r, a, b)
if (b < l) or (r < a) then return Data()
if (a <= l) and (r <= a) then return data[l, r]
return merge(query(l, m, a, b), query(m + 1, r, a, b))
{{{2013-08-23-tco-12-wildcard.markdown}}}
一匹超级马，能$(x, y) \to (x', y')$当且仅当$(x - x')^2 + (y - y')^2 = D$，问是否能$(0, 0) \to (A, B)$。
共有$O(\sqrt{D})$种可能的移动，设为${(x_1, y_1), (x_2, y_2), \dots, (x_k, y_k)}$。不失一般性，假设$\gcd(x_1, x_2, \dots, x_k) = \gcd(y_1, y_2, \dots, y_k) = 1$。
利用$(0, 0) \to (x_i, y_i) \to (2x_i, 0)$的移动，再由$\gcd(x_1, x_2, \dots, x_k) = 1$，可得$(0, 0) \to (2, 0)$。同理$(0, 0) \to (0, 2)$。从而只要研究$(0, 1), (1, 0), (1, 1)$是否可达，同时只有$4$类移动。易知当且仅当存在$(x_i, y_i)$满足$x_i + y_i \equiv 1 \pmod 2$时$(0, 1)$和$(1, 0)$可达。
如果有环显然无解。否则，按照拓扑序计算$end(\mathbf{X})$表示$\mathbf{X}$可能的后缀。之后原来的方程可以写作$\mathbf{A} + end(\mathbf{A}) = \mathbf{B} + end(\mathbf{B}) + \mathit{val}$，两边约去公共后缀可以得到新的$N$个方程。不断迭代$N$次，把每次的$end(\mathbf{X})$相加即可。
给出字符串$A, B$，求满足下列条件的字符串序列$(x_1, x_2, \ldots, x_k)$的数量：
-
$x_1 = A$ -
$x_k = B$ -
$x_{i}$ 由$x_{i - 1}$插入一个字符得到
先考虑$A$是空串，相当于每次要删掉$B$的一个字符，求不同的方案数量。为了避免重复，要求对于连续若干个相同的字符，必须删除最后一个。设$f(l, r)$表示把$[l, r)$的子序列全部删除的方案数。枚举最后一个删除的字符是$k$，我们要求$B[k] \neq B[r]$。从而$[l, k)$和$[k + 1, r)$都是独立的，方案数是$$f(l, k) \cdot f(k + 1, r) \cdot \binom{r - l - 1}{k - l}$$。
如果$A$不是空串，只要枚举$A$出现的位置即可，也可以用递推解决。
复杂度是$O(|B|^3 + |A|^2 |B|)$。
{{{2013-08-25-tco-13-round-2b.markdown}}}
对于给出的$a_1, a_2, a_3$，求$b_1, b_2, b_3$使得$$\min_{i \neq j} |(a_i \cdot x + b_i) - (a_j \cdot y + b_j)|$$最大。
(
不妨设$b_1 = 0$，而$0 \leq b_i < a_i$，枚举$b_2, b_3$，只需计算$$|(a_i \cdot x + b_i) - (a_j \cdot y + b_j)| = |\gcd(a_i, a_j) \cdot z + (b_i - b_j)|$$的最小值。
朴素的想法是，设$S$是当前棋子可能的位置，初始是全体顶点。当$|S| = 1$时，位置即被乙所知，问题转化为图上的最长路，但是顶点太多。设$f(S)$是$S$开始的最长路，注意到$$f(S) = \max_{x, y \in S}f({x, y})$$即可。
按照黑色格子的最小外接矩形分类，而$2$个矩形一定会覆盖外接矩形的$2$个对角（有$2$种覆盖方法）。所以，棋盘合法当且仅当：
-
$4$ 个边界上都有黑色格子 -
至多$1$种覆盖不到
共有$6$个区域，至多$2^6$种格子，统计出$count[mask]$表示$mask$格子的数量，递推即可。
{{{2013-08-26-tco-13-round-2c.markdown}}}
偶然发现的玩具Hakyll。
魔都今天起风了。
题目等价于给出$1000$行，$10000$列的$01$矩阵，询问给定两列是否有公共的$1$。把矩阵的第$i$列表示成二进制数$b_i$，等价于询问$b_i & b_j > 0$，可以压位加速。
考虑其中一项，例如$|(I_a - J_a) - (I_b - J_b)|$，按照${I_a - J_a}$排序后即可求出。
二分答案$\lambda$, 问题转化为计算$$i^2 + 100000 i + j^2 - 100000 j + i \cdot j \leq \lambda$$的解数。枚举$i$，变为关于$j$的二次不等式，直接求解。
令$B(n)$为Bell数，即$[n] = {1, 2, \dots, n}$划分的方案数，易得 $$ B(0) = 1, \ B(n) = \sum_{k = 0}^{n - 1} \binom{n - 1}{k} B(k)$$
再令$b(x)$为${B_n}$的指数生成函数，由递推关系有
$$ b(x) = \sum_{n = 0}^{\infty} \frac{B_n x^n}{n!} \
= 1 + \sum_{n = 1}^{\infty} \frac{\left( \sum_{k = 0}^{n - 1} \binom{n - 1}{k} B(k) \right) \cdot x^n}{n!} $$
改变$n, k$求和的顺序
$$ = 1 + \sum_{k = 0}^{\infty} B(k) \left( \sum_{n = k + 1}^{\infty} \frac{\binom{n - 1}{k} x^n}{n!} \right) \
= 1 + \sum_{k = 0}^{\infty} B(k) \left( \sum_{n = k + 1}^{\infty} \frac{\frac{(n - 1)!}{k! (n - 1 - k)!} x^n}{n!} \right) \
= 1 + \sum_{k = 0}^{\infty} \frac{B(k)}{k!} \left( \sum_{n = k + 1}^{\infty} \frac{x^n}{n \cdot (n - 1 - k)!} \right) $$
分母的$n$碍事，对$x$求导
为了求出$b(x)$，需要利用$(\ln f)' = \frac{f'}{f}$，即
另一方面，
考虑指数生成函数
秋天已经来了，外出的时候都忍不住多穿一件衣服。
这两天在读袁豪前辈的论文，对前辈钦慕的同时，也稍微对这个世界重新产生了兴趣。
今天突如其来的消息，让梦想、希望都坍塌殆尽。
所以，无法成为勇者的我，无可奈何决定去打工。
今天成都赛区结束了，从结果上看，题目还是比较成功的。作为G的出题人稍微啰嗦两句。 （@wuyiqi：对不起）
动态维护自动机似乎比较难，我们考虑每次暴力重建。考虑维护heap和buffer两个自动机，每次插入到buffer中，并重建buffer。当buffer的大小超过某个阈值时，把buffer和heap合并，并重建heap。询问时在heap和buffer上直接询问即可。 假设单词的总长度是$L$，文本的长度是$Q$，复杂度是$O(L \cdot \sqrt{L} + Q)$。
Seter在赛场的做法。
注意到按照$\sqrt{L}$分块太蠢了，参考二项堆的方法，可以维护$O(\log{L})$个自动机，当第$i$号自动机大小超过$2^i$时，把$i$号和$(i + 1)$号合并，这样的复杂度变成$O((L + Q) \log{L})$。虽然询问变慢了，但是仍然可以通过。
其实分为$O(\log{L})$层的思想比较常见，例如在线维护无向图连通性的$O(\log^2{N})$算法。出题的时候大意了。
WZMZBMR在赛场的做法。
虽然AC自动机难以维护，但是后缀自动机是可以在线构造的，而且right树可以通过动态树维护，复杂度应该跟解法乙一样。
由于我出题时候的疏忽，直接rotate实际上不能强制在线。预先把串倍长，就可以把动态树省掉。
杭州的时候，我写G，提交，RE。
我：“我想造数据”
LQ拍桌：“多组！”
遂RE，发现node_count没有清零，通过。
南京的时候，我写H，提交，RE。
我：“我想造数据”
（极限数据，全正解）
NHB拍桌：“多组！”
遂RE，发现edge_count没有清零，通过。
layout: post title: "Happy new blog" date: 2014-01-06 20:50:36 +0800 comments: false categories: daily
I will never mind start a new blog.
A simple to-do list:
add google analytics-
add mathjax support$$\sqrt{a^2 + b^2}$$
果然年龄大了之后也需要抒发感想的地方呢。
今天风非常地大，但是吹在脸上慢慢是春天的气息，加上阳光灿烂，心情大好。
意外点进delayyy的博客，头像上的suzuka酱直戳萌点，所以就超掉节操地跑去勾搭了。（但是总有失败的感觉？好苦恼。
今晚又有Kill la kill的更新了，好兴混！
layout: post title: "Comming summer" date: 2014-05-02 11:18:00 +0800 comments: true categories: life
今天是假期第二天，阳光明媚。 风凉凉的，但是总让人觉得是夏天到了。
昨天晚上看到GDOI 2014的题目，不免有些庆幸生得早？
不过第4题还蛮有意思的。
早上做了LotteryTree，总觉得赶上进度指日可待。
（但是填完题解的坑就不知道是何年何月的事情了
欢迎回来。
五年的时间最后什么都没有改变，这大概是能想到的最好的结局了。
站在香港村屋的露台上，晚风凉如水。
因为今天对着不同的人讲了3次这个故事，所以决定记下来。
我暑假在Cornell U的时候，我问John：“我读过你关于平面图判定的paper，为什么现在没有类似的工作呢？“
约翰语重心长地对我说：
Things are quite different now. 在我们的时代，我们处理的都是几十个点的图，每个点图的结构都至关重要。而现在我们面对的是10^9节点的图，少数几个节点对全图的性质无关紧要。
layout: post title: "Codeforces Round #265E" date: 2014-09-08 20:52:43 +0800 comments: true categories: solution
今天带来的是Codeforces 464E.
模型非常经典。给一个$n = 10^5$个点$m = 10^5$条边的无向图，求点$s$到点$t$的最短路。特殊之处在于边的权值都是$2^{d_i}$的形式(
最短路和特殊的边权让我联想到scaling method，但是事实证明我想歪了。
考虑普通的Dijkstra算法，如果想到用一个函数式线段树来表示一个高精度数，问题就迎刃而解了。
需要实现的操作有$2$个，加法和比较。
加$2^i$时，找到$i$之后第一个0的位置$j$，并把第$i$到第$(j - 1)$位设为0，第$j$为设为1。
比较时，需要快速判断两颗函数式线段树是否完全相等，model solution使用了Hash的方法。
实际上，我们可以赋予每种函数式线段树一个标号，并记录一个表merge[x][y]表示标号$x$和$y$的线段树合并得到的线段树标号。从而可以利用标号进行判断。这个方法的本质是实现了没有冲突的Hash。
具体实现的时候，还有$2$个技巧：
-
预先建立全
0和全1的线段树，区间覆盖的时候可以直接拷贝指针，不需要进行标记下放。 -
每个叶子可以记录32个位的信息，这样线段树可以减少$5$层，时间和空间复杂度大幅降低。