「思维」CF1630D Flipping Range Solution

题面传送门(CF)

题面传送门(luogu)

考虑b能够构造出的区间情况：

• b=1 : 只有一种区间
• b>1 : 先考虑b=2的情况，发现能组合出的最小单位区间是两者的gcd，其实就是辗转相除法，所以所有b能组合出的最小单位区间就是它们的gcd。

这时题意其实转变为了给定区间长度b（gcd），能够翻转区间正负性，求所有数的最大和。

直接用b来做其实有些麻烦，考虑移动区间，组合成同时翻转第i位和第i+b位的正负性（后者其实可以推出i+kb位）。

将所有a中的数按模b余数分类。

分类完后，每一类中如果有奇数个负数，只需要找到这类数中绝对值最小的数作为唯一的负数即可，其余数均取绝对值。

偶数个负数直接类中绝对值求和即可。

但是这样仍不一定最优，b能够翻转下标为1~b的ai，其实就是翻转它们所在类的负数数量奇偶性，所以我们两种答案都要计算。

#include <bits/stdc++.h>
using namespace std;
namespace IO{
    #define I inline
    I char tc(){static char tr[10000],*A=tr,*B=tr;return A==B&&(B=(A=tr)+fread(tr,1,10000,stdin),A==B)?EOF:*A++;}
    I void read(int &x){
        char c;int y=1;x=0;
        while(((c=tc())<'0'||c>'9')&&c!='-');c=='-'?y=-1:x=c-'0';
        while((c=tc())>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0';
        x*=y;
    }
    // I void read(int &x){scanf("%d",&x);}
    #undef I
}using namespace IO;

const int N = 1e6+5;
typedef long long LL;
int gcd(int x,int y){return !y?x:gcd(y,x%y);}
#define min(x,y) (x) < (y) ? (x) : (y)

int T,n,m,a[N];
int main()
{
    for(read(T);T;--T){
        read(n),read(m);
        LL b=0,Ans1=0,Ans2=0;
        for(int i=1;i<=n;++i)read(a[i]);
        for(int i=1,x;i<=m;++i)read(x),b=gcd(x,b);
        for(int i=1;i<=b;++i){
            LL tot=0,cnt=0,mi=1e9;
            for(int j=i;j<=n;j+=b){
                tot+=abs(a[j]);
                cnt+=(a[j]<0);
                mi=min(mi,abs(a[j]));
            }
            // printf("$%d %d %d\n",tot,cnt,mi);
            Ans1+=tot-2ll*(cnt&1?mi:0);
            Ans2+=tot-2ll*(cnt&1?0:mi);
        }
        printf("%lld\n",max(Ans1,Ans2));
    }
}