感觉智商莫名其妙的就变低了……写这题的时候死活想不出来……
做法其实不难……
题目要求形如ABA的串的个数,我们可以枚举A的长度,利用标记关键点的方法统计答案。设枚举到的答案为k,每k个点标记一个关键点,显然每个A只会恰好包含一个关键点,那么我们枚举每个关键点$i$,求一下它和$i+m+l$前后各能匹配到哪儿,显然答案应该加上能匹配的长度。注意为了防止重复计算需要把LCP和LCS(最长公共后缀)对$k$取min。
求LCP和LCS我是用hash写的,一开始base选的2147483647然后WA了,换成123456789和233333333倒是都能过……什么鬼……
/**************************************************************
Problem: 2119
User: hzoier
Language: C++
Result: Accepted
Time:3664 ms
Memory:1800 kb
****************************************************************/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
const unsigned long long base=233333333ll;
unsigned long long gethash(int,int);
int LCP(int,int);
int LCS(int,int);
unsigned long long h[maxn],pw[maxn];
long long ans=;
int n,m,a[maxn];
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<n;i++)scanf("%d",&a[i]);
for(int i=n;i;i--)a[i]-=a[i-];
n--;
for(int i=n;i;i--)h[i]=h[i+]*base+a[i]+base+1ull;
pw[]=;
for(int i=;i<=n;i++)pw[i]=pw[i-]*base;
for(int l=;m+(l<<)<=n;l++){
for(int i=l;i+m+l<=n;i+=l){
int tmpa=min(LCS(i,i+m+l),l),tmpb=min(LCP(i,i+m+l),l);
if(tmpa+tmpb>l)ans+=tmpa+tmpb-l;
}
}
printf("%lld",ans);
return ;
}
inline unsigned long long gethash(int x,int l){return h[x]-h[x+l]*pw[l];}
int LCP(int x,int y){
if(x>y)swap(x,y);
int L=,R=n-y+;
while(L<=R){
int M=(L+R)>>;
if(gethash(x,M)==gethash(y,M))L=M+;
else R=M-;
}
return R;
}
int LCS(int x,int y){
if(x>y)swap(x,y);
int L=,R=x;
while(L<=R){
int M=(L+R)>>;
if(gethash(x-M+,M)==gethash(y-M+,M))L=M+;
else R=M-;
}
return R;
}
bzoj2119 股市的预测的更多相关文章
-
[NOI2016]优秀的拆分&;&;BZOJ2119股市的预测
[NOI2016]优秀的拆分 https://www.lydsy.com/JudgeOnline/problem.php?id=4650 题解 如果我们能够统计出一个数组a,一个数组b,a[i]表示以 ...
-
BZOJ2119 股市的预测 字符串 SA ST表
原文链接https://www.cnblogs.com/zhouzhendong/p/9069171.html 题目传送门 - BZOJ2119 题意 给定一个股票连续$n$个时间点的价位,问有多少段 ...
-
BZOJ2119: 股市的预测(后缀数组)
Description 墨墨的妈妈热爱炒股,她要求墨墨为她编写一个软件,预测某只股票未来的走势.股票折线图是研究股票的必备工 具,它通过一张时间与股票的价位的函数图像清晰地展示了股票的走势情况.经过长 ...
-
bzoj千题计划312:bzoj2119: 股市的预测(后缀数组+st表)
https://www.lydsy.com/JudgeOnline/problem.php?id=2119 题意:将给定数组差分后,求ABA形式的字串个数,要求|B|=m,|A|>0 1.后缀数 ...
-
【BZOJ2119】股市的预测 后缀数组+分块
[BZOJ2119]股市的预测 Description 墨墨的妈妈热爱炒股,她要求墨墨为她编写一个软件,预测某只股票未来的走势.股票折线图是研究股票的必备工具,它通过一张时间与股票的价位的函数图像清晰 ...
-
【BZOJ-2119】股市的预测 后缀数组
2119: 股市的预测 Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 334 Solved: 154[Submit][Status][Discuss ...
-
BZOJ 2119: 股市的预测 [后缀数组 ST表]
2119: 股市的预测 Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 331 Solved: 153[Submit][Status][Discuss ...
-
【BZOJ 2119】 2119: 股市的预测 (后缀数组+分块+RMQ)
2119: 股市的预测 Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 404 Solved: 188 Description 墨墨的妈妈热爱炒股,她 ...
-
BZOJ 2119: 股市的预测 SA
2119: 股市的预测 Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 434 Solved: 200[Submit][Status][Discuss ...
随机推荐
-
Spring缓存机制的理解
在spring缓存机制中,包括了两个方面的缓存操作:1.缓存某个方法返回的结果:2.在某个方法执行前或后清空缓存. 下面写两个类来模拟Spring的缓存机制: package com.sin90lzc ...
-
C++中重定义的问题——问题的实质是声明和定义的关系以及分离式编译的原理
这里的问题实质是我们在头文件中直接定义全局变量或者函数,却分别在主函数和对应的cpp文件中包含了两次,于是在编译的时候这个变量或者函数被定义了两次,问题就出现了,因此,我们应该形成一种编码风格,即: ...
-
数据分析:.Net程序员该如何选择?
上文我介绍了用.Net实现的拉勾爬虫,可全站采集,其中.Net和C#(不区分)的数据爬取开始的早,全国主要城市都有一定数量的分布,加上有了近期其他相似技术类别的数据进行横向比较,可以得到比较合理的推测 ...
-
初探网络编程--TCP套接字编程演示
今天看了一下<计算机网络:自顶向下方法>,也就是计算机网络的教材的应用层一章,决定实现以下后面的Java C/S应用程序的例子,用来演示TCP和UDP套接字编程. 程序流程如下: 1.一台 ...
-
翻译:Knockout 快速上手 - 2: 安装 knockoutJS
只需要五个简单的步骤,就可以做好使用 Knockout 开发的准备! 第一步 我们需要什么? 最低限度,为了完成后面的教程,你需要如下的准备 Web 浏览器 文本编辑器 你的电脑上大约 2M 的磁盘空 ...
-
SQL Server中取两个表的交集,并集和差集
在项目中遇到要取两个表差集的情况 假设有两个表tblNZPostCodes, NZPostcode 两个表中存储的都是新西兰的post code信息,字段一致,只是数据上有所差异. 1. Union ...
-
myeclipse 右键 Add Struts... 页面报404 错误
网上试了很多种方法都不对,结果老师两下点出来了 我的改正方法是: 将WebRoot/WEB-INF/web.xml中的 <url-pattern>/*</url-pattern> ...
-
【简译】JavaScript闭包导致的闭合变量问题以及解决方法
本文是翻译此文 预先阅读此文:闭合循环变量时被认为有害的(closing over the loop variable considered harmful) JavaScript也有同样的问题.考虑 ...
-
sublime远程连接到linux主机
sublime远程连接到linux主机 sublime远程连接到linux主机 微信开发,直接使用sublime的sftp功能修改wx_sample.php 1.为sublime安装安装包管理插件Pa ...
-
python read txt file
refer to: http://www.jianshu.com/p/d8168034917c http://www.liaoxuefeng.com/wiki/001374738125095c955c ...