#C241120A. [NOI2016] 优秀的拆分

标签（Label）

• 动态规划
• 枚举
• 思维
• 二分

网址（Website）

P1117 [NOI2016] 优秀的拆分 - 洛谷

题目（Problem）

题目描述

如果一个字符串可以被拆分为 $\text{AABB}$ 的形式，其中 $\text{A}$ 和 $\text{B}$ 是任意非空字符串，则我们称该字符串的这种拆分是优秀的。

例如，对于字符串 $\texttt{aabaabaa}$ ，如果令 $\text{A}=\texttt{aab}$，$\text{B}=\texttt{a}$，我们就找到了这个字符串拆分成 $\text{AABB}$ 的一种方式。

一个字符串可能没有优秀的拆分，也可能存在不止一种优秀的拆分。

比如我们令 $\text{A}=\texttt{a}$，$\text{B}=\texttt{baa}$，也可以用 $\text{AABB}$ 表示出上述字符串；但是，字符串 $\texttt{abaabaa}$ 就没有优秀的拆分。

现在给出一个长度为 $n$ 的字符串 $S$，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。这里的子串是指字符串中连续的一段。

以下事项需要注意：

1. 出现在不同位置的相同子串，我们认为是不同的子串，它们的优秀拆分均会被记入答案。
2. 在一个拆分中，允许出现 $\text{A}=\text{B}$。例如 $\texttt{cccc}$ 存在拆分 $\text{A}=\text{B}=\texttt{c}$。
3. 字符串本身也是它的一个子串。

输入格式

每个输入文件包含多组数据。

输入文件的第一行只有一个整数 $T$，表示数据的组数。

接下来 $T$ 行，每行包含一个仅由英文小写字母构成的字符串 $S$，意义如题所述。

输出格式

输出 $T$ 行，每行包含一个整数，表示字符串 $S$ 所有子串的所有拆分中，总共有多少个是优秀的拆分。

样例 #1

样例输入 #1

none

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

样例输出 #1

none

3
5
4
7

提示

样例解释

我们用 $S[i, j]$ 表示字符串 $S$ 第 $i$ 个字符到第 $j$ 个字符的子串（从 $1$ 开始计数）。

第一组数据中，共有三个子串存在优秀的拆分：
$S[1,4]=\texttt{aabb}$，优秀的拆分为 $\text{A}=\texttt{a}$，$\text{B}=\texttt{b}$；
$S[3,6]=\texttt{bbbb}$，优秀的拆分为 $\text{A}=\texttt{b}$，$\text{B}=\texttt{b}$；
$S[1,6]=\texttt{aabbbb}$，优秀的拆分为 $\text{A}=\texttt{a}$，$\text{B}=\texttt{bb}$。
而剩下的子串不存在优秀的拆分，所以第一组数据的答案是 $3$ 。

第二组数据中，有两类，总共四个子串存在优秀的拆分：
对于子串 $S[1,4]=S[2,5]=S[3,6]=\texttt{cccc}$，它们优秀的拆分相同，均为 $\text{A}=\texttt{c}$，$\text{B}=\texttt{c}$，但由于这些子串位置不同，因此要计算三次；
对于子串 $S[1,6]=\texttt{cccccc}$，它优秀的拆分有两种：$\text{A}=\texttt{c}$，$\text{B}=\texttt{cc}$ 和 $\text{A}=\texttt{cc}$，$\text{B}=\texttt{c}$，它们是相同子串的不同拆分，也都要计入答案。
所以第二组数据的答案是 $3+2=5$。

第三组数据中，$S[1,8]$ 和 $S[4,11]$ 各有两种优秀的拆分，其中 $S[1,8]$ 是问题描述中的例子，所以答案是 $2+2=4$。

第四组数据中，$S[1,4]$，$S[6,11]$，$S[7,12]$，$S[2,11]$，$S[1,8]$ 各有一种优秀的拆分，$S[3,14]$ 有两种优秀的拆分，所以答案是 $5+2=7$。

数据范围

对于全部的测试点，保证 $1 \leq T \leq 10$。以下对数据的限制均是对于单组输入数据而言的，也就是说同一个测试点下的 $T$ 组数据均满足限制条件。

我们假定 $n$ 为字符串 $S$ 的长度，每个测试点的详细数据范围见下表：

