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

★★   输入文件: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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

Gym 100952C&&2015 HIAST Collegiate Programming Contest C. Palindrome Again !!【字符串,模拟】

C. Palindrome Again !! time limit per test:1 second memory limit per test:64 meg...

2683
来自专栏人工智能LeadAI

TensorFlow从0到1丨第2篇:TensorFlow核心编程

上一篇Hello, TensorFlow!中的代码还未解释,本篇介绍TensorFlow核心编程的几个基本概念后,那些Python代码就很容易理解了。 与Ten...

4084
来自专栏数据结构与算法

BZOJ 3450: Tyvj1952 Easy

Description 某一天WJMZBMR在打osu~~~但是他太弱逼了,有些地方完全靠运气:( 我们来简化一下这个游戏的规则 有n次点击要做,成功了就是o...

2944
来自专栏数据结构与算法

P1789 【Mc生存】插火把

题目背景 初一党应该都知道...... 题目描述 话说有一天linyorson在Mc开了一个超平坦世界,他把这个世界看成一个n*n的方阵,现在他有m个火把和k个...

3665
来自专栏数据结构与算法

1225 八数码难题

1225 八数码难题  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 钻石 Diamond 题解  查看运行结果 题目描述 Descri...

2864
来自专栏Spark学习技巧

CountVectorizer

CountVectorizer 关于文本特征提取,前面一篇文章TF-IDF介绍了HashingTF,本文将再介绍一种Spark MLlib的API CountV...

6447
来自专栏数据结构与算法

7828:最大公约数与最小公倍数

7828:最大公约数与最小公倍数 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 两个正整数的最大公约数是G,最小公倍数是...

4638
来自专栏乐沙弥的世界

SQL, PL/SQL 之NUMBER数据类型

    NUMBER数据类型在Oracle中使用的较为广泛,可以存储零值,正负数,以及定长数,对于这个数据类型有个几个概念要搞清,否则容易搞混,下面给出具体描述...

952
来自专栏数据结构与算法

洛谷P1730 最小密度路径(floyd)

很显然的一个dp方程\(f[i][j][k][l]\)表示从\(i\)到\(j\)经过了\(k\)条边的最小权值

973
来自专栏小樱的经验随笔

1082 与7无关的数(思维题,巨坑)

1082 与7无关的数 题目来源:                 有道难题 基准时间限制:1 秒 空间限制:131072 KB 分值: 5        ...

3437

扫码关注云+社区

领取腾讯云代金券