# T1

注意到对每一个数进行一个单位的操作相当于给每一个数减 1。所以答案具有单调性，可以二分目标数。

问题变为判断是否能使所有数变为这个目标数。

考虑对于一个大于目标的数，不对它进行操作是不可能达到目标的，因为前面的数的操作只会增加它。而且对它操作时，如果不把它减少到不大于目标，我们就仍然需要继续操作，所以每一次操作必须减少到达标或小于标准。

若这个数和标准的差值是偶数就直接调整至达标即可；若是奇数则减至比标准小 1。特判标准为 0 且当前数为奇数的情况，此时需要把这个数变为 1。

这里需要一个特判：若这个数 $< 2$，那么无法进行操作。

重复上面这个过程直到无法继续操作即可，由于每次被操作数都减半，所以一圈的复杂度近似 $O(\log V)$，其中 $V$ 是被操作数的最大值。





# T2

找到最大元素，递归地求解其左右子数组的问题。对于较小子数组中的每个元素，利用前7位和后7位的折半搜索（meet-in-the-middle），统计较大子数组中满足 AND 条件的元素个数——例如，对所有 $x$，统计那些是 $x$ 的子掩码且后7位与 $x$ 相同的元素。为了加速，可以通过累加较大子数组中已计算出的数量来统计。





# T3

首先考虑什么样的路径是最优路径。我们先不妨假设我们一直向右走，再一直向下走，即 $(1,1) \to (1,2) \to \cdots \to (1,m) \to (2,m) \to \cdots \to (n,m)$，但是这样显然不一定是最优解，因此考虑调整。调整的第一步显然是将 $(1,m-1) \to (1,m) \to (2,m)$ 调整为 $(1,m-1) \to (2,m-1) \to (2,m)$，显然后者代价前者更优，当且仅当 $a_2 + b_{m-1} < a_1 + b_m$。再者就是将 $(1,m-2) \to (1,m-1) \to (2,m-1) \to (2,m)$ 调整为 $(1,m-2) \to (2,m-2) \to (2,m-1) \to (2,m)$，以此类推。按照这样的方式继续手玩下去可以发现，在最终的状态中，假设我们在点 $(i,j)$，那么我们会往下走，当且仅当 $j=m$，或者 $i \neq n$ 且 $a_{i+1} - a_i < b_{j+1} - b_j$。

我们考虑设 $pos_i$ 表示我们处于第 $i$ 行时，会在哪个位置首次向下走，由于 $n$ 很小并且题目中 $a, b$ 序列都是下凸的，因此对于同一行 $i$，必然存在一个断点 $j$，使得对于 $j$ 左边所有位置，当我们位于 $(i,j)$ 时都会向右走，而对于 $j$ 右边所有位置，当我们位于 $(i,j)$ 时都会向下走。且 $pos$ 数组也是单调不降的。这样一来问题就好办了，由于 $n$ 很小，因此对于每次修改，改完之后都可以直接线段树二分修改 $pos$ 数组，而答案即为

$$\sum_{i=1}^{n}\left(a_i \cdot (pos_i - pos_{i-1} + 1) + \sum_{j=pos_{i-1}}^{pos_i - 1} b_j\right)$$

这个也可以每次 $O(n \log m)$ 地求。比较麻烦的是要实现单点加求三阶前缀和，用树状数组维护平方项、一次项和常数项能够获得常数较小的实现。

时间复杂度 $\Theta(nm \log m)$。



# T4

意思可以转化为，删掉的数 $x \to x-2, x+K$ 连续，不存在环（若不存在，按逆拓扑删除即可；若存在，这些数都不能删除）

如果 $K$ 是偶数，奇偶分别 dp 即可，以下默认 $K$ 是奇数。

可以发现，不存在环等价于，把所有删了的数在一个长度为 $n$ 的 01 串中设为 1，不存在形如 `1*1*1*…*1` 的子串（`*` 匹配任意一个字符，中间 `1` 的个数为大于等于 3 的奇数，上面字符中不算 `*`，总 `1` 数恰为 $K+2$）

把奇数位置、偶数位置排成两行，那么就是不能存在以下图形（也不能存在以下图形反过来）：

```text
... 1 1 1 1 1 1 1 ...

(m 个 1)

... ? 1 1 1 1 ? ? ...

(至少有 K+2-m 个 1，下面的对称中心是上面的对称中心右移 0.5 格)
```

或者

```text
... ? ? 1 1 1 1 1 ? ...

(至少有 K+2-m 个 1，下面的对称中心是上面的对称中心右移 0.5 格)

... 1 1 1 1 1 1 1 ...

(m 个 1)
```

这个做法的后半部分是神仙 crn 教我的，orz crn!

设 $f(p,i,j,k)$ 表示现在算到了第 $p$ 个位置，和 $p$ 奇偶性相同的一行自从 $i$ 以来就全是 1，和 $p$ 奇偶性不同的一行从 $j$ 以来就全是 1 的前 $p$ 个位置，

- $i<j$：目前的限制是和 $p$ 奇偶性相同的一行最右边至多能填到 $k$ 的方案数。
- $i>j$：目前的限制是和 $p$ 奇偶性不同的一行最右边至多能填到 $k$ 的方案数。

转移：

- $f(p,i,j,k) \to f(p+1,\,n+1,\,i,\,?)$（不填第 $p+1$ 个位置，$?$ 的位置如果 $i<j$ 就是 $k$ 否则是 $n+1$）
- $f(p,i,j,k) \to f\big(p+1,\,\min(p+1,j),\,i,\,\min(k,R)\big)$（$i<j$，填第 $p+1$ 个位置，拿 $[i,p]$ 和 $[j,p+1]$ 算出来 $p$ 这一行最多能填到 $R$）（$i>j$，填第 $p+1$ 个位置，拿 $[i,p]$ 和 $[j',p+1]$ 算出来 $p+1$ 这一行最多能填到 $R$，要求 $\min(k,R)\ge p+1$）