0730小马拉松 题解
T358782 阶乘
数学。
测试点 \(1\sim 3\)：long long 暴力阶乘。预期 30 分。
测试点 \(4\sim 5\)：暴力试除，找出因子 \(5\) 的个数。预期 50 分。
测试点 \(6\sim 7\)：
考虑这样一个程序：while(x)x/=5,cnt+=x;
即求出有多少个数是 \(5\) 的倍数，\(25\) 的倍数，\(125\) 的倍数......加起来就是因子 \(5\) 的个数。预期 \(70\) 分。
测试点 \(8\sim 10\)：使用高精除。预期 \(100\) 分。
T358793 最大公约数
数学题。
测试点 \(1\sim 3\)：枚举两个数，求最大公约数。复杂度 \(O(N^2\log W)\)。预期 \(30\) 分。
测试点 \(4\sim 5\)：枚举值域，看有多少个数是它的倍数。复杂度 \(O(NW)\)。预期 \(50\) 分。
测试点 \(6\sim 10\)：用桶优化一下。复杂度调和级数。\(O(W\log W)\)。预期 \(100\) 分。
T358804 字符炼金术
分讨 + 差分。
测试点 \(1\sim 2\)：暴力枚举每个点的情况。复杂度 \(O(NMAB)\)。预期 \(20\) 分。
测试点 \(3\sim 10\)：
考虑将问题抽象化理解。
对于当前空位，将其相邻的所有点放在二维平面上，颜色为横坐标，形状为纵坐标。那么字符 \((a,b)\) 放在此处满足条件，当且仅当以其为中心的“十字”能够覆盖所有点。
对相邻点分类讨论：
-
一个点：以其为中心的十字。
-
颜色一样：一横条。
-
形状一样：一竖条。
-
其他：枚举可能的横纵坐标，看能否全覆盖。
最后差分记录贡献即可。复杂度 \(O(NM)\)。预期 \(100\) 分。
T358812 幸运手环
根号分治 + DP。
\(Sub1\)：手搓。复杂度 \(O(1)\)。预期 10 分。
\(Sub2\)：暴力枚举边长和点。复杂度 \(O(N^2M^2)\)。预期 \(35\) 分。
\(Sub3\)：上下两个数相加，求最大子段和。复杂度 \(O(M)\)。预期 \(50\) 分。
\(Sub4\)：枚举任意两行，中间部分还是用类似最大子段和的方法算。复杂度 \(O(N^2M)\)。预期 \(70\) 分。
\(Sub5\)：显然，\(\min(n,m)\le \sqrt{nm}\)，所以我们只需将较小的边作为行即可。复杂度 \(O((NM)^{\frac{3}{2}})\)。预期 \(100\) 分。
T358815 取数游戏
单调队列优化 DP。
\(Sub1\)：手搓。复杂度 \(O(1)\)。预期 \(20\) 分。
\(Sub2\)：
定义 \(f_{l,r}\) 表示已选区间 \([l,r]\)，接下来小 Z 能获得的最大分数。
可以根据当前是谁来进行相应的转移。
小 Z 刚选完：\(f_{l,r}=\min(f_{l_2,r_2})\)。
小 W 刚选完：\(f_{l,r}=\max(f_{l_2,r_2}+\operatorname{sum}(l_2,l-1)+\operatorname{sum}(r+1,r2))\)
特殊的，\(f_{1,n}=0\)。
复杂度 \(O(n^2\log n)\)。预期 \(65\) 分。
\(Sub3\)：
优化一下状态设计和转移。
定义 \(f_{i,j}\) 表示已选区间 \([i,i+2^j)\)，接下来小 Z 能获得的最大分数。
转移的时候我们发现，新的左端点的可行区间是在不断向右移动的。
所以考虑用单调队列优化。
小 Z 刚选完：由于要取 \(\min\)，维护以 \(f_{l,j+1}\) 为权值的递增队列。
小 W 刚选完：由于要取 \(\max\)，维护以 \(f_{l,j+1}+\operatorname{sum}(l,l+2^{j+1}-2)\) 为权值的单调递减队列。
复杂度 \(O(n\log n)\)。预期 \(100\) 分。
T359269 打怪游戏
Trie 优化 DP。
测试点 \(1\sim 10\)：
容易发现，两个人是一段一段地取，所以可以按段来 DP。
为了方便操作，我们先假设所有怪物都被同一个人干掉，即长度之和减去相邻的 LCP。
现在考虑将区间断开，定义 \(f_i\) 为考虑到第 \(i\) 个怪兽，断开 \((i-1,i)\) 后最小的增量。
显然，相邻两个断点会形成一个新的区间，如图。
减掉白黑的 LCP，加上白白的 LCP。
所以转移方程为：\(f_i=\min(f_j+\operatorname{LCP}(i,i-1)-\operatorname{LCP}(j-1,i))\)。
初始化为 \(f_i=\operatorname{LCP}(i-1,i)\)。
最后加上最初的答案即可。复杂度 \(O(n^2L)\)。预期 \(50\) 分。
测试点 \(11\sim 20\)：
注意到 \(L\le 20\)，所以考虑将贡献拆开，放到 Trie 树上。
每次转移时，只需要从当前怪物末节点往上跳，对每种 LCP 求最小值。
所以对于 Trie 树上每个节点，维护其子树内最小的贡献，更新时把到根节点路径上的都取 \(\min\) 即可。
复杂度 \(O(nL)\)。预期 \(100\) 分。
欢迎各位来补充！