本人不会任何有一点思维难度的方法,于是写了倍增(假倍增)
#include <bits/stdc++.h>
#define ll long long
#define rll register ll
#define cll const ll
#define N 2005
using namespace std;
inline ll read()
{
rll x=0;bool f=1;register char c=getchar();
while(c<48||c>57){if(c=='-') f=0;c=getchar();}
while(c>=48&&c<=57){x=x*10+(c^48);c=getchar();}
return f?x:-x;
}
inline void write(ll x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+48);
}
ll q=read(),n,m,a[N],b[N],t[N][25];
inline bool check()
{
for(rll i=1;i<=n;i++)
if(a[i]!=b[i]) return 0;
return 1;
}
int main()
{
while(q--)
{
n=read(),m=log(n)/log(2);
memset(a,0,sizeof a);
for(rll i=1;i<=n;i++) t[i][0]=read();
for(rll i=1;i<=n;i++) b[i]=read();
if(n==1)
{
if(t[1][0]==b[1]) puts("YES");
else puts("NO");
continue;
}
for(rll i=1;i<=n;i++)
t[i][1]=t[i][0]+t[n-i+1][0];
memset(a,0,sizeof a);
for(rll j=2;j<=m;j++)
for(rll i=1;i<=n;i++)
t[i][j]=t[i][j-1]*2;
for(rll j=m;j>=0;j--)
while(a[1]+t[1][j]<=b[1])
for(rll i=1;i<=n;i++)
a[i]+=t[i][j];
if(check()) puts("YES");
else puts("NO");
}
return 0;
}
希望有人看懂并帮我调出来,万分感谢+膜拜