倍增求助
查看原帖
倍增求助
749630
wxzzzz楼主2023/10/5 19:14

本人不会任何有一点思维难度的方法,于是写了倍增(假倍增)

#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;
}

希望有人看懂并帮我调出来,万分感谢+膜拜

2023/10/5 19:14
加载中...