第五届图灵杯趣味网络国际邀请赛 - 中级组T1求助
  • 板块灌水区
  • 楼主Ac_forever
  • 当前回复9
  • 已保存回复9
  • 发布时间2023/5/19 20:15
  • 上次更新2023/10/23 15:20:53
查看原帖
第五届图灵杯趣味网络国际邀请赛 - 中级组T1求助
768416
Ac_forever楼主2023/5/19 20:15
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 500007
using namespace std;
typedef long long ll;
int n,a[N],t;
struct ar {
	ll cha1,back1,back2,cha2;
	int t1,t2;
} b[9000007];
int main() {
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	scanf("%d",&t);
	while(t--) {
		scanf("%d",&n);
 		for(int i=1; i<=n; i++)scanf("%d",&a[i]);
 		sort(a+1,a+n+1);
		int w=3,l=1;
		int g=a[2]-a[1],wz=0;
		bool hh=1,ff=1;
		for(int i=3; i<=n; i++)
			if(a[i]-a[i-1]!=g) {
				wz=i,ff=0;
				break;
			}
		if(ff) {
			printf("Yes\n");
			continue;
		}
		int u=a[wz+1]-a[wz];
		for(int i=wz+2; i<=n; i++)
			if(a[i]-a[i-1]!=u) {
				hh=0;
				break;
			}
		if(hh) {
			printf("Yes\n");
			continue;
		}
		b[1].back1=a[2],b[1].cha1=a[2]-a[1],b[1].back2=a[3],b[1].t1=2,b[1].t2=1;
		b[2].back1=a[1],b[2].back2=a[3],b[2].cha2=a[3]-a[2],b[2].t1=1,b[2].t2=2;
		b[3].back1=a[3],b[3].cha1=a[3]-a[1],b[3].back2=a[2],b[3].t1=2,b[3].t2=1;
		if(a[3]-a[2]==a[2]-a[1])++w,b[4].back1=a[3],b[4].cha1=a[3]-a[2],b[4].t1=3,++w,b[5].back2=a[3],b[5].cha2=a[3]-a[2],b[5].t2=3;
		int bz=1;
		for(int i=4; i<=n; i++) {
			bool flag=0;
			int u=w;
			for(int j=l; j<=u; j++) {
				if(b[j].t1==1)b[++w]=b[j],b[w].cha1=a[i]-b[j].back1,b[w].back1=a[i],b[w].t1++,flag=1;
				else if(b[j].t1==0)b[++w]=b[j],b[w].back1=a[i],b[w].t1++,flag=1;
				else if(a[i]-b[j].back1==b[j].cha1)b[++w]=b[j],b[w].back1=a[i],b[w].t1++,flag=1;
				if(b[j].t2==1)b[++w]=b[j],b[w].cha2=a[i]-b[j].back2,b[w].back2=a[i],b[w].t2++,flag=1;
				else if(b[j].t2==0)b[++w]=b[j],b[w].back2=a[i],b[w].t2++,flag=1;
				else if(a[i]-b[j].back2==b[j].cha2)b[++w]=b[j],b[w].back2=a[i],b[w].t2++,flag=1;
			}
			l=u+1;
			if(!flag) {
				printf("No\n"),bz=0;
				break;
			}
		}
		if(bz)printf("Yes\n");
		for(int i=1; i<=w+1; i++)b[i].back1=b[i].back2=b[i].cha1=b[i].cha2=b[i].t1=b[i].t2=0;
	}
}

subtask3 即a[n]<=n+2的子任务第二个出错了,求hack或指正,修改。 题目链接:https://contest.xinyoudui.com/contest/92/problem/368

2023/5/19 20:15
加载中...