等差子序列（sequence）
发布时间
阅读量：
阅读量
等差子序列（sequence）
题目描述
考虑一个从1到N的排列{Ai}。研究是否存在满足p1, p2, ..., pLen为严格递增序列，并且其长度至少为3的一组索引值（其中p_len表示p的下标），使得对应的项Ap₁, Ap₂, ..., Ap_Len构成一个等差数列。
输入
输入的第一行包含一个整数T，表示组数。
随后从T组数据源开始读取数据。每个数据块的第一行包含一个整数N。第二行是一个1到N的排列序列，请注意数字之间以空格分隔。
输出
对于每组数据，如果存在一个等差子序列，则输出一行“Y”，否则输出一行“N”。
样例输入
样例输出
提示
【数据说明】
对于5%的数据，N<=100
对于30%的数据，N<=1000
对于100%的数据，N<=10000，T<=7
solution
首先只要有3个数满足，那么就行了
我们枚举中间的数ai
我们可以记录每一个数值是否出现过：记为p
如果p是一个以a[i]为对称轴的回文串，那么就是不合法的。
也就是a[i-x],a[i+x]出现状况相同
这个可以用哈希实现
现在我们要维护哈希值，支持修改，区间查询
树状数组啦
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 10005
#define ll unsigned long long
#define p 1000000007
using namespace std;
int T,n,a[maxn];
ll ha[maxn],hb[maxn],po[maxn];
void cle(){
for(int i=1;i<=n;i++)ha[i]=hb[i]=0;
}
void add_a(int i,ll v){
for(;i<=n;i+=i&-i)ha[i]+=v;
}
void add_b(int i,ll v){
for(;i<=n;i+=i&-i)hb[i]+=v;
}
ll ask_a(int i){
ll sum=0;for(;i;i-=i&-i)sum+=ha[i];
return sum;
}
ll ask_b(int i){
ll sum=0;for(;i;i-=i&-i)sum+=hb[i];
return sum;
}
int main()
{
cin>>T;
while(T--){
cle();
cin>>n;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
po[0]=1;for(int i=1;i<=n;i++)po[i]=po[i-1]*p;
bool f=0;
//for(int i=1;i<=n;i++)add_b(a[i],po[n-a[i]+1]);
for(int i=1;i<=n;i++){
add_a(a[i],po[a[i]]);add_b(a[i],po[n-a[i]+1]);
int M=min(a[i],n-a[i]+1);
//cout<<"i "<<i<<' '<<a[i]<<' '<<M<<endl;
ll t1=ask_a(a[i])-ask_a(a[i]-M);
ll t2=ask_b(a[i]+M-1)-ask_b(a[i]-1);
if(a[i]<n-a[i]+1)t1=t1*po[n-a[i]+1-a[i]];
else t2=t2*po[a[i]-(n-a[i]+1)];
//cout<<t1<<' '<<t2<<endl;
if(t1!=t2){f=1;break;}
}
if(f)puts("Y");else puts("N");
}
return 0;
}全部评论 (0)
还没有任何评论哟~