WA #2,但是对了几十万组的拍没找到问题,调疯了
  • 板块CF1474D Cleaning
  • 楼主ny_Dacong
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/12/16 19:35
  • 上次更新2024/12/16 22:27:55
查看原帖
WA #2,但是对了几十万组的拍没找到问题,调疯了
928972
ny_Dacong楼主2024/12/16 19:35

跟题解区的代码对拍,数据随机生成。没拍出来,调疯了。

#include<bits/stdc++.h>
using namespace std;
long long t,n;
long long num[200005],h[200005],Min[200005],pos[200005];
int main(){
//	freopen("Jdata.in","r",stdin);
//	freopen("J.out","w",stdout);
	scanf("%lld",&t);
	while(t--){
		scanf("%lld",&n);
		memset(h,0,(n+3)*sizeof(long long));
		memset(num,0,(n+3)*sizeof(long long));
		memset(pos,0,(n+3)*sizeof(long long));
		memset(Min,0x3f,(n+3)*sizeof(long long));
		for(long long i = 1; i <= n; i++){
			scanf("%lld",&num[i]);
			h[i] = num[i]-h[i-1];
		}
		for(long long i = n; i >= 0; i--){
			if(Min[i+1] > h[i]){
				Min[i] = h[i];
				pos[i] = i;
			}else{
				Min[i] = Min[i+1];
				pos[i] = pos[i+1];
			}
		}
		if(Min[0] >= 0 && h[n] == 0){
			puts("YES");
			goto End;
		}
		for(long long i = 1; i <= n-1; i++){
//			h[i+3] = num[i+1]-num[i]-num[i]+num[i+1]
//			h[i+2] = -num[i+1]+num[i]+num[i]-num[i+1]
			if((pos[i]-i)&1){
				if(Min[i]-(num[i+1]<<1)+(num[i]<<1) >= 0){
					if((n-i)&1){
						if(h[n]-(num[i+1]<<1)+(num[i]<<1) == 0){
							puts("YES");
							goto End;
						}
					}else{
						if(h[n]+(num[i+1]<<1)-(num[i]<<1) == 0){
							puts("YES");
							goto End;
						}
					}
				}
			}else{
				if(Min[i]+(num[i+1]<<1)-(num[i]<<1) >= 0){
					if((n-i)&1){
						if(h[n]-(num[i+1]<<1)+(num[i]<<1) == 0){
							puts("YES");
							goto End;
						}
					}else{
						if(h[n]+(num[i+1]<<1)-(num[i]<<1) == 0){
							puts("YES");
							goto End;
						}
					}
				}
			}
			if(h[i] < 0){
				puts("NO");
				goto End;
			}
		}
		puts("NO");
		End:
			continue;
	}
	return 0;
}
2024/12/16 19:35
加载中...