「题集」精致的袖珍题目-2022 年度
「LG P1393」Mivik 的标题
题目链接：洛谷。
设 \(L=|S|\)，设 \(s\) 为所谓名字的字符串。
前半部分算是非常套路。设 \(f_k\) 表示随机生成一个长度为 \(k\) 的字符串后，它的一个后缀为 \(s\)，且 \(s\) 为第一次出现的概率。
不难发现答案就是 \(\sum_{k=1}^{n}f_k\)。这个状态的转移也是套路的容斥，也就是去容斥“第一次出现”。我们首先要保证没有 \(s\) 的结尾位置落在 \([1,k-L]\) 之间，那么此时任意组合的概率就是 \((1-\sum_{j=1}^{k-L}f_j)\times m^{-L}\)。
接着对于结尾在 \((k-L,k)\) 的 \(s\) 进行容斥，对于每一种不合法的情况，我们在第一次重复出现 \(s\) 的位置那里容斥掉它。前面已经保证了在 \(k-L\) 之前不会有 \(s\) 结尾，因此之前的贡献可以用 \(f\) 计算。假设相交的长度为 \(l\)，则贡献应当为 \(-f_{k-L+l}\times m^{-L+l}\)，并且还需要满足 \(s[1:l]\) 是 \(s\) 的一个 Border。
现在其实已经可以将问题写成多项式形式并使用半在线卷积计算答案了。不过，我们可以将 Border 划分为 \(O(\log L)\) 个等差数列，这样每个等差数列中的 \(-f_{k-L+l}\times m^{-L+l}\) 可以直接前缀和维护，最终只需要维护 \(O(\log L)\) 组前缀和即可优化转移。
小结：
- 注意这类问题的通用 DP 形式；
- 注意使用等差性质优化转移的思想；
「LOJ569」Misaka Network 与测试
题目链接：LOJ。
就那么一个点要说的：我们总是优先选最小的满足要求的矩形。这个原则很容易推断出“单独选 2 格子”，但是很容易忘记这可以往后退一步——选完所有 2 之后，如果 1 和 3 相邻，那么就可以直接选走。按照这种方法选完之后就不可能剩下更多的满足要求的矩形了，因此可以直接跑二分图匹配。
小结：思考要足够深，想的时候稍微多想那么一步嘛。
「ARC103B」Robot Arms
题目链接：洛谷，AT。
首先思考无解的情况：不妨设我们对于 \(S\) 之中的操作，将 \(d\) 的权值赋成了 \(-1\)。由于 \(x+y=\sum_i(-1)^{[i\in S]}d_i=\sum_id_i-2\sum_{j\in S}d_j\)，所以所有 \(x+y\) 的奇偶性必须相同我们才可以构造出来。相应地，我们尝试在其它情况下构造出解。
这个问题，稍微摆弄一下就会觉得有一点比较奇怪：明明是上下左右四个方向移动，为什么一次操作对于某一维来说 +1,-1,0 有三种系数？这其实还是系数之间不是独立分配的原因。我们让系数独立开来，也就是每一维上要么是 +1，要么是 -1。这个可以直接通过将坐标轴旋转 \(45^\circ\) 并缩放达成。
各维独立之后，整个问题就变得容易许多。类似于无解情况的构造方法，这个问题本质上就是凑数的问题，直接按照二进制配每一位即可。此外还有一点点化归想法：\((x+y)\bmod 2=1\) 的情况比 \((x+y)\bmod 2=0\) 的情况，我们于是加入一个长度为 1 的机械臂来调整即可。
小结：熟悉平面上常见的空间变换方式，同时多尝试一下独立变量。