题解

CWOJ contest 0625 题解

Problem A

注意到如果没有二操作，就是一个简单的dp。观察发现连续执行两次执行操作二一定不优。因为若连续执行两次操作二，之前至少有一次操作三。那么把这两个操作二删去，在之前的操作三前添加一个操作二，一定更优且结果不变，得证。

那么对于一个操作二，它之前就只可能是操作三。

那么设 $dp_i$ 为得到 $i$ 的最小步数，转移为：

$$dp_i\leftarrow dp_{i-1}+x\\ dp_i\leftarrow dp_{\frac{i}{2}}+y(i\%2=0)\\ dp_i\leftarrow \min(dp_{\frac{i-1}{2}}+x+y,dp_{\frac{i+1}{2}}+x+y);$$
时间复杂度 $O(n)$ 。

Problem B

观察发现其实当 $3\leq k$ 的时候，可行的左端点是 $O(sqrt_3(n))$ 级别的，对于这些情况，我们可以直接暴力尺取法，注意判断一下边界，因为很容易乘爆。

对于 $k=2$ 的 $\text{case}$ ，发现左端点其实是 $O(sqrt(n))$ 的，多组询问无法接受，于是考虑长度，发现可行的长度是 $O(sqrt_3(n))$ 的，可以枚举长度并二分左端点得到答案。这样的话，预处理前缀平方和的数组会超过 unsigned long long 的存储范围，你当然可以使用 __int128 ，但是有一种更加优美的做法，我们知道二者相减一定是在 unsigned long long范围内的，所以考虑直接让前缀和自然溢出，这样就相当于对 $2^{64}$ 取模，如果减出来是负数，那么加上一个 $2^{64}$ 就可以得到希望的答案。

对于 $k=1$ 的 $\text{case}$ ，套用等差数列求和公式有 $n=(l*2+len-1) * (len) / 2$。我们对 $n$ 进行分解质因数然后枚举其所有约数作为 $len$ 并检查是否合法即可，注意约数个数是相当有限的，所以这样是没问题的。注意对 $20$ 个 $10^{14}$ 级别的数分解质因数的时间有点无法接受，所以考虑预处理出 $10^7$ 以内的约 $10^6$ 个质数，并只枚举质数分解。枚举约数可以直接 $\text{dfs}$。

复杂度分析省略。

Problem C

我们考虑对进行操作后的序列，发现只需要满足 $max(a_i)-min(a_i)\leq d$ 就可以了。

于是考虑所有可行的 $min$ 值。不妨记其为 $x$ 。考虑确定了 $x$ 后如何计算答案，发现一定是把比它小的数调整到 $x$ ，把比 $d+x$ 大的数调整到 $x+d$ ，其它数不用管。

考虑所有可行的 $x$ 发现它一定是 $a_i$ 或 $a_i-d$，假设不是这些值，不妨让把所有的 $a_i$ 和 $a_i-d$ 在数轴上画出来，考虑用一条长度为 $d$ 的线段在数轴上移动，其左端点为我们选择的 $x$ ，如果没有在哪些点上，我们向左或向右移动到那些点之后一定会更优，因为这个过程中，我们的左右端点不会越过任何一个会对答案产生贡献的点，所以，如果左边需要调整的点多，就往左，否则往右。

考虑对所有的这些点离散化，枚举 $x$，然后用线段树维护区间的有贡献的点 ($a_i$) 和它们的坐标和。分别计算左边和右边的贡献就可以得到当前的最优答案，把所有答案取 $\text{min}$ 就可以了。

时间复杂度 $O(nlogn)$。

存在 $O(n)$ 做法，请自行思考。

Problem D

考虑暴力的dp,设 $dp_{i,j}$ 为第 $i$ 天在 $j$ 的概率，时间复杂度 $O(n\times k)$ ，可通过子任务2。

容易发现，上面的 $dp$ 第 $i$ 天和第 $i+n$ 天的转移是一样的，即第 $i$ 天的转移只和 $i\%n$ 有关，所以每个周期的转移是相同的。于是我们可以把 $n$ 天作为一个周期，若设 $k=xn+r(r<n)$ 那么 $k$ 天可以划分为 $x$ 个周期和余下的天数。考虑如何快速计算 $x$ 个周期从 $1$ 出发到达每个点的方案数，对于一个周期预处理出 $dp_{i,j}$ ，表示从 $i$ 出发，经过一个周期到 $j$ 的方案数。如果把 $dp$ 看成矩阵，那么 $x$ 个周期的方案数就是 $dp^x$ ，可用矩阵快速幂优化。对于余下的 $r$ 天直接暴力转移。时间复杂度 $O(n^3\times\log(k))$ ，可通过子任务3。

上面算法的复杂度瓶颈在于求 $x$ 个周期的方案数。我们考虑 $dp$ 矩阵记录的信息是否都是必要的？能否简化？接下来是经典的矩阵乘法转卷积的过程。

我们再次观察 $dp$ 矩阵，发现若 $a-b\equiv c-d$ ，则 $dp_{a,b}=dp_{c,d}$ ，说明其实方案数只和起点和终点的位置差有关，而和起点无关。

所以我们调整状态，设$f_u(i)$ 表示走完 $u$ 个周期后，终点的位置相对于起点的位置之差为 $i$ （顺时针方向）的方案数。对于一个周期，我们预处理出 $f_1(i)$ ，这一部分时间复杂度 $O(n^2)$ 。那么容易得到 $f_2(i)$ ：

$$f_2{((i+j)\%n)}\leftarrow f_1(i)\times f_1(j)$$
这是一个卷积的形式，而 $x$ 个周期就恰好是 $x$ 个 $f_1$ 卷起来，可以用快速幂优化。因为（暴力）卷积的复杂度是 $O(n^2)$ 的，所以这一部分复杂度 $O(n^2\times \log(n))$ 。总时间复杂度 $O(n^2\times \log(n))$ 。