CSP-S 模拟赛 29
T1
- \(n\le 18\) 显然是状压 dp。
- 考虑设状态 \(dp_{i,j}\) 表示状态为 \(i\)，最终的 \(a\) 为 \(j\) 时的最大代价及方案数。转移是简单的。
- 优化是观察到最终的 \(a\in(\max a_i,\max a_i+1)\)。那么这一维便可以用 \(0/1\) 来设。 于是时间复杂度 \(O(2^nn)\).
T2
-
对于网格图上统计问题，常见的想法是扫描线或者四个方向前缀和。
-
simple 的想法是从每个点向四个方向做前缀积，暴力乘上逆元来统计答案。然而我们发现 \(M\) 不一定是质数，也就是说逆元不一定存在。
-
考虑到只有 \(2000\) 个卫星，那么容易想到离散化。于是我们离散化每一个卫星，维护到四个方向的前缀和，于是我们发现这样的维护是不需要逆元的，并且事实上被分割成了一个个的矩形。
-
那么对于询问的每一个点，我们暴力计算它到所在矩形端点的距离计入答案即可。
T3
- \(O(n^2)\) 的暴力 Hash 是显然的。
- 考虑优化。考虑对于两个串 \(a,b\)，长度分别为 \(p,q\)，那么 Hash 比对的时间为 \(O(\min(p,q))\)。
- 得到部分分的启示，我们考虑预处理一部分东西。那么这个东西就很像根号分治。
- 具体地，对于 \(\min(p,q)\ge \sqrt n\)，我们预处理所有这样的二元字符串组 \((a,b)\)，那么这样的字符串组会有 \(n\) 个，复杂度最劣显然是长度全取到 \(\sqrt n\)，复杂度为 \(O(n\sqrt n)\)，对于 \(\min(p,q)\le \sqrt n\)，直接暴力比对，复杂度 \(O(q\sqrt n)\)，于是总复杂度 \(O((n+q)\sqrt n)\)，能过。
T4
- 抽象。
- 考虑转化所求答案：求出对于一个节点 \(i\)，能够连到的离他最近的点编号与他的差。如果这个值是 \(p\)，那么表明连边是以 \(p\) 为周期进行的，于是答案就是 \(p\)。
- 我们猜想在一定情况下 \(\operatorname{ans}=\gcd(S)\)。显然只有当每个点 \(i=j+s_k\) 或 \(i=j-s_k\) 时成立。
- 对于 \(s_i\le \dfrac{n}{2}\)，无论 \(i\) 在何处均有对应的 \(j\)。于是对于 \(s_i\le\dfrac{n}{2}\)，当前答案 \(d=\gcd(s_i)\)。
- 对于全部 \(s_i>\dfrac{n}{2}\) 的情况，这些节点不会被任何点连到，于是考虑删去他们，同时改变 \(n\) 和 \(s\) 的取值。
- 对于 \(s_i>\dfrac{n}{2},d+s_i\le n\) 的，它仍然可以扩展到，因此新的 \(d'=\gcd(d,s_i)\)。
- 对于 \(s_i>\dfrac{n}{2},d+s_i>n\) 的，能跳的显然是前面的前 \(d\) 和后 \(n\bmod d\) 个点，更新 \(n\) 和 \(s\)，并递归。
- 时间复杂度 \(O(m\log^2n)\)。