求助 ARC C
  • 板块学术版
  • 楼主樱雪喵>w<
  • 当前回复6
  • 已保存回复6
  • 发布时间2023/1/29 22:08
  • 上次更新2023/11/12 17:53:04
查看原帖
求助 ARC C
234074
樱雪喵>w<楼主2023/1/29 22:08

RT,赛时一直 WA 4 个点,球大佬帮忙看下哪里写挂了 QAQ

思路大概是如果序列里有任何一对奇数距离<2,则整个序列可以随便移动;否则只有长度>=3 的偶数段能动,然后和目标序列比对。感觉做法和题解应该一样的(?)

#include<bits/stdc++.h>
#define il inline
using namespace std;
il int read()
{
	int xr=0,F=1;char cr=getchar();
	while(cr<'0'||cr>'9') {if(cr=='-') F=-1;cr=getchar();}
	while(cr>='0'&&cr<='9')
	    xr=(xr<<3)+(xr<<1)+(cr^48),cr=getchar();
	return xr*F;
}
const int N=2e5+5;
int n,a[N],b[N],c[N],d[N];
int main()
{
	n=read();
	for(int i=1;i<=n;i++) a[i]=c[i]=read();
	for(int i=1;i<=n;i++) b[i]=d[i]=read();
	
	sort(c+1,c+n+1),sort(d+1,d+n+1);//排序后相等 
	for(int i=1;i<=n;i++) if(c[i]!=d[i]){printf("No\n");return 0;}
	
	bool flag=0;
	bool hv=0;
	for(int i=1;i<=n;i++) if(a[i]%2==0) hv=1;
	if(!hv)//全是奇数则不能移动 
	{
		for(int i=1;i<=n;i++) if(a[i]!=b[i]){printf("No\n");return 0;}
		printf("Yes\n");return 0;
	}
	for(int i=2;i<=n;i++)
	{
		//if(a[i]) hv=1;
		if((a[i]&1)&&((a[i-1]&1)||(a[i-2]&1))) flag=1;
	}
	if(!flag)//原序列奇数不能移动 
	{
		int lst=0;a[n+1]=b[n+1]=1;
		for(int i=1;i<=n+1;i++)
		{
			if(a[i]&1)
			{
				//cout<<"qwq "<<lst<<" "<<i<<endl;
				if(a[i]!=b[i]) {printf("No\n");return 0;}
				if(lst!=i-3) sort(a+lst+1,a+i),sort(b+lst+1,b+i);
				for(int k=lst+1;k<i;k++) 
				{
					if(a[k]!=b[k])
					{
						printf("No\n");
						return 0;
					}
				}
				lst=i;
			}
		}
		printf("Yes\n");
		return 0;
	}
	bool fg=0;
	for(int i=2;i<=n;i++)//目标序列的奇数能否移动 
	{
		if((b[i]&1)&&((b[i-1]&1)||(b[i-2]&1))) fg=1;
	}
	if(fg) printf("Yes\n");
	else printf("No\n");
	return 0;
}
/*
7
1 2 6 4 1 8 3
4 1 6 1 2 8 3
*/
2023/1/29 22:08
加载中...