炼石计划 9 月 29 日 NOIP 模拟赛 #5【补题】 - 比赛 - 梦熊联盟 (mna.wang)
复盘
T1 有 80 的暴力。想了一会正解但不会做于是放弃了。
T2。怎么这么像双栈排序？操作 3 是什么鬼？\(n \le 5\) 爆搜不会打？不管了先跳了。
T3。一眼蒙德里安的梦想+矩阵加速。复杂度未知，说不定是正解，不是也有 65 分。先写。
写+调+卡常 2h，过了大样例！此时我以为大样例就是极限数据，我以为我过了。实际上大样例 \(len = 1000\)，最后一档分 \(len = 3000\)。
T4 好像有好多部分分。但最终只拿了爆搜的 \(15\)。
然后打了 T2 的特殊性质。
预期 \(80+20+100+15=215\)，实际 \(0+0+65+0=65\)。
总结
不足：
- 挂分太多；
- 对大样例过于信任；
知识点
- T1：数学
- T3：状压 DP，矩阵快速幂。
题解
A. 公约数神庙
显然可以暴力建图。复杂度 \(\mathcal O(n^2)\)。
我们考虑这张图的构成。由于 \(1000\) 内的质数只有 \(148\) 个，于是我们枚举质数 \(p\)，将 \(a\) 中所有能被 \(p\) 整除的数取出来，从左往右练成一条链。那么这 \(148\) 条链的传递闭包与上面的图完全相同。
对于一条链 \((i_1,i_2,\dots,i_k)\) 而言，如果我们达到了某个 \(i_j\)，那么 \(i_{j+1\dots k}\) 显然都可以到达。也就是说，我们并不关心我到了链上的哪个位置，而只需要关注哪个后缀是我将来能跳到的。
考虑设 \(f(i, j)\) 表示从 \(i\) 开始跳，最小能跳到第 \(j\) 跳链的哪个位置。
考虑如何处理查询 \(x, y\)。注意到 \(2 \times 3 \times 5 \times 7 \times 11 > 1000\)，也即 \(1000\) 内的数至多只有 \(4\) 个质因子，也即一个数至多同时属于 \(4\) 条链。那么如果我们想到达 \(y\)，我们可以到达 \(y\) 所在的任意一条链 \(p\)，即 \(f(x, p)\)。如果 \(f(x, p) \le y\) 那么合法。
考虑如何预处理所有 \(f(i, j)\)。枚举 \(i\) 的出边即可。
\[f(i, j) = \begin{cases} i & j \mid i \\ \min_{i \to k} f(k, j) & j \not \mid i \end{cases} \]其中 \(i \to k\) 表示一条 \(i\) 的出边，显然最多 \(4\) 条。
C. 城堡考古
显然蒙德里安的梦想。加上最朴素的矩阵快速幂优化后复杂度能做到 \(\mathcal O(\log r \times m^6)\)。
考虑优化矩阵大小。注意到对于压缩后的状态，从第一列的 \(0\) 开始搜索，最多只会访问到 \(20\) 个不同的状态，优于刚才的 \(64\)。所以矩阵大小可以改为 \(21 \times 21\)，可过。
D. 生命之树
设 \(f(u, i)\) 表示 \(u\) 子树的答案，且 \(u\) 是通过 \(i\) 点亮的。注意点亮 \(u\) 的可能不止一个点，这里 \(i\) 是其中任意一个。
考虑转移。首先如果 \(dis(u, i) > d(u)\) 则 \(f(u, i) \gets +\infty\)，否则初始化 \(f(u, i) \gets c_i\)。
考虑枚举 \(u\) 的儿子 \(v\)。考虑 \(v\) 的子树对 \(f(u, i)\) 的贡献。
若 \(v\) 这个点也是通过 \(i\) 点亮的，那么 \(f(v, i) - c_i \to f(u, i)\)。这里 \(-c_i\) 的原因是 \(i\) 的贡献分别在 \(u, v\) 都计算了一次。
否则，若 \(v\) 不是通过 \(i\) 点亮的，那么 \(\min_{j \in [1, n]} f(v, j) \to f(u, i)\)。边转移边维护 \(g(v) = \min_{j\in [1, n]} f(v,j)\) 即可做到 \(\mathcal O(1)\) 转移。
总复杂度 \(\mathcal O(n^2)\)。
标签：大样,复杂度,矩阵,times,mathcal,1000,模拟,10.16 From： https://www.cnblogs.com/2huk/p/18470607