洛谷 P2757 [国家集训队]等差子序列 解题报告
2024-08-28 17:18:08
P2757 [国家集训队]等差子序列
题目描述
给一个\(1\)到\(N\)的排列\(\{A_i\}\),询问是否存在
\[1 \le p_1<p_2<p_3<p_4<p_5<…<p_{Len} \le N (Len \ge 3)
\]
\]
使得\(A_{p_1},A_{p_2},A_{p_3},\cdots,Ap_{Len}\)是一个等差序列。
输入输出格式
输入格式:
输入的第一行包含一个整数\(T\),表示组数。
下接\(T\)组数据,每组第一行一个整数\(N\),每组第二行为一个\(1\)到\(N\)的排列,数字两两之间用空格隔开。
输出格式:
对于每组数据,如果存在一个等差子序列,则输出一行“\(Y\)”,否则输出一行“\(N\)”。
说明
对于\(5\%\)的数据,\(N\le 100\)
对于\(30\%\)的数据,\(N\le 1000\)
对于\(100\%\)的数据,\(N\le 10000,T\le 7\)
思路真不错啊
显然我们只需要考虑\(len=3\)的情况
对于一段连续的位置\([l,r]\),我们定义一端长为\(n\)的\(01\)串表示这个位置上的数的选取集合
比如区间\([l,r]\)的数字分别为\(2351\),而\(n=6\),那么选取集合为\(111010\)
这样是从小到大排列的,我们同样定义一个从大到小排列的。这样刚刚的例子就是\(010111\)了
考虑枚举等差中项,如果当前枚举到的位置为\(i\)
那么如果\(\tt{Ta}\)左边区间的集合从小到大排列的和从大到小排列的相应长度的位置串是相等的,那么它就不可能作为等差中项。
维护\(01\)串相等可以使用\(\tt{bitset}\)可以通过此题。
也可以使用\(Hash+\text{树状数组}\)维护
Code:
#include <cstdio>
#include <cstring>
#define ll long long
const int N=1e4;
const ll mod=1e9+7;
ll po[N+10],s[2][N+10];
int n;
void add(int typ,int x)
{
for(int i=x;i<=n;i+=i&-i)
(s[typ][i]+=po[x])%=mod;
}
ll query(int typ,int x)
{
ll sum=0;
while(x) (sum+=s[typ][x])%=mod,x-=x&-x;
return sum;
}
int main()
{
po[0]=1;int T;
for(int i=1;i<=N;i++) po[i]=po[i-1]*2%mod;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
memset(s,0,sizeof(s));
int flag=0;ll c1,c2;
for(int a,i=1;i<=n;i++)
{
scanf("%d",&a);
int len1=a-1,len2=n-a;
if(len1>len2)//左边多了
{
int d=len1-len2;
c1=query(0,len1)-query(0,d);
(c1+=mod)%=mod;
c2=query(1,len2)*po[d]%mod;
}
else
{
int d=len2-len1;
c1=query(0,len1)*po[d]%mod;
c2=query(1,len2)-query(1,d);
(c2+=mod)%=mod;
}
if(c1!=c2) flag=1;
add(0,a);
add(1,len2+1);
}
if(flag) puts("Y");
else puts("N");
}
return 0;
}
2018.11.7
最新文章
- Match:Power Strings(POJ 2406)
- Uva674 完全背包求方案数
- 字符串hash - POJ 3461 Oulipo
- GT-n8000平板开机密码忘记 解决办法
- 【标题】一本帮你提高Excel办公效率的VBA书
- Ubuntu 13.10 安装Qt5
- hive metastore异常 org.apache.thrift.protocol.TProtocolException: Missing version in readMessageBegin, old client
- linux命令之chown命令
- java_annotation_02
- [HeadFirst-HTMLCSS入门][第十一章布局排版]
- JSON互转
- [HDUOJ1312]Red And Black (经典的DFS)
- 8.23.1 IO-输入输出流概念
- 解决 c3p0报错 Establishing SSL connection without server&#39;s identity verification is not recommended
- 构建SpringBoot第一个Demo
- http请求415错误Unsupported Media Type
- JS事件(五)内存与性能
- mac docker环境搭建mysql主从同步服务器
- 模拟实现简单ATM功能
- flask模板,路由,消息提示,异常处理