A - GCD is Funny
题意：在黑板上写有$n$个数，每次删掉$a,b,c$三个数并把$d$写两遍，$d$可以是$(a,b),(a,c),(b,c)$。在$n-2$次操作后会留下两个相同的数，输出这个数的所有可能情况。
题解：给跪了。。。其实是所有大小超过$1$的子集的$gcd$的集合。。。
注意点：值域限制，说是子集当然不可能直接按子集做，而是利用值域很小这一点标记着做；gcd下降速度，两个不一样的数取$gcd$，最大也只能是大数的一半，即对数级别次就可以到$1$。
B - Square Distance
题意：给一个串$s$，长度为$n$(保证偶数)，输出一个串$t$，要满足：$t$由两个相同的串拼接而成；$s$到$t$的汉明距离恰好为$m$；$t$是所有满足条件的串中字典序最小的。$s,t$均只含小写字母，若$t$不存在输出Impossible。
题解：后半段放到前半段综合考虑，用dp可以求出前$i$个字符产生$j$个距离可不可行。因为要输出字典序最小，所以最终的贪心一定是从前往后从小往大，若是直接在这种dp上贪心，会导致最后的距离不一定是$m$。所以这里需要倒着dp，即从第$\frac{n}{2}$个到第$i$个字符产生$j$个距离可不可行。
注意点：看着很像贪心但是没有具体策略的时候一定要想一想dp！不一定只贪心或者只dp，也不一定是用贪心优化dp，像这题就是在dp得到的表上进行贪心。
C - LCIS
题意：给出$n$个数的序列$a$和$m$个数的序列$b$，问公共的上升的并且数值连续的子序列的最长长度。
题解：对$a$扫一遍得到以$x$结尾的连续值上升子序列的最长长度，同样地对$b$扫一遍，最后枚举结尾是什么数字，取两个结果的较小值更新答案。
注意点：当对子序列的限制非常强时，很有可能可以每个序列分开做，最后再合并到答案。
D - Black White Tree
题意：$n$个节点的无根树$T$，每个节点是黑色或者白色，求$W = \displaystyle\sum_{a=0}^{n}\sum_{b=0}^{n}{(a+1)(b+1)S(a,b)}$，其中$S(a,b)=1$表示存在一个子树恰好由$a$个白色节点和$b$个黑色节点构成，$S(a,b)=0$表示不存在。$T$的一个子树定义为$T$的一个子图并且是树。
题解：对于确定大小的子树，如果可以知道最少以及最多有几个黑色节点，那么答案直接两重循环加一个判断就可以算出来了。所以我们可以进行树形dp求出这个最少和最多。先规定$1$作为根，那么题意中的子树就是规定根以后的连通块，用$f[u][i],g[u][i]$分别表示以$u$为根，大小为$i$时最少和最多的黑色节点数，用$F[i],G[i]$表示连通块大小为$i$时最少和最多的黑色节点数。这个转移直接借助代码来说还更好一点。
1 | void dfs(int u,int fa) |
每个节点被访问深度次，所以最终的复杂度是$O(n^2)$。
注意点：无根树的子树等价于确定一个根以后的连通块。
F - Aaronson
题意：$x_{0}+2x_{1}+4x_{2}+…+2^{m}x_{m}=n$的解是$(x_0,x_1,x_2,…,x_m)$，$x_i \ge 0$，求$\displaystyle\sum_{i=0}^{m} x_i$的最小值，$(0 \le n,m \le 10^9)$。
题解：若$m$比较小，特殊处理一下$x_m$，剩下的以及其他的情况都是二进制表示的$1$的个数。
G - Bellovin
题意：长度为$n$的$a$序列，求一个长度也为$n$的$b$序列满足，$a$中以$a_i$结尾的$LIS$长度和$b$中以$b_i$结尾的$LIS$长度相等$(1\le i \le n)$，$b$的字典序最小。
题解：因为$b_i$最小是$1$，直接把$a$中以$a_i$结尾的$LIS$长度当作$b_i$即可。
H - Colmerauer
题意：一个矩阵的权值定义为其所含的所有鞍点的值的和，若一个点在列上是唯一最大值，在行上是唯一最小值，则其为鞍点。又在矩阵$M$上定义$S(a,b)$，表示所有大小为$a$行$b$列的子矩阵的权值和。现给出矩阵$M$，求$W = (\displaystyle\sum_{a=1}^{n}\sum_{b=1}^{m}{a \cdot b \cdot S(a,b)}) \text{ mod } 2^{32}$。
题解：很容易想到单点贡献。对于矩阵中的每一个点，我们暴力出（或者用单调栈优化一下）它能往上下左右延伸的长度，然后直接贡献即可。
注意点：左右长度的算式没有理清楚，应该写出原始的公式再进行化简。
I - Dertouzos
题意：$n$的真因子是不为$n$的因子。给出$n$和$d$，问有多少小于$n$的数的最大真因子是$d$。
题解：即$pd=m\lt n$，显然有
- $p \le \frac{n-1}{d}$；
- $p$必须为质数；【如若不然，则$p$有真因子$q$，$qd$是比$d$更大的$m$的真因子。
- $p \le c$，其中$c$为$d$的最小质因子。【如若不然，则$\frac{d}{c}\times p$是比$d$更大的$m$的真因子。
由2，我们先做一遍筛法以及前缀和。再算出1的界，最后用筛出来的质数去算3的界。
注意点：用筛出来的质数去算3的界会有$O(\sqrt{d})$的复杂度，当$d$很大($\approx 10^{9}$)时会超时，而此时1的界必然比较小，应该在超过已有的界时及时退出。
J - Eades
题意：长度为$n$的$a$序列，定义$g(l,r)$为$a_l$到$a_r$的最大值，定义$f(l,r)=\displaystyle\sum_{i=l}^{r}[a_i = g(l,r)]$。求对于所有$1\le k \le n$的$k$分别有多少对$(l,r)$满足$f(l,r)=k$。
题解：如果$a_i$要对$f$函数有贡献的话必须是这个区间内最大的，所以首先用单调栈求出往左以及往右第一个大于$a_i$的位置。那么在$L+1…R-1$中，$a_i$这个值将区间分为若干段，朴素的想法是直接枚举左端点和右端点在哪一段上然后累加到答案，但是这样还是$O(n^2)$的~~【其实处理得好能卡过~~，不过进一步可以发现具体贡献到哪一个答案其实只跟$j-i$(两个段编号的差)有关，那么把其中一个反过来就是一个卷积形式，可以套一个$fft$。
注意点：具体细节较多，想不清楚时一定要耐心&动手模拟一下。
K - LCP Array
题意：$s$是一个$1base$的字符串，记$a_i=lcp(ssuff_i,suff_{i+1})$，$(1 \le i < n)$。现给出$a$序列，问有多少只含小写字母的字符串$s$满足这个序列。
题解：若$a_i$不为$0$，那么$s_i…s_{i+a_{i}}$这些字符必须全都相同(手动模拟一下)，由此推出从后往前：$a_i$不为$0$则必须连续地增加，若不满足答案为$0$；$a_i$为$0$则将答案乘上25。
L - Shortest Path
题意：$n$个点的无向图，原来在$i$和$i+1$之间有边，现在添加3条边，所有边的权值都是$1$，每次询问$u$到$v$的最短路是多少。
题解：实际上就是改变了6个点(或者不到6个)之间的距离，直接Floyd。询问的时候直接暴力枚举穿过哪两个点。
注意点：不要忘记跟初始的距离取$min$。
M - Transform
题意：给出$n$个数，可以对整数$x$进行两种操作，
- 翻转$x$的一个bit；
- $x \leftarrow x\ xor\ a_i$ 。
每次询问把$S$变成$T$最少需要几步。
题解：两个操作都可以归结为$xor$，所以从$S$走到$T$跟从$0$走到$S\ xor\ T$是等价的。直接以$0$为起点按两种操作进行$bfs$，$O(1)$回答。
注意点：状态数trick，虽然每次有几十条边，但是最后询问的范围只有$10^5$左右，最多也就是$0$到$(2^{17}-1)$每个点都走一遍。
N - Toposort
题意：有向无环图有$n$个点$m$条边，问恰好删除$k$条边可以做到的字典序最小的拓扑序。
题解：考虑字典序最小，首先$1$号点放在第一绝对比放在第二好，那么：如果$1$号点当前的入度$d_1$小于等于$k$，直接将这$d_1$条边全部删除即可；如果大于，再测试$2$号点、$3$号点……。用优先队列保证每次取出的是最小编号的点，每条边访问一次，每个点最多入队$n$次，复杂度感觉上是$O((n+m)log{n})$。
注意点：对字典序和贪心的理解不够深刻。
O - Deletion
题意：无向图$G$有$n$个点$m$条边，每次可以删除一个边集，要求这个边集组成的导出子图的每个连通分量最多只有一个环。问最少几次可以把图$G$完全删除。
题解：对于一个连通分量，若至多一个环，那它就是一个广义的环加外向树（可以没有环或者没有树）。环加树又可以理解为每个点最多一个出度，再反推回去，若有答案为$k$，那么等价于给图$G$中的每条边定向，使得所有点的出度均不超过$k$。考虑到一条边$(u,v)$，要么在$u$是出度要么在$v$是出度，新建一个点$x_{uv}$表示原图中的这条边，那么它要么与$u$匹配要么与$v$匹配。在这个新图中，左边的点(原图的点)最多匹配$k$次，右边的点(原图的边)最多匹配$1$次，且当右边的点完全匹配时$k$是一个可行的答案，可以二分答案每次判断最大流是不是等于$m$。xg最后提到其实二分可以不要，因为右边的点到汇的容量始终是$1$，每次改改增广路啥的。【然而这种操作本菜鸡就没必要学了吧。。。
注意点：环、树、环加树的点数边数以及度数都有特殊的结论。
P - Card Game
题意：Soda 和 Beta 各有$n$张牌，两人随机抽$m$张牌，用它们的和比大小，问 Soda 能不能稳赢。
题解：取 Soda 最小的$m$张跟 Beta 最大的$m$张，它们的和比一下大小。
Q - LCS
题意：有两个排列${a_1, a_2, …, a_n}$，${b_1, b_2, …, b_n}$，要找到另一个排列${p_1, p_2, …, p_n}$，使得${a_{p_1},a_{p_2},…,a_{p_n}}$和${b_{p_1},b_{p_2},…,b_{p_n}}$的$LCS$最长，输出$LCS$长度的最大值。
题解：$b$是$a$的置换，长度为$l$的环能产生$l-1$的$LCS$。
注意点：特判环长度为1。
R - Beauty of Sequence
题意：定义魅力值为一个序列去除序列中连续重复元素(每一段只保留一个)后的序列的和。给出$n$个数的序列$a$，求$a$的所有子序列的魅力值之和。
题解：考虑单点贡献，并且出现连续相同值时只有最左边的要贡献。那么对于$a_i$，只要之前的子序列不以$a_i$结尾就可以贡献，累加答案以后更新一下以$a_i$结尾的子序列的数量即可。
注意点：不用考虑本质不同。
U - Souvenir
题意：$p$块钱可以买1个纪念品，$q$块钱可以买纪念品套装，内含$m$个纪念品，问要给$n$个人各发一个纪念品至少要多少钱。
题解：只有三种情况，只用$p$，只用$q$，用$q$直到剩下不到$m$的用$p$。
注意点：显然是可以多买的。
W - Sequence
题意：一个数列的第$n(n \ge 1)$项为$3n(n-1)+1$，给出一个数$m$，问至少几个数的和能恰好等于$m$。如，$22 = 19 + 1 + 1 + 1 = 7 + 7 + 7 + 1$。若不能，输出$-1$。
题解：联想到三角形数$a_{n}=\frac{1}{2}n(n-1)$，至多3个三角形数可以表示任意自然数。而$3n(n-1)+1=6a_{n}+1$，那么$m\equiv ans \mod 6$。特判一下$ans$等于$1$或$2$，否则就是$3\dots 8$中与$m$同余的数。
注意点：特判也需要考虑复杂度！