测试点编号	$n \leq$	特殊性质
$1 \sim 2$	$300$	$S$ 中所有字符相同
$3 \sim 4$	$2,000$	$S$ 中所有字符相同
$5 \sim 6$	$10$
$7 \sim 8$	$20$
$9 \sim 10$	$30$
$11 \sim 12$	$50$
$13 \sim 14$	$100$
$15$	$200$
$16$	$300$
$17$	$500$
$18$	$1,000$
$19$	$2,000$
$20$	$30,000$

题解（Solution）

95分

考虑一个 $O(n^2)$ 的做法，看到这道题，很明显就会想到把 $AA$ 和 $BB$ 分开处理，实际发现我们直接记录 $f_i,g_i$ 分别表示左区间在 $i$ 的 $AA$ 和右区间在 $i$ 的 $BB$ ，那么最后的答案就是 $\sum_{i=1}^{n-1} g_i\times f_{i+1}$ ，暴力枚举每个区间，然后直接哈希判断即可。

时间复杂度 $O(Tn^2)$ 。

100分

乍一看这道题好像没有思路，研究一下从短的 $AA$ 段向长的递推的做法，发现很难做。考虑 $AA$ 段的特点以及性质，寻找从什么地方下手：

1. 前半段和后半段相等。这个性质我们在前面已经用过了，仔细思考后也想不出什么；
2. 如果已经存在 $AABB$ 段，那么这一段再和后面的 $CCDD$ 段还能拼接成一个更大的 $AABB$ 段。这个性质在这个题目中并不好用，我想过先找出最小的 $AABB$ 段，然后往长度更长的组合，但是由于起点不同且这些串可能重复，时间复杂度会退化到 $O(n^2)$ ，而且处理非常麻烦。
3. 起点和终点。上面已经用过这个性质。
4. 长度。考虑相同长度的串能组成什么，对于一段长为 $2i$ 区间，我们暴力枚举起点，并且计算 $f_i,g_i$ ，时间复杂度还是 $O(n^2)$ 。

这一番想下来，发现还是不知道该怎么做，我们再看到 $n$ 的值域——$n\le 30000$ ，这么小？那么时间复杂度应该是 $O(n\log^2 n)$ 的吧，要么就是把一个 $\log n$ 换成 $\ln n$ 。想到 $\ln n$ ，就自然会想到调和级数，根据上面的长度，的条件，我们考虑枚举长度 $len$ ，然后把长为 $n$ 的字符串分割成 $\frac{n}{len}$ 份，这样时间复杂度刚好是 $\ln n$ 的。

我们考虑固定关键点，每个点都在 $k\times len|k\in \mathbb{N}^*$ 的地方，枚举相邻的关键点 $p_1,p_2$ ，每次只计算经过这两个点的长为 $2\times len$ 的字符串 $AA$ ，容易发现每个 $A$ 串会经过一个关键点，我们令 $A_1$ 经过 $p_1$ ，$A_2$ 经过 $p_2$ ，根据 $A_1=A_2$ 的性质，那么他们在 $p_1$ 和 $p_2$ 分别向左向右相同长度对应的字符一定相同，形式化的，即 $\forall i \in[l,r],\ s_{p_1+i}=s_{p_2+i} | (r-l+1)\ge len \land l\in[-len+1,0]\land r\in[0,len-1]$ 。我们可以使用二分+哈希求出 $p_1,p_2$ 向左最多能有多少字符相同，设最多向左 $li$ ，便有 $s[p_1-li:p_1]=s[p_2-li:p_2]$ ，同理，我们求出向右最多有多少字符相同，记为 $ri$ ，那么满足条件的 $AA$ 区间就会在 $[p_1-li,p_2+ri]$ 这个范围内滑动，这个地方就可以使用差分处理了。

总结一下，这道题主要考验的就是对时间复杂度的分析以及抓住关键信息之后联想的能力，非常考验思维，总时间复杂度 $O(n\log n\ln n)$ 。

代码（Code）

95分

