主题

主题

 
   

1283 等差子序列

原题:http://codevs.cn/problem/1283/

题目描述 Description

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

输入描述 Input Description

输入的第一行包含一个整数 T,表示组数。

 下接 T 组数据,每组第一行一个整数 N,每组第二行为一个 1 到 N 的排列, 数字两两之间用空格隔开。

输出描述 Output Description

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

样例输入 Sample Input

2

3

1 3 2

3

3 2 1

样例输出 Sample Output

N

Y

数据范围及提示 Data Size & Hint

对于5%的数据,N<=100,对于30%的数据,N<=1000,对于100%的数据,N<=10000,T<=7


个人解法:

第一篇题解精炼。本蒟就不再赘述,只是记录一下所做不多的几个字符串Hash题。

每读入一个数,可将1~n当前的出现状态表示成一个01串。

由于是排列,故一个数会在后面当且仅当前面没有出现。

假设读入x,则只需判断以第x位为对称中心,这个01串是否相同。

若存在前面为1后面为0,则后面为0的那个一定会在后面出现,三者构成了一个递增的等差数列,反之亦然。

把01串当成字符串,用线段树维护区间Hash值,每次判断Hash值是否相等即可。

由于单点修改区间查询,用的BIT。


代码如下:

https://code.csdn.net/snippets/2153438

 
 
评论
 
 
热度(1)