题面传送门(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));
}
}