2124: 等差子序列
- Time Limit: 3 Sec Memory Limit: 259 MB
- Submit: 2354 Solved: 826
- [Submit][Status][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
- Source
思路: 题目即是问有没有等于 3 的等差数列. 最直观的解决就是从前往后扫, 假设扫到 X 了, 我们去看关于 X 对称的数, 是否其出现的情况不相同, vis[X+i]!=vis[X-i].
我们可以用两个 hash 来维护两个方向的 01 字符串, 表示出现情况. 这里野可以用 bitset 来解决.
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn=20010;
- int a[maxn],N;
- bool check()
- {
- bitset<maxn>s,t;
- for(int i=1;i<=N;i++) t[i]=1;
- for(int i=1;i<=N;i++){
- t[a[i]]=0;
- if(((s>>(20001-a[i]*2))&t).any()) return true;
- s[20001-a[i]]=1;
- }
- return false;
- }
- int main()
- {
- int T; scanf("%d",&T);
- while(T--){
- scanf("%d",&N);
- for(int i=1;i<=N;i++) scanf("%d",&a[i]);
- if(check()) puts("Y");
- else puts("N");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2869880.html