【VP 记录】ABC258

KSCD_ · 2024-06-11 22:11:26 · 个人记录

记录

D 前边切得挺顺的，E 模拟二分调整场，F 模拟赛后调半天，GH 倒是比较板，~~虽然我看了也不一定能做出来就是了~~。

判断基本题，略过不表。

枚举位置和方向，模拟即可。

发现若把整个段看成环，每操作一次都会使序列开头的编号 -1，记录总共操作次数，取模得到目前的 x 在原序列的位置即可。

显然最优方式一定是每关只打一遍直到解锁 x，之后重复打 x 直到满足次数要求。因此枚举 x，计算前缀 a_i+b_i 的和再加上 b_i 乘上剩余次数，更新最小值即可。

首先发现每次取到的土豆都是一个连续段，所以先预处理出土豆重量的前缀和 s_i。这时会发现若 x\ge s_n，那么每次不管从哪开始取都会先把 n 个土豆全取一遍，所以可以把这部分单独拿出来，取模使得 x<s_n

再发现从同一个 i 开始取，每次都会取到固定的 x_i 个土豆，所以用二分计算出从 i 取到的土豆个数 x_i。接着发现最多 n+1 次取后就一定会出现循环节，所以找到这个循环节，便可以实现 O(1) 查询，要注意还要把 s_n 的整数倍这一部分加到答案中。

结论显然，要么直接走，要么从四个方向中选择一个走到主干道上，再沿主干道走到终点周围的某个方向，再走到终点，共 16 种方案。这里关键在于处理走的路线长度，考虑走到主干道上后可能两点在同一行或列的主干道块上，就不能使用差的绝对值作为距离，此时还要分讨两点同时从哪边走，总之比较麻烦。

很显然可以枚举 a_{i,j}=1 的 i,j，统计 a_{i,k}=1 且 a_{k,j}=1 的 k 个数，用 bitset 优化，时间复杂度 O(\frac{n^3}{w})

考虑朴素的转移，设 f_i 为总和为 i 的划分方案，则 f_i=\sum_{j=2-i\mod2}^{i-2}，这里设 g_i=\sum_{j=2-i\mod2}^{i}，转移就变成了 f_i=g_{i-2}，若遇到被限制的数字直接取 f_{a_i}=0 即可，时间复杂度 O(S)

发现 S 范围比较大，考虑矩阵优化，把 f_i,s_{i-1},s_{i-2} 放入矩阵中，按照 a_i 把整个过程分成 n+1 段进行转移，每次转完以后把 f_{a_i} 赋为 0 再转下一段即可，时间复杂度 O(n\log S)