做题记录 #2：The 2nd Universal Cup. Stage 2: SPb
:::align{center}
\color{Black}\textsf{The 2nd Universal Cup. Stage 2: SPb}
:::
:::align{center}
\color{Green}\textsf{\textbf{[A] Mixed Messages}}
:::
- 标签：黄，DP，贪心。
- 解法：设状态
f_{i,j} 表示考虑了前i 个字符，匹配到字符串\texttt{spbsu} 的第j 个字符时需要的最小交换操作次数，直接进行 DP，时间复杂度O(n) 。
:::align{center}
\color{Green}\textsf{\textbf{[B] I Flipped The Calendar...}}
:::
- 标签：橙，模拟。
- 解法：简单模拟题。求出一年的第一天是星期几，之后直接不断加月份天数计算答案。
:::align{center}
\color{Green}\textsf{\textbf{[C] Many Many Cycles}}
:::
- 标签：紫，数论，图论。
- 解法：求出图的任意一棵生成树，有重要结论：只需要求出包含最多
2 条非树边的环的环长\gcd 。使用 dfs 求生成树，先处理包含1 条非树边的情况，接下来枚举一条非树边分讨另一条非树边的位置即可。令n,m 同阶，时间复杂度O(n^2) 。
:::align{center}
\color{Green}\textsf{\textbf{[D] Bishops}}
:::
- 标签：蓝，构造，数学。
- 解法：对于
n,m 的奇偶性分类讨论，求出答案上界，之后考虑构造取到上界。更多细节请参照本人题解。
:::align{center}
\color{Green}\textsf{\textbf{[E] Fischer's Chess Guessing Game}}
:::
- 标签：紫，交互，搜索，贪心。
- 解法：典型的搜决策树题。首先搜出合法状态，发现只有
960 种，这启发我们直接硬做。每次贪心地选一个串询问，满足在最坏情况下剩下的可能状态最少，跑一遍搜索发现决策树深度为6 ，于是可以通过。
:::align{center}
\color{Gray}\textsf{\textbf{[F] Forward-Capturing Pawns}}
:::
待更新。
:::align{center}
\color{Green}\textsf{\textbf{[G] Graph Cuts}}
:::
- 标签：蓝，根号分治，bitset。
- 解法：考虑直接对于每个点维护一个
bitset表示它的连边编号集合，修改时直接把它的贡献\mathrm{xor} 到全局贡献上，查询时_Find_first()即可。但是注意到这样子会爆空间，于是使用根号分治；设定阈值B ，对于连边数量\le B 的使用basic_string存边，修改时暴力遍历，其他情况使用bitset，时间复杂度O\left(n\sqrt{n}+\frac{n^2}{w}\right) ，空间复杂度O\left(\frac{n\sqrt{n}}{w}\right) 。
:::align{center}
\color{Green}\textsf{\textbf{[H] Very Sparse Table}}
:::
- 标签：蓝，分块。
- 解法：把图论问题转换成区间询问，相当于维护一个类似不交 ST 表的东西，只是单次询问支持
2 次信息合并，预处理的信息数量不大于6n 。使用分块，预处理块内前后缀和，和所有整块区间的答案，这样就能解决l,r 不在同一块的询问。对于l,r 在同一块的情况，对于块内继续递归做同样的分块……最后预处理的信息数量在n\le 2^{16} 时不会超过6n 。
:::align{center}
\color{Green}\textsf{\textbf{[I] Password}}
:::
- 标签：红，数学。
- 解法：第二问答案显然为
n 。第一问对于n 的奇偶性分类讨论即可。
:::align{center}
\color{Green}\textsf{\textbf{[J] Transport Pluses}}
:::
- 标签：黄，分类讨论。
- 解法：注意到传送器最多使用
2 次就可以到达任何被传送器覆盖的位置。于是对于使用0,1,2 次传送器分类讨论，最终取一个最小值。时间复杂度O(n^2) 。
:::align{center}
\color{Green}\textsf{\textbf{[K] Poor Students}}
:::
- 标签：紫，模拟费用流。
- 解法：如果抛开数据范围不看，这就是一个最小费用最大流的模板题。但是这题其中左部的点数特别大（
n\le 5\times 10^5 ），而右部特别小（k\le 10 ），暗示使用复杂度与k 强相关的做法。考虑费用流求解的本质，可以转换为每次加入一个左部点，求出一条最短增广路s\to l_0\to r_0\to l_1\to r_1\to\cdots\to l_m\to r_m\to t ，相当于进行若干次（\le 10 次）学生的调整，每次调整选择代价最小的。两个集合之间代价最小的调整方案可以用set维护，每次跑 SPFA 求最短路，时间复杂度O(nk^3+nk^2\log n) 。
:::align{center}
\color{Green}\textsf{\textbf{[L] "Memo" Game With a Hint}}
:::
待更新。
:::align{center}
\color{Gray}\textsf{\textbf{[M] Hardcore String Counting}}
:::
待更新。