LOJ #10132 异象石
题目简述：支持对树上一点集删单点和加单点的操作，询问点集组成的虚树的边权之和（虚树边权为原树上两点间距离）。
做法：考虑给定点集答案的求法，将其中的点按dfs序排序，使dfs序从小到大的点依次相邻，同时使dfs序最大和最小的相邻，构成一个环。环上相邻点的距离就是答案。再考虑修改时的贡献，例如增加一个点，则把点集这个点的前驱和后继的距离从答案中减去，在将这个点到前驱的距离，这个点到后继的距离加回来。
参考题解：Link
LOJ #10110 太鼓达人
这是一道欧拉回路的题目。考虑将题目中给出的传感器表示变形。
传感器是长度为K的二进制串。记传感器 \(A[a_1a_2...a_k]\) ，则右边相邻的传感器 \(B[a_2a_3...a_ka_{k+1}]\)。将A->B的关系用边表示：\(U[a_1a_2...a_{k-1}]\) 通过边 \(a_{k}\) 到达 \(V[a_2a_3...a_{k}]\)。
发现我们可以用一条边表示一个传感器，即起点上的二进制串和边上的二进制数码（0或1）拼起来。当传感器长度为K时，有点 \(2^{k-1}\) 个，边 \(2^{k}\) 条。容易发现这是一欧拉图。故所有的边可以走到。建出图从0为起点，先走0边，进行dfs。
LOJ #10061 最短母串
这样一种最短母串无法快速设计出来，故考虑搜索。
我们以模式串建立AC自动机，并从起点开始广搜。若搜索到某一节点s上，状态为字符串 \(S\)，则经过一条边 \(K\)，状态变为 \(S+K\)。第一个包含所有模式串的状态，即是最小母串。我们考虑一状态的包含模式串数。一个新状态包含的模式串有转移之前旧状态包含的模式串和新转移到的点包含的模式串。题目中模式串的数量不超过12，故包含模式串的信息可以状压表示，并在转移过程中用新加进来的点更新。
对于每一种情况（在AC自动机的节点 \(u\)，包含模式串的状压为 \(s\)）只会入对一次。故时间复杂度为 \(2^n*sum|S|\)。
LOJ #10062 病毒
显然，先将模式串建出AC自动机。我们可以把构造串的过程视作一个点在AC自动机上转移，将沿途的边代表的字符按顺序拼接。
构造串中不能出现任何一个模式串，说明不能经过后缀中存在end标记的节点。同时我们需要串可以无限长，则点需要最终能够在一个环上循环转移。故我们需要在不能经过的点被剔除后，找到一个从起点0出发，终止于一个环的路线，通过dfs实现。
LOJ #10174 动物园
状压DP趣味题。首先需要把握如何统计贡献。对于每一个小孩，其可视区间都为5，所以我们可以将孩子的贡献统一放在区间的端点上。\(n\) 个端点对应 \(n\) 个区间。设第 \(i\) 个区间为 \([i,i+4]\)，\(dp[i][s]\) 表示前 \(i\) 个区间，第 \(i\) 个区间状态为 \(s\)（状压）的贡献和的最大值。
转移方程：\(f[i][s]=max(f[i-1][(s\&15)<<1],f[i-1][(s\&15)<<1|1])+num(i,s)\)。
其中 \(num(i,s)\) 是第i个区间取状态s的贡献值，可以预处理；而 \((s\&15)<<1\)，\((s\&15)<<1|1]\) 则巧妙联系了相邻区间的关系，及 \(i-1\) 区间的状态后四位和 \(i\) 区间的前四位相同。
最后需要关注，对于呈环形的 \(n\) 个区间，第 \(n\) 个区间和第1个区间满足相邻区间的关系。
LOJ #10183 股票交易
单调队列辅助dp，困难在讨论和推dp方程上。
题目中 \(T\) 和 \(MAXP\) 的范围在 \([1,2000]\)，允许我们开二维的数组，设计状态 \(f_{i, j}\) 表示第 \(i\) 天后，持有 \(j\) 股股票，所赚得的最大利润。这里的利润不包括股票在当天卖出的价值。
分类讨论：
1.在当天凭空买进。
\(f_{i, j}=-AP*j (0\le j\le AS)\)
2.从前一天继承下来，如果继承，则赚的钱同前一天保持不变。
\(f_{i, j}=max(f_{i, j}, f_{i-1, j}) (0\le j\le MAXP)\)
3.从W天之前的某一天买入若干股转移而来。
\(f_{i, j}=max_{k=1}^{min(j, AS)}(f_{i, j}, f_{i-W-1, j-k}-AP*k)\)
4.从W天之前的某一天卖出若干股转移而来。
\(f_{i, j}=max_{k=1}^{BS}(f_{i, j}, f_{i-W-1, j+k}+BP*k)\)
在第3，4条时，我们只从第 \(i-W-1\) 天转移而来，在实际上，我们可以从第 \(i-W-1\) 天和之前的任意一天转移而来。但由于第2条对前面优秀状态的继承，\(f_{i, j}\) 其实是前 \(i\) 天持有 \(j\) 股赚钱最多的一天的赚的钱数。故3，4条的正确性可以保证。然后发现第3，4条中对于相同的 \(i\)，任意 \(j\) 的转移区间长度是固定的，故使用单调队列优化。
参考题解：Link
LOJ # 10067 构造完全图
首先有一个定理，可参看oi-wiki 最小生成树，即若不在最小生成树上的一条边可替代最小生成树上一条边权相同的边，则最小生成树不唯一。
对于任意一点对\((u, v)\)，如果在MST上它们直接连边，那么在构造的完全图上也要保留连边，并且边权不变。若它们没有直接连边，则在MST上会有一条 \(u\) 到 \(v\) 的简单路径，记路径上边权最大的边为 \(E\)，我们在完全图上构造的 \((u, v)\) 的边权为 \(W\)，若 \(W<W_E\)，则在给定的MST上断开 \(E\) 连接的两点，连接 \(u\)，\(v\) 两点，构造出的生成树边权和更小，不合题意；若 \(W=W_E\)，则用 \((u, v)\) 替代 \(W_E\)，最小生成树不唯一。故 \(W>W_E\)。题目要求完全图的边权和尽量小，故 \(W\) 取 \(W_E+1\) 最优。
枚举点对，借助ST表计算路径上的最大边权，时间复杂度为 \(O(n^2logn)\)，难以接受。
考虑模拟Kruskal的过程，起初 \(n\) 个点没有连边，将MST中的边按边权从小到大排序后顺序添加。加入边 \((u, v)\) 其实是将 \(u\) 所属的连通块 \(S_u\)，和 \(v\) 所属的联通块 \(S_v\) 合并成一整个连通块 \(S\) 的过程。在 \(S_u\) 和 \(S_v\) 中的边，边权均小于 \(W_{(u, v)}\)，故任一点对 \((x_1, x_2)\)，满足\(x_1 \in S_u,x_2 \in S_v,(x_1, x_2) \neq (u, v)\)，其边权应赋为 \(W_{(u, v)}+1\)。我们用并查集维护，顺便记录连通块的大小，在每次加边时更新答案即可。
LOJ # 10069 Tree
首先膜拜uoj群里的大佬。要求有 \(need\) 条白边，我们考虑将白边边权都加上一个 \(delta\)，并二分 \(delta\)。\(delta\) 取 \(mid\)时，求出最小生成树，记录白边的数量 \(x\)。若 \(x<need\)，证明 \(delta\) 偏高，若 \(x>need\)，证明 \(delta\) 偏低。我们于是可以根据 \(x\) 和 \(need\) 的关系更新 \(l\) 和 \(r\)。
细节：\(kruskal\) 中给边排序时，规定相同权值的边，白边排在前(边权相同的边，白边尽量多选)。在二分的时候，这是可能不会有恰好 \(x=need\) 的情况了(即 \(x\) 不是 \(<need\) 就是 \(>need\))，我们需要在 \(x>=need\) 时更新答案。
LOJ # 10202 樱花
\(\frac 1x+\frac 1y=\frac1{n!}\)
\(\frac {x+y}{xy}=\frac1{n!}\)
\((x+y)(n!)=xy\)
\(xy-(x+y)(n!)=0\)
\((n!)^2-(x+y)(n!)+xy=(n!)^2\)
\((x-n!)(y-n!)=(n!)^2\)
令 \(a=(x-n!),b=(y-n!)\)。对于任意一组 \((a, b)\)，对应唯一一组\((x, y)=(n!+a,n!+b)\)。
问题于是变成了统计 \((a, b)\) 的数量。
设有质因数分解 \(\displaystyle n!=\prod_{i=1}^mp_i^{c_i}\)。
则 \(\displaystyle c_i=\sum_{j=1}^{p_i^j\le n} \frac n{p_i^j},(n!)^2=\prod_{i=1}^mp_i^{2c_i}\)。
故根据乘法原理，答案为 \(\displaystyle \prod_{i=1}^{m}(2c_i+1)\)。
LOJ # 6223 汽车加油行驶
普通的最短路难以表达剩余油量，且油量的范围很小，故采用分成图最短路。设第 \(i\) 层代表剩余油量为 \(i\)。将第 \(i(0<i \le k)\) 层的某一点连向代表少一格油的上下左右的点（上和左边权为 \(B\)，下和右边权为 \(0\)），但如果这一点有油库则不连(因为必须加油)。同时，对于第 \(i(0 \le i <k)\) 层的某一点，连向第 \(k\) 层的同一个点，表示加油，若其本来有油库，边权为 \(A\)，否则为 \(A+C\)。
需要考虑一些建模细节。对于一个没有油库的点，若进行增设油库，不影响其正常连上下左右的边，即不用考虑增设油库后再次到达必须加油的情况，因为再次加油和第一次加油情况相同，而积累的代价只会更多，必然是不优的情况，由于这种建模漏洞导致的非法情况必然不优，不会影响最终答案。
LOJ # 10081 道路与航线
尝试后会发现，使用spfa会有两个测试点无法通过。
发现若将题目给定的双向边（即道路）连接的联通块缩成点后，单向边（即航线）与连通块缩成的点形成一个DAG。从 \(s\) 所在的联通块出发，可以到达的连通块内的点是有答案的，进行拓扑排序（按照拓扑顺序对每个连通块内的点进行dijkstra求最短路）即可，而不可到达的联通块内的点没有答案。
其实有spfa的优化可以通过此题，在loj上的最短提交统计上可以看到。
LOJ # 10093 网络协议
首先对图用Tarjan缩点。记缩完点的图为 \(G\)。
第一问的答案即图 \(G\) 中入度为 \(0\) 的点。
对于第二问，我们在图 \(G\) 中入度和出度为 \(0\) 的点之间连边，因为任意一中间的点都可以通过一条从入度为 \(0\) 的点到出度为 \(0\) 的点的路径遍历到。故我们可以将 \(G\) 转换成由入度为 \(0\) 的点，出度为 \(0\) 的点，和一些边组成的二分图。连边的规则是，入度为 \(0\) 的点与能到达的出度为 \(0\) 的点连边。现在需要添加最少的边使其变成一个强连通图。
记入度为 \(0\) 的点为 \(S\)，出度为 \(0\) 的点为\(T\)。对其二分图进行最大匹配，得到 \(k\) 对匹配的点。我们这样加边：对于相邻两对匹配的点 \((S_i,T_i)\) 和 \((S_{i+1},T_{i+1})\)，在 \(T_i\) 和 \(S_{i+1}\) 之间连边，最后在 \(T_k\) 和 \(S_1\) 之间连边，于是匹配上的点形成一个强连通分量，剩下的是未匹配上的点。而这种点，若属于 \(S\)，则其所对应的 \(T\) 点都被匹配了，即都属于强连通分量里了，再加一条边，就能将其包含进去，若属于 \(T\) 同理。
这是示例。黑色边组成的二分图，红边为匹配，绿色边为对匹配的加边，蓝色边是对没匹配成功的点的处理。
最后对于每个散点（在原二分图上没有任何连边的点），只需要多加一条边插在任意一条其他附加边的中间即可。若都是散点，只需要把它们全部串起来即可。至此，可以得出结论，答案是出度为 \(0\) 和入度为 \(0\) 的点的个数的较大值。
LOJ # 10078 新年好
兔年贺岁题，和今年CSP S的T1有点像。以5个点为起点依次进行dijkstra，可以求出其中任意两点之间的最短距离。将5个点进行全排列枚举拜年顺序，取最优值即可。
LOJ # 10019 生日蛋糕
采用dfs剪枝算法。
从下层向上搜，有函数 \(dfs(dep, v, s)\)，代表当前枚举第 \(dep\) 层（从下往上枚举，即 \(m,m-1,m-2..\)），已有体积 \(v\)，表面积 \(s\)。记录数组 \(r[],h[]\)，表示当前状态被搜索出来的 \(dep-1\) 层的圆柱半径和高度。
1.精确\(r_{dep}\) 和 \(h_{dep}\) 的范围。
\(dep \le r_{dep} \le min(\sqrt{n-v}, r_{dep+1})\)
\(dep \le h_{dep} \le min(\frac{n-v}{r^2}, h_{dep+1})\)
2.可行性剪枝。
记上 \(i\) 层的最小体积前缀和为 \(mnv[i]\)。枚举 \(m\) 到 \(dep\) 层总体积为 \(v\) 时，若 \(v+mnv[dep=1]>n\)，则当前方案不可行。
3.最优性剪枝。
记上 \(i\) 层的最小测表面积前缀和为 \(mns[i]\)，当前最优答案为 \(ans\)。枚举 \(m\) 到 \(dep\) 层总表面积（包括上表面积）为 \(s\) 时，若 \(s+mns[dep=1]>ans\)，则当前方案不优。
4.最优性剪枝2。
枚举 \(m\) 到 \(dep\) 层总体积为 \(v\)，总表面积为 \(s\)，当前最优答案为 \(ans\)。剩下 \(dep-1\) 层的总表面积可表示为
\(\displaystyle \sum_{i=1}^{dep-1}2r_ih_i=\displaystyle \frac {2\sum_{i=1}^{dep-1}r_ir_{dep}h_i}{r_{dep}} \ge \frac{2\sum_{i=1}^{dep-1}r_i^2h_i}{r_{dep}}=\frac{2(n-v)}{r_{dep}}\)。
若 \(s+\frac{2(n-v)}{r_{dep}}>ans\)，则当前方案不优。
5.枚举顺序的改变。
枚举半径和高度时从大到小枚举。
P1363 幻象迷宫
将原图中联通的点之间建边；\((x, 1)\) 与 \((x, m)(1 \le x \le n)\) 之间建边，\((1, y)\) 与 \((n, y)(1 \le y \le m)\) 之间建边（即模拟穿越到另一张地图）。若从 \(S\) 出发可搜索到环，则有两种情况，要么可以拓展的地图上无限走下去，要么在拓展的地图上被困住了环里。但若无法搜到环，则肯定无法无限走下去。
可以发现搜到环时，若被困住，则环上左右的穿越次数是相等的，上下的穿越次数也是相等的；而若可以无限走，环上在上下穿越和左右穿越必然有至少有一者的两种穿越次数不同。合适的建模后，通过spfa判断负环。