本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-11 22:11:26

记录

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

题解

A - When?

判断基本题，略过不表。

B - Number Box

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

C - Rotation

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

D - Trophy

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

E - Packing Potatoes

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

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

F - Main Street

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

G - Triangle

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

Ex - Odd Steps

考虑朴素的转移，设 $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)$