首页 > 代码库 > [BZOJ2124]等差子序列
[BZOJ2124]等差子序列
[BZOJ2124]等差子序列
试题描述
给一个1到N的排列{Ai},询问是否存在1<=p_1<p_2<...<p_Len,Len>=3),使得Ap_1,Ap_2,Ap_3,…Ap_Len是一个等差序列。
输入
输入的第一行包含一个整数T,表示组数。下接T组数据,每组第一行一个整数N,每组第二行为一个1到N的排列,数字两两之间用空格隔开。
输出
对于每组数据,如果存在一个等差子序列,则输出一行“Y”,否则输出一行“N”。
输入示例
2 3 1 3 2 3 3 2 1
输出示例
N
Y
数据规模及约定
对于100%的数据,N<=10000,T<=7
题解
注意输入的是一个排列,所以不会有重复的数字,也就是它出现了一次之后就不会再出现了。
于是我们考虑从前往后加入每个数;令 B[i] 表示数字 i 当前是否被加入,当加入数字 x 时,我们把 B[x] 设为 1,然后看一下 B 数组中以 x 为中心的极长子区间是不是一个回文串,如果不是则说明找到了一个长度为 3 的等差数列。为什么呢?考虑 x 左边的某个数 y 如果是 0(即它还没有被插入,也就是它是在原排列中 x 的后面出现的),那么只要 2x - y 的位置是 1(即它在 x 的前面出现),那么 {y, x, 2x - y} 就构成了一个等差数列。
那么我们维护 B 数组的区间正反哈希值就好了。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <algorithm> using namespace std; int read() { int x = 0, f = 1; char c = getchar(); while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = getchar(); } return x * f; } #define maxn 10010 #define UL unsigned long long int n; UL h1[maxn<<2], h2[maxn<<2], idx[maxn]; UL query1(int o, int l, int r, int ql, int qr) { if(ql > qr) return 0; if(ql <= l && r <= qr) return h1[o]; int mid = l + r >> 1, lc = o << 1, rc = lc | 1; UL ans = 0; if(ql <= mid) ans = query1(lc, l, mid, ql, qr); if(qr > mid) ans = ans * idx[min(qr,r)-mid] + query1(rc, mid + 1, r, ql, qr); return ans; } UL query2(int o, int l, int r, int ql, int qr) { if(ql > qr) return 0; if(ql <= l && r <= qr) return h2[o]; int mid = l + r >> 1, lc = o << 1, rc = lc | 1; UL ans = 0; if(qr > mid) ans = query2(rc, mid + 1, r, ql, qr); if(ql <= mid) ans = ans * idx[mid-max(ql,l)+1] + query2(lc, l, mid, ql, qr); return ans; } void update(int o, int l, int r, int x) { if(l == r) h1[o] = h2[o] = 1; else { int mid = l + r >> 1, lc = o << 1, rc = lc | 1; if(x <= mid) update(lc, l, mid, x); else update(rc, mid + 1, r, x); h1[o] = h1[lc] * idx[r-mid] + h1[rc]; h2[o] = h2[rc] * idx[mid-l+1] + h2[lc]; } return ; } int main() { idx[0] = 1; for(int i = 1; i < maxn; i++) idx[i] = idx[i-1] * 233; int T = read(); while(T--) { n = read(); memset(h1, 0, sizeof(h1)); memset(h2, 0, sizeof(h2)); bool ok = 0; for(int i = 1; i <= n; i++) { int x = read(), l = x - 1, r = n - x; l = r = min(l, r); if(query1(1, 1, n, x - l, x - 1) != query2(1, 1, n, x + 1, x + r)) ok = 1; update(1, 1, n, x); } puts(ok ? "Y" : "N"); } return 0; }
[BZOJ2124]等差子序列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。