怎样做好物流网站建设,手机销售网站怎么做,营销策略论文,wordpress 帮助模板解析
设 x,y∈B,xyx,y\in B,xyx,y∈B,xy#xff0c;那么也有 x−y∈Bx-y\in Bx−y∈B。 递归下去#xff0c;根据辗转相减求 gcd\gcdgcd 的方法可知#xff0c;最终会得到 gcd(x,y)\gcd(x,y)gcd(x,y)。 那么对于整个集合 BBB #xff0c;它也就等价于所有…解析
设 x,y∈B,xyx,y\in B,xyx,y∈B,xy那么也有 x−y∈Bx-y\in Bx−y∈B。 递归下去根据辗转相减求 gcd\gcdgcd 的方法可知最终会得到 gcd(x,y)\gcd(x,y)gcd(x,y)。 那么对于整个集合 BBB 它也就等价于所有元素的 gcd\gcdgcd设为 ggg。 这样我们就把多个元素转化为了单一元素的问题。
构造一个数列 b1...nb_{1...n}b1...n如果最后 aia_iai 乘了 −1-1−1bi1b_i1bi1反之为 000。 设 fx⊕i%gxbi,x∈[0,g−1]f_{x}\oplus_{i\%gx}b_i,x\in[0,g-1]fx⊕i%gxbi,x∈[0,g−1]。那么初始的 fff 均为 000每次操作所有的 fff 都会异或 111所以无论如何变换所有的 fxf_xfx 都是相等的。 同时我们也可以通过变换得到任意一个 fxf_xfx 相等的局面所以 fxf_xfx 均为 0/1 是一个序列合法的等价条件。 利用这个性质简单 dp 即可。
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
const int N2e6100;
const int M1e6100;int n,m;
int gcd(int x,int y){return y?gcd(y,x%y):x;
}
int g;
int a[N];
ll dp[N][2];
void work(){nread();mread();g0;for(int i1;in;i) a[i]read();for(int i1;im;i) ggcd(g,(int)read());for(int i1;ig;i){dp[i][0]a[i];dp[i][1]-a[i];}for(int ig1;in;i){dp[i][0]max(dp[i-g][0]a[i],dp[i-g][1]-a[i]);dp[i][1]max(dp[i-g][1]a[i],dp[i-g][0]-a[i]);}ll x(0),y(0);for(int in-g1;in;i){xdp[i][0];ydp[i][1];}printf(%lld\n,max(x,y));
}
signed main(){#ifndef ONLINE_JUDGE//freopen(a.in,r,stdin);//freopen(a.out,w,stdout);#endifint Tread();while(T--) work();return 0;
}
/*
*//*
*/
