1893. [国家集训队2011]等差子序列(bitset)

attack

发布于 2018-04-12 11:42:54

8060

发布于 2018-04-12 11:42:54

文章被收录于专栏：数据结构与算法数据结构与算法

★★ 输入文件：nt2011_sequence.in 输出文件：nt2011_sequence.out 简单对比时间限制：0.3 s 内存限制：512 MB

【试题来源】

2011中国国家集训队命题答辩

【问题描述】

给一个1到N的排列{Ai}，询问是否存在1<=p1<p2<p3<p4<p5<…<pLen<=N（Len>=3），使得Ap1,Ap2,Ap3,…ApLen是一个等差序列。

【输入格式】

输入的第一行包含一个整数T，表示组数。下接T组数据，每组第一行一个整数N，每组第二行为一个1到N的排列，数字两两之间用空格隔开。

【输出格式】

对于每组数据，如果存在一个等差子序列，则输出一行“Y”，否则输出一行“N”。

【样例输入】

2 3 1 3 2 3 3 2 1

【样例输出】

N Y

【数据说明】

对于5%的数据，N<=100 对于30%的数据，N<=1000 对于100%的数据，N<=10000，T<=7 对于100%的数据，时间限制为0.3s。

思路比较好想，以一个数为中心，

判断一下这个数的对称的两侧，

如果一侧的数出现了但是另一侧的没出现。

那么一定存在一个可行方案

但是。

感觉自己见鬼了，

用bitset超时的题居然改成bool类型就A了，。

而且还开着o2优化。。。。

在codevs上bool比bitset快5000+ms。。。。。。。。。。。

顺便提一下，

这道题的正解是线段树/树状数组+hash

一份不能A的bitset：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<bitset>
using namespace std;
using std::bitset;
const int MAXN=10001;
bitset<MAXN>bit;
int a;
inline void read(int &n)
{
	char c='+';int x=0;bool flag=0;
	while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
	while(c>='0'&&c<='9'){x=x*10+(c-48);c=getchar();}
	n=flag==1?-x:x;
}
int main()
{
	freopen("nt2011_sequence.in","r",stdin);
	freopen("nt2011_sequence.out","w",stdout);
	int T;
	read(T);
	while(T--)
	{
		bit.reset();
		int n;
		read(n);
		bool flag=0;
		for(int i=1;i<=n;i++)
		{
			read(a);
			if(flag)continue;
			bit.set(a);
			for(int j=a-1;j!=0;j--)
			{
				int k=a*2-j;
				if(k>n)continue;
				if(bit.test(j)^bit.test(k))
				{
					flag=1;
					break;
				}
			}
		}
		flag==1?printf("Y\n"):printf("N\n");
	}
	return 0;
}

一份可以A的bitset

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<bitset>
using namespace std;
const int SIZEN=10010;
int N;
int A[SIZEN];
bitset<SIZEN> pre,suf;
bool test(void){//只能检测递增的
	pre.reset();suf.reset();
	for(int i=1;i<=N;i++) suf[i]=1;
	static bitset<SIZEN> tmp;
	for(int i=1;i<=N;i++){
		suf[A[i]]=0;
		if(i>1) pre[N+1-A[i-1]]=1;
		tmp=(suf>>A[i])&(pre>>(N+1-A[i]));
		if(tmp.any()) return true;
	}
	return false;
}
void work(void){
	scanf("%d",&N);
	for(int i=1;i<=N;i++) scanf("%d",&A[i]);
	if(test()){
		printf("Y\n");
		return;
	}
	reverse(A+1,A+1+N);
	if(test()){
		printf("Y\n");
		return;
	}
	printf("N\n");
}
int main(){
	freopen("nt2011_sequence.in","r",stdin);
	freopen("nt2011_sequence.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--) work();
	return 0;
}

一份可以A的bool

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<bitset>
using namespace std;
using std::bitset;
const int MAXN=10001;
bool bit[MAXN];
int a;
inline void read(int &n)
{
	char c='+';int x=0;bool flag=0;
	while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
	while(c>='0'&&c<='9'){x=x*10+(c-48);c=getchar();}
	n=flag==1?-x:x;
}
int main()
{
	freopen("nt2011_sequence.in","r",stdin);
	freopen("nt2011_sequence.out","w",stdout);
	int T;
	read(T);
	while(T--)
	{
		memset(bit,0,sizeof(bit));
		//bit.reset();
		int n;
		read(n);
		bool flag=0;
		for(int i=1;i<=n;i++)
		{
			read(a);
			if(flag)continue;
			bit[a]=1;
			for(int j=a-1;j!=0;j--)
			{
				int k=a*2-j;
				if(k>n)continue;
				if(bit[j]^bit[k])
				{
					flag=1;
					break;
				}
			}
		}
		flag==1?printf("Y\n"):printf("N\n");
	}
	return 0;
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017-08-08 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

数据结构

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

数据结构

登录后参与评论

0 条评论

热度