题目可以转化为求\(AA\)的数量,设\(cnt1_x\)表示左端点为\(x\)的\(AA\)的数量,\(cnt2_x\)表示右端点为\(x\)的\(AA\)的数量,那么答案就是\(\sum cnt2_i \times cnt1_{i+1}\)
比较朴素的想法是枚举两个后缀然后哈希/SA判断这两个后缀的LCP是否足够长,能够拼成一个\(AA\)形式的串。然后这样就能拿95分???
考虑\(n\)比较大的时候优化枚举。我们对于所有\(len \in [1,\frac{N}{2}]\),在串中标记若干个关键点,两个相邻的关键点的距离为\(len\)。那么一个形如\(AA\)、长度为\(2 \times len\)的串会覆盖恰好\(2\)个关键点,而且两个关键点在覆盖了它的\(A\)串中的位置是一样的。
这意味着对于这两个关键点\(i,j = i+len\),\(min(LCP(suffix_i,suffix_j),len) + min(len,LCS(prefix_i , prefix_j)) > len\)(与\(len\)取\(min\)的原因是不能让覆盖范围超出了\(i,j\)两个点)。这给了我们需要求\(LCP\)与\(LCS\)的信息。SA与二分+Hash均可(反正这题不卡复杂度)。
当然做到上面我们仍然没有优化复杂度……
接下来,考虑算出了\(q=min(LCP(suffix_i,suffix_j),len)\)与\(p=min(len,LCS(prefix_i , prefix_j))\),这意味着串\(s_{[i-p+1 , i + q - 1]}\)与\(s_{[j-p+1,j+q-1]}\)是相等的,而\(j = i + len\)。那么我们随意取出\(s_{[i-p+1 , i + q - 1]}\)的一段长度为\(len\)的段,它的右边都一定紧接着一段长度为\(len\)并且与它相同的段。所以\(cnt1_{i-p+1,i+q-len}\)都会这一步中\(+1\),同时\(cnt2_{i-p+1+2 \times len , i + q + len}\)也会\(+1\)。使用差分数组维护,最后前缀和一下就可以统计答案了。
因为调和级数\(\sum \limits _{i=1}^n \frac{n}{i} < nlogn\),所以总复杂度为\(O(nlogn)\)(使用SA)或者\(O(nlog^2n)\)(使用二分+Hash)
#include<bits/stdc++.h>
#define ll long long
#define PLL pair < long long , long long >
//This code is written by Itst
using namespace std;
inline int read(){
int a = 0;
char c = getchar();
bool f = 0;
while(!isdigit(c) && c != EOF){
if(c == '-')
f = 1;
c = getchar();
}
if(c == EOF)
exit(0);
while(isdigit(c)){
a = a * 10 + c - 48;
c = getchar();
}
return f ? -a : a;
}
const int MAXN = 3e4 + 7 , seed = 131 , MOD1 = 1e9 + 7 , MOD2 = 1e9 + 9;
char s[MAXN];
int L , sum1[MAXN] , sum2[MAXN];
ll Hash[MAXN][2] , poww[MAXN][2] , ans;
inline void init_hash(){
for(int i = 1 ; i <= L ; ++i){
Hash[i][0] = (Hash[i - 1][0] * seed + s[i]) % MOD1;
Hash[i][1] = (Hash[i - 1][1] * seed + s[i]) % MOD2;
}
}
inline PLL get_hash(int l , int r){
return PLL((Hash[r][0] - Hash[l - 1][0] * poww[r - l + 1][0] % MOD1 + MOD1) % MOD1 , (Hash[r][1] - Hash[l - 1][1] * poww[r - l + 1][1] % MOD2 + MOD2) % MOD2);
}
inline int calc_LCP(int p , int q){
int l = 0 , r = min(q - p , L - q + 1);
while(l < r){
int mid = (l + r + 1) >> 1;
get_hash(p , p + mid - 1) == get_hash(q , q + mid - 1) ? l = mid : r = mid - 1;
}
return l;
}
inline int calc_LCS(int p , int q){
int L = 0 , R = min(q - p , p);
while(L < R){
int mid = (L + R + 1) >> 1;
get_hash(p - mid + 1 , p) == get_hash(q - mid + 1 , q) ? L = mid : R = mid - 1;
}
return L;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
//freopen("out","w",stdout);
#endif
poww[0][0] = poww[0][1] = 1;
for(int i = 1 ; i <= 3e4 ; ++i){
poww[i][0] = poww[i - 1][0] * seed % MOD1;
poww[i][1] = poww[i - 1][1] * seed % MOD2;
}
for(int T = read() ; T ; --T){
memset(sum1 , 0 , sizeof(sum1));
memset(sum2 , 0 , sizeof(sum2));
scanf("%s" , s + 1);
L = strlen(s + 1);
init_hash();
for(int i = 1 ; i < L ; ++i)
for(int j = 1 ; j + i <= L ; j += i){
int p = calc_LCS(j , j + i) , q = calc_LCP(j , j + i);
if(p + q - 1 >= i){
++sum1[j - p + 1];
--sum1[j + q - i + 1];
++sum2[j - p + 1 + 2 * i - 1];
--sum2[j + q + i];
}
}
for(int i = 1 ; i <= L ; ++i){
sum1[i] += sum1[i - 1];
sum2[i] += sum2[i - 1];
}
ans = 0;
for(int i = 1 ; i < L ; ++i)
ans += sum2[i] * sum1[i + 1];
cout << ans << endl;
}
return 0;
}
UOJ219 NOI2016 优秀的拆分 二分、字符串哈希的更多相关文章
-
BZOJ4650/UOJ219 [Noi2016]优秀的拆分
本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作. 本文作者:ljh2000 作者博客:http://www.cnblogs.com/ljh2000-jump/ ...
-
[UOJ#219][BZOJ4650][Noi2016]优秀的拆分
[UOJ#219][BZOJ4650][Noi2016]优秀的拆分 试题描述 如果一个字符串可以被拆分为 AABBAABB 的形式,其中 A 和 B 是任意非空字符串,则我们称该字符串的这种拆分是优秀 ...
-
[NOI2016]优秀的拆分(SA数组)
[NOI2016]优秀的拆分 题目描述 如果一个字符串可以被拆分为 \(AABB\) 的形式,其中 A和 B是任意非空字符串,则我们称该字符串的这种拆分是优秀的. 例如,对于字符串 \(aabaaba ...
-
题解-NOI2016 优秀的拆分
NOI2016 优秀的拆分 \(T\) 组测试数据.求字符串 \(s\) 的所有子串拆成 \(AABB\) 形式的方案总和. 数据范围:\(1\le T\le 10\),\(1\le n\le 3\c ...
-
[NOI2016]优秀的拆分&;&;BZOJ2119股市的预测
[NOI2016]优秀的拆分 https://www.lydsy.com/JudgeOnline/problem.php?id=4650 题解 如果我们能够统计出一个数组a,一个数组b,a[i]表示以 ...
-
luogu1117 [NOI2016]优秀的拆分
luogu1117 [NOI2016]优秀的拆分 https://www.luogu.org/problemnew/show/P1117 后缀数组我忘了. 此题哈希可解决95分(= =) 设\(l_i ...
-
【BZOJ4560】[NOI2016]优秀的拆分
[BZOJ4560][NOI2016]优秀的拆分 题面 bzoj 洛谷 题解 考虑一个形如\(AABB\)的串是由两个形如\(AA\)的串拼起来的 那么我们设 \(f[i]\):以位置\(i\)为结尾 ...
-
并不对劲的bzoj4650:loj2083:uoj219:p1117:[NOI2016]优秀的拆分
题目大意 "优秀的拆分"指将一个字符串拆分成AABB的形式 十次询问,每次给出一个字符串S(\(|S|\leq3*10^4\)),求它的所有子串的优秀的拆分的方案数之和 题解 此题 ...
-
[BZOJ]4650: [Noi2016]优秀的拆分
Time Limit: 30 Sec Memory Limit: 512 MB Description 如果一个字符串可以被拆分为 AABBAABB 的形式,其中 AA 和 BB 是任意非空字符串, ...
随机推荐
-
PHP中的全局变量global和$GLOBALS的区别
1.global Global的作用是定义全局变量,但是这个全局变量不是应用于整个网站,而是应用于当前页面,包括include或require的所有文件. 但是在函数体内定义的global变量,函数体 ...
-
OGRE的学习资源
本文介绍从哪儿开始学习OGRE(Object-Oriented Graphics Rendering Engine的简称,又叫做OGRE 3D),如何在网上找寻OGRE的学习资源. 首先是wikipe ...
-
HTML5 video 支持air play
< video src="/path/to/video.mp4" x-webkit-airplay="allow" preload controls> ...
-
jQuery中position()与offset()区别
使用jQuery获取元素位置时,我们会使用position()或offset()方法,两个方法都返回一个包含两个属性的对象-左边距和上边距,它们两个的不同点在于位置的相对点不同. 可以看看下边的图: ...
-
struts2漏洞原理及解决办法
1.原理 Struts2的核心是使用的webwork框架,处理action时通过调用底层的getter/setter方法来处理http的参数,它将每个http参数声明为一个ONGL(这里是ONGL的介 ...
-
Struts2配置文件讲解
解决在断网环境下,配置文件无提示的问题我们可以看到Struts.xml在断网的情况下,前面有一个叹号,这时,我们按alt+/ 没有提示,这是因为” http://struts.apache.org/d ...
-
HTML+CSS笔记 CSS中级 颜色&长度值
颜色值 在网页中的颜色设置是非常重要,有字体颜色(color).背景颜色(background-color).边框颜色(border)等,设置颜色的方法也有很多种: 1.英文命令颜色 语法: p{co ...
-
Egret学习笔记 (Egret打飞机-4.添加主角飞机和实现飞行效果)
今天继续写点击了开始之后,添加一个飞机到场景中,然后这个飞机的尾巴还在冒火的那种感觉 先拆解一下步骤 1.首先完成飞机容器的图片加载 2.然后把容器添加到场景中 3.然后实现动画 -首先,我们新建一个 ...
-
用Maven实现一个protobuf的Java例子
注:试验环境在Mac Idea环境下 1. 介绍Protocol Buffers Protocal Buffers(简称protobuf)是谷歌的一项技术,用于结构化的数据序列化.反序列化,常用于RP ...
-
Java并发编程(五)锁的使用(下)
显式锁 上篇讲了使用synchronized关键字来定义锁,其实Java除了使用这个关键字外还可以使用Lock接口及其实现的子类来定义锁,ReentrantLock类是Lock接口的一个实现,Reen ...