「MCOI-02」Build Battle 建筑大师 题解

· · 题解

假设当前询问的m_i为m，a_i为第i个羊毛的颜色。

Subtask\ 1:

直接暴力枚举所有可能的子序列并用Hash/一些奇奇怪怪的方法判重。

时间复杂度O(2^n*判重的时间)。期望得分5分。

Subtask\ 2$ && $3:

考虑DP，f_i表示我们匹配到颜色序列第i位时的方案数。考虑再在后面添加一个x，假设next_{i,x}表示i右边最近的x的位置，则f_{next_{x,i}}+=f_i。

因为我们这种贪心匹配（每次选择最近的一个），所以不会计算重复。

时间复杂度O(n*max \{ m_i\})。期望得分35分。

Subtask\ 4:

我们这样只是将这个序列当成一个普通序列来做的，并没有利用其良好的性质。

我们考虑对于x，只有x-m，x-m-1，...，x-1会转移到x（因为更前面的点会转移到x-m）。

所以f_i=f_{i-1}+f_{i-2}+...+f_{i-m}，前缀和优化即可。

时间复杂度O(n)，期望得分60分。

Subtask\ 5:

假设s_i=\sum_{j=1}^{i}f_j，所以s_i=2*s_{i-1}-s_{i-m-1}，而我们要求的就是s_n。

可以考虑把这个问题转换成另一个问题：

从0出发走到n，有一个初始等于1的阈值v，有两种行动方式：

$2.$从$x$走到$x+m+1$，并让 $v=-v$。 每次走到$n$之后，让初始为$0$的$ans+=v$。可以发现转换问题后$s_n=ans$（即跟原问题等价）。 可以发现$v$的值只跟两种行动方式的次数有关，所以考虑枚举行动方式$2$的次数，则可以得到： $s_n=ans=\sum_{i=0}^{i\le \lfloor \frac{n}{m+1} \rfloor}2^{n-(m+1)*i}*(-1)^{i}* \binom{(n-(m+1)*i)+i}{i}

(行动方式2走了i步，行动方式1会走n-(m+1)*i步，总共就会走(n-(m+1)*i)+i步)

可以对所有m直接暴力算出这个式子的值，这样时间复杂度是n/1+n/2+...+n/n=O(nlogn)的。期望得分100分。

总体来说本题应该是一道比较良心的签到题，有经验的OIer应该可以直接秒掉。出题人认为这题应该比A简单，但是书虫非要我放B /kk。

为啥那么多人会60不会100啊，这trick不是挺常见的嘛/fad。

upd：我才发现我上面的系数写反了，感谢@2016wudi的指出qwq。