等差子序列
- Time Limit: 3 Sec Memory Limit: 259 MB
- Submit: 1919 Solved: 713
- [Submit https://www.lydsy.com/JudgeOnline/submitpage.php?id=2124][Status https://www.lydsy.com/JudgeOnline/problemstatus.php?id=2124 ][Discuss https://www.lydsy.com/JudgeOnline/bbs.php?id=2124 ]
- Description
给一个 1 到 N 的排列 {Ai}, 询问是否存在 1<=p1<p2<p3<p4<p5<...<pLen<=N (Len>=3),
使得 Ap1,Ap2,Ap3,...ApLen 是一个等差序列.
Input
输入的第一行包含一个整数 T, 表示组数.
下接 T 组数据, 每组第一行一个整数 N, 每组第二行为一个 1 到 N 的排列, 数字两两之间用空格隔开.
- N<=10000,T<=7
- Output
对于每组数据, 如果存在一个等差子序列, 则输出一行 "Y", 否则输出一行 "N".
- Sample Input
- 2
- 3
- 1 3 2
- 3
- 3 2 1
- Sample Output
- N
- Y
- HINT
因此, 我们构造一个辅助数组 b, 其中 x 如果出现过, 那么 b[x]=1; 否则 b[x]=0. 因此如果 x 满足条件, 那么必然存在一个数 y 使得 b[x-y]!=b[x+y]; 然后我们发现如果把 b 看成一个字符串, 那么实际上就是判断以 x 为中心的极长字符串是否是回文串, 如果不是那么显然存在 y 使得 b[x-y]!=b[x+y], 那么就可以输出'Y'. 快速的字符串比较不妨使用 hash, 然后因为需要修改那么就用两个树状数组分别维护它所在区间正着和倒着的 hash 值即可.
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #define ll long long
- #define mod 1000000007
- #define N 10005
- using namespace std;
- int n,a[N],pw[N];
- struct bit_node{
- int c[N];
- void clr(){ memset(c,0,sizeof(c)); }
- void add(int x){
- int i; for (i=x; i<=n; i+=i&-i) c[i]=(c[i]+pw[i-x])%mod;
- }
- int getsum(int x){
- int i,t=0; for (i=x; i; i^=i&-i) t=((ll)c[i]*pw[x-i]+t)%mod;
- return t;
- }
- int qry(int x,int y){
- int p=getsum(x-1),q=getsum(y);
- return (q-(ll)p*pw[y-x+1]%mod+mod)%mod;
- }
- }bit1,bit2;
- int main(){
- int cas,i; scanf("%d",&cas);
- pw[0]=1; for (i=1; i<=10000; i++) pw[i]=(ll)pw[i-1]*12347%mod;
- while (cas--){
- scanf("%d",&n); int x;
- for (i=1; i<=n; i++) scanf("%d",&a[i]);
- bit1.clr(); bit2.clr();
- for (i=1; i<=n; i++){
- x=min(a[i]-1,n-a[i]);
- if (x && bit1.qry(a[i]-x,a[i]-1)!=bit2.qry(n-a[i]-x+1,n-a[i])) break;
- bit1.add(a[i]); bit2.add(n-a[i]+1);
- }
- puts((i>n)?"N":"Y");
- }
- }
来源: http://www.bubuko.com/infodetail-2563171.html