题解 CF1630D【Flipping Range】

· · 题解

本篇是 CF1630D 的题解，请管理员暂且从 CF1603D 的题解处撤下本篇，谢谢！

这题初看起来也许有些无从下手，我们先来分析一些简单的情况。假若存在某个 b_i=1，我们知道，每一位上的数字的符号反转与否是相互独立的，答案便是全部数字的绝对值之和。

我们来考虑，如果对一组 B，答案一定是全部数字的绝对值之和，这组 B 应该满足什么条件。举例来说，假设有 B 中有两个数 3,4，我们可以断言答案一定就是全部数字的绝对值之和，因为如果我们要单独反转某一位，我们一定可以先反转以这个位为左端点 / 右端点的一段长度为 4 的区间，再把本来不应该反转的 3 位去掉。注意这里“一定能找到这样的区间”用到了 b_i\leq \lfloor \dfrac{n}{2}\rceil 的性质。再比如说，如果有两个数 3,5，我们可以如法炮制，利用反转 3,5 的“工具”来获得一个反转 2 的“工具”，再利用反转 3,2 的“工具”来获得最终的反转 1 的工具。

从这里实际上已经可以发现此题和辗转相除法的关系了。利用两个权值为 x,y 的“工具”（也就是 B 中的两个元素），我们可以创造出权值为 x-y 的“工具”，进一步地，还能创造出权值为 (x,y) 的工具（这里的小括号指最大公因数，下同）。同样地，设 d=(b_1,...,b_m)，那么我们可以创造出权值为 d 的工具。可以发现，这个权值为 d 的工具的反转能力和之前的 B 的反转能力完全一致。也就是说，我们只需要解决 B 中只有一个元素的情况，就解决了原题。

接下来的问题并不困难。观察到每次操作一定恰好反转了下标模 d 余 0,1,...,(d-1) 的元素各一个，记 c_i(0\leq i < d) 表示下表模 d 余 i 的位置有多少个被反转了，那么有解的一个必要条件为 c_0,...,c_{d-1} 奇偶性全部相同。容易证明这也是有解的充分条件。通过 DP 求出对每个 i，模 d 余 i 的元素中选出奇数个 / 偶数个取反，各数总和的最大值，最后在 c_i 全为奇数或偶数的总和中取较大值即可。

#include<cstdio>
#include<algorithm>

using namespace std;

int gcd(int x,int y){return y?gcd(y,x%y):x;}

long long a[2000000];
long long dp[2000000][2];

int main()
{
    int T=0;scanf("%d",&T);
    while(T--)
    {
        int n=0,m=0;scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
        int d=0;for(int i=1,b=0;i<=m;i++){scanf("%d",&b);d=gcd(b,d);}
        for(int i=n;i>=1;i--)
        {
            if(i+d>n)dp[i][0]=a[i],dp[i][1]=-a[i];
            else dp[i][0]=max(dp[i+d][0]+a[i],dp[i+d][1]-a[i]),
                dp[i][1]=max(dp[i+d][1]+a[i],dp[i+d][0]-a[i]);
        }
        long long sum1=0,sum2=0;for(int i=1;i<=d;i++)sum1+=dp[i][0],sum2+=dp[i][1];
        printf("%lld\n",max(sum1,sum2));
    }
}