c

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
#define show(a,b) {For(i,1,n) cerr<<a[i]<<b;cerr<<'\n';}
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}template<typename G>
void write(G x){
	if(x<0) putchar('-'),write(-x);
	else if(x<=9) putchar(x+'0');
	else write(x/10), putchar(x%10+'0');
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 30123;
bool ST;

char s[N];
int n,ans;

namespace H{
	const int p1 = 1e9+97, b1 = 1333331;
	const int p2 = 998244991, b2 = 997;
	int fac1[N], pw1[N];
	int fac2[N], pw2[N];
	void init(){
		pw1[0]=1;For(i,1,N-5) pw1[i]=pw1[i-1]*b1%p1;
		pw2[0]=1;For(i,1,N-5) pw2[i]=pw2[i-1]*b2%p2;
	}
	void pre(){
		For(i,1,n) fac1[i] = (fac1[i-1]*b1 + s[i]-'a'+1)%p1;
		For(i,1,n) fac2[i] = (fac2[i-1]*b2 + s[i]-'a'+1)%p2;
	}
	inline int calc(int l,int r){
		int t1 = (fac1[r]-pw1[r-l+1]*fac1[l-1]%p1+p1)%p1;
		int t2 = (fac2[r]-pw2[r-l+1]*fac2[l-1]%p2+p2)%p2;
		return (t1<<31)+t2;
	}
}

int f[N],g[N];

void Solve(){
	scanf("%s",s+1), n=strlen(s+1);
	For(i,1,n) f[i]=g[i]=0;
	H::pre(),ans=0;
	
	For(i,1,n) for(int j=i+1,m=i;j<=n;j+=2,m++)
		if(H::calc(i,m) == H::calc(m+1,j)) f[i]++, g[j]++;
	
	For(i,1,n-1) ans += g[i]*f[i+1];
	write(ans), putchar('\n');
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int T = rd();double Tim = clock();
	H::init();while(T--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}

100分

c

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
#define show(a,b) {For(i,1,n) cerr<<a[i]<<b;cerr<<'\n';}
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}template<typename G>
void write(G x){
	if(x<0) putchar('-'),write(-x);
	else if(x<=9) putchar(x+'0');
	else write(x/10), putchar(x%10+'0');
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 301234;
bool ST;

char s[N];
int n,ans;

namespace H{
	const int p1 = 1e9+97, b1 = 1333331;
	const int p2 = 998244991, b2 = 997;
	int fac1[N], pw1[N];
	int fac2[N], pw2[N];
	void init(){
		pw1[0]=1;For(i,1,N-5) pw1[i]=pw1[i-1]*b1%p1;
		pw2[0]=1;For(i,1,N-5) pw2[i]=pw2[i-1]*b2%p2;
	}
	void pre(){
		For(i,1,n) fac1[i] = (fac1[i-1]*b1 + s[i]-'a'+1)%p1;
		For(i,1,n) fac2[i] = (fac2[i-1]*b2 + s[i]-'a'+1)%p2;
	}
	inline int calc(int l,int r){
		int t1 = (fac1[r]-pw1[r-l+1]*fac1[l-1]%p1+p1)%p1;
		int t2 = (fac2[r]-pw2[r-l+1]*fac2[l-1]%p2+p2)%p2;
		return (t1<<31)+t2;
	}
}inline int calc(int l,int r){return H::calc(l,r);}
inline void add(int *c,int l,int r){c[l]+=1,c[r+1]-=1;}

int f[N],g[N];

void Solve(){
	scanf("%s",s+1), n=strlen(s+1);
	For(i,1,n) f[i]=g[i]=0;
	H::pre(),ans=0;
	
	For(i,1,n) for(int p1=i,p2=i<<1;p2<=n;p1+=i,p2+=i){
		if(s[p1] ^ s[p2]) continue;
		int li=0,ri=0;
		{
			int l=0,r=i-1,mid;
			while(l<=r){
				mid = (l+r)>>1;
				if(calc(p1-mid,p1)==calc(p2-mid,p2)) l=mid+1,li=mid;
				else r=mid-1;
			}
		}{
			int l=0,r=min(i-1,n-p2),mid;
			while(l<=r){
				mid = (l+r)>>1;
				if(calc(p1,p1+mid)==calc(p2,p2+mid)) l=mid+1,ri=mid;
				else r=mid-1;
			}
		}
		if(li+ri+1 < i) continue;
		add(f, p1-li, p1+ri-i+1);
		add(g, p2-li+i-1, p2+ri);
	}
	
	For(i,1,n) f[i] += f[i-1], g[i] += g[i-1];
	For(i,1,n-1) ans += g[i]*f[i+1];
	write(ans), putchar('\n');
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int T = rd();double Tim = clock();
	H::init();while(T--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}