专栏文章

题解：P10976 统计重复个数

BBinah_cyc
P10976题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miphr818
此快照首次捕获于
2025/12/03 12:12
3 个月前
此快照最后确认于
2025/12/03 12:12
3 个月前
查看原文
大家写的怎么都是同一种做法？我来给出一个另类的倍增方法。
以下所有的字符串下标均从 00 开始。
第一步是转化题意，[[s2,n2],m]=[s2,n2×m][[s2,n2],m]=[s2,n2 \times m]，找最大的 mm 就是找最大的 tt 使得 [s2,t][s2,t] 能由 [s1,n1][s1,n_1] 获得，mm 就是 ⌊tn2⌋\lfloor {t \over n_2} \rfloor。
我们以 s2s_2 为基准，设 nxtinxt_i 表示从 s2s_2 的第 ii 个字符开始，在 s1s_1 中匹配，匹配完整个串后匹配到了第几位，valival_i 表示在这个过程中匹配出了几个 s2s_2。注意，第一段不完整的代表前面有一段已经匹配好的，所以应当计入答案。
直接说可能不是很好理解，我来给个例子。
设 s1=cycycycycs_1=\texttt{cycycycyc}，s2=cycs_2=\texttt{cyc}。
nxt0=1nxt_0=1，val0=2val_0=2，具体分配方式如下。cycycycyc\color{red}\texttt{cyc}\color{black}\texttt{y}\color{red}\texttt{cyc}\color{black}\texttt{y}\color{red}\texttt{c}
nxt1=1nxt_1=1，val1=2val_1=2，具体分配方式如下。cycycycyc\color{black}\texttt{c}\color{red}\texttt{yc}\color{black}\texttt{y}\color{red}\texttt{cyc}\color{black}\texttt{y}\color{red}\texttt{c}
nxt2=0nxt_2=0，val2=3val_2=3，具体分配方式如下。cycycycyc\color{red}\texttt{c}\color{black}\texttt{y}\color{red}\texttt{cyc}\color{black}\texttt{y}\color{red}\texttt{cyc}
这样就可以快速的将一个 s1s_1 与 s2s_2 匹配了，只需要匹配 n1n_1 次就能得出答案。
但是它还是不够快，因此考虑倍增优化。套路的，设 dpi,jdp_{i,j} 表示从 s2s_2 的第 jj 个字符开始，在 s1s_1 中匹配完 2i2^i 个串后匹配到了第几位，curi,jcur_{i,j} 表示在这个过程中匹配出了几个完整的 s2s_2。
转移方程就是把它劈成两半分别计算。
dpi,j=dpi−1,(dpi−1,j),curi,j=curi−1,j+curi−1,(dpi−1,j)dp_{i,j}=dp_{i-1,(dp_{i-1,j})},cur_{i,j}=cur_{i-1,j}+cur_{i-1,(dp_{i-1,j})}
然后对 n1n_1 进行二进制拆分，对每个二进制位进行计算。
讲的可能有点朦胧，可以看看代码。
CPP
// Problem: P10976 统计重复个数
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10976
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// Author: Binah_cyc

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N=105;
int n1,n2;
string s1,s2;
int nxt[N],val[N];
int dp[25][N],cur[25][N];
main()
{
	cin.tie(0)->sync_with_stdio(false);
	while(cin>>s2>>n2>>s1>>n1)
	{
		for(int i=0;i<s2.length();i++)
		{
			int it=i;
			for(int j=0;j<s1.length();j++)//匹配字符串
			{
				if(s1[j]==s2[it])
				{
					it++;
					if(it==s2.length()) val[i]++,it=0;//匹配了一整个字符串
				}
			}
			nxt[i]=it;
		}
		for(int i=0;i<s2.length();i++)
			dp[0][i]=nxt[i],cur[0][i]=val[i];
		for(int i=1;i<=20;i++)
		{
			for(int j=0;j<s2.length();j++)
			{
				dp[i][j]=dp[i-1][dp[i-1][j]],cur[i][j]=cur[i-1][j]+cur[i-1][dp[i-1][j]];//正常倍增
			}
		}
		int now=0,num=0;
		for(int i=20;i>=0;i--)//从高位到低位考虑
		{
			if((1<<i)<=n1)//n1的这一位有值
			{
				n1-=(1<<i),num+=cur[i][now],now=dp[i][now];
			}
		}
		cout<<num/n2<<'\n';
		for(int i=0;i<s2.length();i++) val[i]=nxt[i]=0;//多测要清空
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...