【ZJ选讲·BZOJ 5071】

小A的数字

有一串数字A1 ,A2，……，An，每次可以进行如下骚操作： 选择一个数字i，将(Ai-1，Ai，Ai+1)变为(Ai-1+Ai，-Ai，Ai+1+Ai)， （特别地，若i=N，则(An-1，An)变为(An-1+An，-An )。） 问是否可以通过若干次操作，使得序列变为给定的B1 ,B2 ,……,Bn 

N<=105

【题解】

①分析变化的特点，可以发现前缀和发生的变化如下：

(Si-1,Si,Si+1) ——> (Si,Si-1,Si+1)

②上述变化相当于冒泡排序，由于操作次数无限,所以只需要将两个序列排序看是否相同即可。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

ll sumA[100005],sumB[100005];

int main(){

	int T,n;

	scanf("%d",&T);

	while(T--){

		scanf("%d",&n);

		for(int i=1;i<=n;i++) scanf("%lld",&sumA[i]),sumA[i]+=sumA[i-1];

		for(int i=1;i<=n;i++) scanf("%lld",&sumB[i]),sumB[i]+=sumB[i-1];

		sort(sumA+1,sumA+n+1);

		sort(sumB+1,sumB+n+1);

		for(int i=1;i<=n+1;i++){

			if(i==n+1) printf("YES\n");

			if(sumA[i]!=sumB[i]){

				printf("NO\n");

				break;

			}

		}

	}

	return 0;

}//*ZJ

巴特西

【ZJ选讲·BZOJ 5071】

最新文章

热门文章