近一个月来第一次赛时通过一道题。真是可喜可贺。
一开始以为与网络流相关；后来考虑 DP；结果是个贪心或者乱搞。
给定长为 $\newcommand\bigO{\operatorname{O}}n\ \ (n\leq 10^5)$ 的序列 $\langle a_i\rangle,a_i\in\{1,2,3\}$。匹配尽可能多的子序列，每个子序列均为 $\langle 1,2,3\rangle$ 或 $\langle 3,2,1\rangle$，且一个位置最多被一个子序列占用。求最大匹配数。 （更多…）
T1 的 Hack 数据提醒我，尽管时间复杂度没有变化，但所有想到剪枝和常数优化在时限不充裕的题目中仍是必要的。
T2 没有认真读题，忽略了“恰执行一次”的要求。
T3 里面没有使用自己熟悉的存边方式，时间趋紧的情况下代码实现出错。这再次告诫我应以求稳为重。
从 $(x,y)$ 跨步跳能够跳到 $(x\pm 2,y),(x,y\pm 2)$，以及 $(x+k,y+k),k=\pm 2$。可以发现 $x,y$ 奇偶性均不变。我们只需要考虑所有存在棋子的格子及其邻居。它们形成若干连通块，在这些连通块上 BFS 即可。
若采用 std::map 存储，时间复杂度为 $\newcommand\bigO{\operatorname{O}}\bigO(7n\log n)$。需要采纳“避免遍历不存在的连通块”之类的优化。 （更多…）
中规中矩的一场模拟赛。
T1 写得实在是太久了……这也是没办法的事情——如果不对转移作压缩优化就没办法过。
T2 有我喜欢的马拉车 Manacher 算法，是印象里第二次在模拟赛应用。
然后就没时间了。后两题仍然只有暴力分，但最近频繁遇到跟凸包和线性函数相关的题目，这使我发现 T3 跟它相关。在最后一点时间里实现了构建凸包的函数。代码本身没问题，但思路是错误的。
这好像是很早以前的译名了。现在它叫《莉可丽丝》。
遇见多模式串匹配，自然想到自动机上 DP。但我们发现题目中给定的两个串 sakana chinanago 在任何一个文本串中最多只能匹配其中一个，且匹配位置唯一。于是简单计数 DP 转移，记录当前二者匹配数之差与目前匹配位置即可。
一些不应用就过不了的优化：
? s c a o 还有其他字符分类讨论，保证单次转移复杂度为 $\newcommand\bigO{\operatorname{O}}\bigO(1)$。时间复杂度 $\bigO(n^2)$。 （更多…）
感冒咳嗽，头实在是太晕了，打完前两题和后两题的暴力之后跑去睡了会觉。结果考得还行。
简单的 $\newcommand{\bigO}{\operatorname{O}}\bigO(m2^k)$ DP。记录每个节点的路径数奇偶性考虑是否翻转即可。
用 std::bitset 写的暴力大家都会。不过如果你胆子大些，不判断是否为部分分数据范围直接提交（加入随机化的）暴力，将喜提 $\text{100 pts}$。
命题：现有一个由 $2n$ 个元素构成的集合，保证 $2\mid n$。有 $n+1$ 个大小恰为 $n$ 的子集 $S_1,\cdots,S_{n+1}$。则至少存在 $n/2$ 对无序对 $(i,j),i\neq j, i,j\in[1,n+1]$，使得 $|S_i\cap S_j|\geq n/2$。
证明（引自宋佳兴学长）：记元素 $p,p\in\{1,\cdots,2n\}$ 在所有子集中出现的次数为 $\newcommand{\cnt}{\operatorname{cnt}}\cnt(p)$。则显然有“所有子集两两之交的大小”
$$\sum_{i=1}^{n}\sum_{j=i+1}^{n+1}|S_i\cap S_j|=\sum_{p=1}^{2n}\binom{\cnt(p)}{2}$$
考虑计算该式最小为何。不妨先考虑 $\binom{a}{b}+\binom{n-a}{b}$ 在何时取最小值。
引理：$\binom{a}{b}+\binom{n-a}{b}, b\leq n, a\geq 0, a\leq n$ 在 $a=\lfloor n/2\rfloor$ 处取最小值。
堪堪能接受的一场。前两题一个半小时左右做完，后两题实在没什么思路，打完所有可能的暴力之后跑路了。
他们告诉我题目名称可以从上到下连起来读。
可以发现，假若同时有 $\newcommand{\bigO}{\operatorname{O}}a_i,a_{i+1}$ 和 $a_{i+1},a_{i+2}$ 都可合并，则取 $a_i, a_{i+2}$ 中任意一个合并之后，质因数集合总是变为原来的超集，另外一项仍可合并。
故而可以贪心合并所有合法的邻项，最终检查是否仅剩一项即可。注意到 $[1,700]$ 仅含 $125$ 个质因数，故可以用 std::bitset 保存每一项的质因子集合。复杂度 $O(\frac{128n}{\omega})$。赛时竟然还开了数组保存每个质因子的实际指数！ （更多…）
签到题看了半个小时；T2 没有考虑到只需要包含最优解即可，非要确定另一多余状态，只拿了部分分。
T3 只会考虑 “$x, y$ 的公共祖先中含有 $l$ 的概率”，不会高效计算“当二者的 $\operatorname{lca}$ 恰为 $l$ 时”的期望/概率与总长之和的乘积，仍然只有暴力分。
T4 无思路。
可以简单用归纳法证明，仅有所有管道中通行时间最大的会阻塞进度，是为两数据包到达终点的时间间隔。算出首个数据包到达的时间再将前者相加即可。
第一反应是类似笛卡尔树一样，在区间上依次合并区域最大值并计算贡献。$n \leq 300$ 似乎也在暗示这是一个区间 DP。
设 $f(l,r,\text{mx})$ 表示“考虑完成区间 $[l,r]$ 内所有贡献，且最大值恰好为 $\text{mx}$”的最大权值和。转移时从小到大枚举最大值 $\text{mx}=V_{i,j}$，枚举包含它的区间，尝试转移 $$f(l,r,\text{mx})\leftarrow f(l,i-1,\text{mx}’)-C_{i,j}+\text{mx}\cdot \operatorname{calc}(l,r,i)+f(i+1,r,\text{mx}”)$$，其中 $\operatorname{calc}(l,r,i)$ 计算 $\sum_{l’=l}^{i}\sum_{r’=i}^{r}Q_{l’,r’}$，可以由二维前缀和实现。稍加演算会发现，这样转移不会重复计算贡献。时间复杂度 $\operatorname{O}(\sum K_{i}N^2)$。 （更多…）
通过优化，将子集求和类相关问题的时间复杂度由朴素的 $\mathrm{O}(3^n)$ 优化到 $\mathrm{O}(n\times 2^n)$。
CodeForces Round #755 Div.2 F / Div.1 D Serious Business
此题整整困了我一天半，耗费了好几张草稿纸。实在走投无路，翻看题解，却发现正解曾经近在咫尺。有必要稍作整理。
考虑DP。
这道题与清理班次（《算法竞赛进阶指南》上的一道例题）过于相似，都是“给定一些段落$[l_p, r_p]$，选择其中一些完整覆盖$[l_0,r_0]$，求最小花费”的形式。记上述花费为$f(l_0, r_0)$。但本题与原题不一样之处在于其起点和终点是任意给定的。我的第一反应是枚举在$x_2$位置从第$2$行转到第$3$行，利用数据结构维护所有$x_1\leq x_2$，在$x_1$转移到第二行，解锁到达$x_2$的最小代价。对于各行前缀和，我们可以利用线段树或树状数组维护。同时我们也知道可以利用数据结构优化在$\mathrm{O}(n \log n)$的时间内，计算出对于一个固定的起点$l_0$，所有$f(l_0, r_0), r_0 \in [l_0, n], \exists p, r_p=r_0$的值。 （更多…）
被这玩意卡了一上午——前天CSP-S模拟的T4需要用到这类问题的转移。为什么题解TMD是错的？
即$g(i,j,k)$表示“每个位置有$i$类元素可选，且序列中必须包含指定的$j$类元素的，长度为$k$的序列的个数”。形式化地讲，我们需要统计满足以下条件的序列的个数：$\forall p \in [1,k], a_p \in S\space(|S|=i); \forall b \in T \subseteq S\space(|T|=j), \exists p \in [1,k], a_p=b$。
通过容斥原理，我们可以计算出至少有$0,1,2,\dots,j$个$T$中的元素没有被包含在序列中的序列的个数，然后乘上容斥系数累加既是答案。也即：
$$g(i,j,k)=\sum\limits_{x=0}^{j}(-1)^x\dbinom{j}{x}(i-x)^{k}$$。通俗地讲，我们在 $j$ 个元素中选择 $x$ 个，并强制使得它们不出现在序列中，其余元素任选。除去组合数的预处理时间，复杂度为$\mathrm{O}(j)$。参阅AtCoder ABC 194 F – Digits Paradise in Hexadecimal，可以使用上述计算而非DP求解（虽然DP更加简洁直观）。