The Solution of CF1630D

CSP_Sept · 2022-01-31 16:02:59 · 题解

是我 idea 弱化版 /fn

（以下内容除了 Hint 选自官方 Editorial 帮助理解外，其他均为原创。）

视频讲解

大意

给定长度为 n 的数列 a 和含有 m 个元素的集合 B，其中 1\le B_i\le \left\lfloor\frac{n}2\right\rfloor。

你可以进行无限次操作，每次操作：

1. 选择一个 x 和一个区间 [l,r]，其中有 x\in B,1\le l\le r\le n 且 r-l+1=x。
2. 把所有 i\in [l,r] 的 a_i 变成 -a_i。

求操作后 \sum a_i 的最大值。

Hint 1

最短的可操作区间长度是多少？

Hint 2

构造长度为 n 的 01 串 s，s_i=0 则说明 a_i 会被乘上 -1，s_i=1 则反之。什么样的 s 是可以实现的？（下标从 0 开始）

解法

以下我们把「选择区间 [l,r] 进行操作」记作「q(l,r)」，把「使长度为 len 的一个区间中的所有数变成它的相反数」记作「p(len)」。

如果我们有 x,y\in B（不妨设 x>y），因为 B 的所有元素至多是 \left\lfloor\frac{n}2\right\rfloor，所以我们可以实现任意一个 p(x-y)，方法如下：

1. 依次进行 q(k+1,k+x),q(k+x-y+1,k+x)，即可实现，其中 k 是我们要实现的长度为 x-y 的区间的左端点。
2. 依次进行 q(k-x+1,k),q(k-x+1,k-x+y)，即可实现，其中 k 是我们要实现的长度为 x-y 的区间的右端点。

于是我们可以直接把 x-y 弹进 B'（即 B 的扩充集合），运用辗转相除法可以得到 \gcd(x,y)\in B'。

令 g=\gcd(B_1,B_2,\ldots,B_m)，运用上面的证明得到以下性质：

于是问题转化为：

进行任意次 p(g)，最大化 \sum a_i。

考虑「Hint 2」的定义，s 初始为全 0 串，每个 p(g) 都 01 翻转了 s 的一个长度为 g 的区间。

我们定义 f_x(0\le x< g) 表示所有 i\bmod g=x 的 s_i 的异或和，注意到任意一次操作后所有 f_x 都会变化。

所以只有使所有 f_x 都相等的 s 是可以实现的。

于是可以考虑 dp。

设 dp(i,j) 表示 a_i+a_{i+g}+a_{i+2\cdot g}+\cdots+a_{i+k\cdot g} 的最大值，其中 f_i\oplus f_{i+g}\oplus f_{i+2\cdot g}\oplus\cdots\oplus f_{i+k\cdot g}=j。

考虑答案，显然是

时间复杂度 O(n)。

核心代码

for(int i = 0 ; i < m ; i++)
    g = gcd(g, b[i]);
for(int i = 0 ; i < g ; i++)
    dp[i][0] = 0, dp[i][1] = -3e9;
for(int i = 0 ; i < n ; i++){
    ll x1 = dp[i % g][0], x2 = dp[i % g][1];
    dp[i % g][0] = max(x1 + a[i], x2 - a[i]);
    dp[i % g][1] = max(x2 + a[i], x1 - a[i]);
}
sum1 = sum2 = 0;
for(int i = 0 ; i < g ; i++)
    sum1 += dp[i][0], sum2 += dp[i][1];
printf("%lld\n", max(sum1, sum2));

完整版本（\textit{144625983}）