【bzoj2124】等差子序列 STL-bitset
2024-08-29 11:18:23
题目描述
给一个1到N的排列{Ai},询问是否存在1<=p1<p2<p3<p4<p5<…<pLen<=N (Len>=3),使得Ap1,Ap2,Ap3,…ApLen是一个等差序列。
输入
输入的第一行包含一个整数T,表示组数。
下接T组数据,每组第一行一个整数N,每组第二行为一个1到N的排列,数字两两之间用空格隔开。
N<=10000,T<=7
输出
对于每组数据,如果存在一个等差子序列,则输出一行“Y”,否则输出一行“N”。
样例输入
2
3
1 3 2
3
3 2 1
样例输出
N
Y
题解
STL-bitset
首先选出的长度一定为3(长度多了没有意义,只取前3项即可)。
然后枚举中间位置的数,转化为是否存在$i+k=2j$,其中$i$在$j$之前出现,$k$在$j$之后出现。
考虑暴力怎么求:对于前面和后面各开一个桶,暴力枚举。
由于给出的是一个全排列,因此每个数只出现1次,相当于开的桶是bool类型的。我们可以使用bitset优化。至于如何判断是否存在两个数的和为定值,可以维护$20000-i$和$k$,如果存在$i+k=2j$,那么$(20000-i)=k+(20000-2j)$。所以维护左边的$20000-i$和右边的$k$,如果把右面左移$20000-2j$后与$20000-i$的与不为0则存在。
时间复杂度$O(\frac{Tn^2}{16})$,分母不是32是因为bitset的范围需要开到2W。
貌似正解是分段哈希。
#include <cstdio>
#include <bitset>
using namespace std;
int v[10010];
int main()
{
int T;
scanf("%d" , &T);
while(T -- )
{
bitset<20010> b , c;
int n , i;
scanf("%d" , &n);
for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &v[i]) , c[v[i]] = 1;
for(i = 1 ; i <= n ; i ++ )
{
c[v[i]] = 0;
if(((b >> (20000 - (v[i] << 1))) & c).any())
{
puts("Y");
break;
}
b[20000 - v[i]] = 1;
}
if(i > n) puts("N");
}
return 0;
}
最新文章
- 给zabbix穿一件漂亮的衣服
- IOS开发基础知识--碎片37
- 最近360和adsafe软件有冲突
- mysql+mybatis 插入可递增字段库表操作
- 【JDBC】预编译SQL与防注入式攻击
- 细说javascript 中的 window.open() 参数设置
- AppUse学习笔记
- 2016年1月编程语言排行榜:Java荣获2015年度冠军
- 嵌入式 现已发展为 IT行业的主流——高薪,且人才缺乏
- 1692: [Usaco2007 Dec]队列变换|后缀数组|贪心
- 审核Memcrashed Drdos攻击代码
- C# 大数组赋值给小数组,小数组赋值给大数组
- Java Socket通信代码片
- 使用 OpenCV 与 Face++ 人脸识别
- 3.Lucene3.x API分析,Director 索引操作目录,Document,分词器
- 应对WannaCry勒索危机之关闭445端口等危险端口——以本人Windows7系统为例
- HDU 5988 Coding Contest(浮点数费用流)
- MySQL 的 DISTINCT 应用于2列时
- 如何将div中的内容设置为空同时还要保留div本身
- java 对象和基本数据类型 “==”区别