当前位置:网站首页>NOIP2020正式赛 字符串匹配 (string)题解

NOIP2020正式赛 字符串匹配 (string)题解

2020-12-17 14:10:01 osc_8o71811p

在这里插入图片描述
考场上无限接近正解
84pts的想法比较显然(虽说我这个菜逼想了近1h)
枚举AB整块位置,以及块的长度,剩下的是C,然后根据C有多少出现次数为奇数的字母(后缀预处理)来确定A有多少划分方案(边枚举边将目前的A有多少出现次数为奇数的字母扔进树状数组),将所有方案加起来就是答案
这样的时间复杂度到底多少?
考场上分析错了,以为是 O ( T n l o g 2 n ) O(Tnlog^2n) O(Tnlog2n)导致没有做出正解
事实上,A拥有的出现次数为奇数的字母不可能超过26个,所以时间复杂度是 O ( T n l o g n l o g 26 ) O(Tn log n log 26) O(Tnlognlog26)
5亿左右的复杂度不能过,我们可以将 l o g n log n logn l o g 26 log 26 log26分开
为什么要用树状数组?直接循环更新呀!
循环更新可以在枚举AB整块位置 O T ( 26 n ) OT(26n) OT(26n)的完成
询问则是 O ( T n l o g n ) O(Tn log n) O(Tnlogn)的,这样加起来,卡卡常,就可以过了
为什么不能用树状数组呢?主要问题是树状数组的查询修改都是 l o g 26 log26 log26的,但是这道题查询枚举本身就带一个log。直接的暴力修改,虽然修改是 O ( 26 ) O(26) O(26)的,但是保证了查询 O ( 1 ) O(1) O(1)的复杂度,使修改查询的复杂度,从而能过。
因此,要根据题目不同的特点适当选择算法,而不是盲目选择所谓最快的,最好的算法。











#include <cstdio>
#include <cstring>
#include <algorithm>
#define N (1<<20)+5
#define mo1 1000000007
#define mo2 19260817
#define ll long long
#define lowbit(x) x&(-x)
#define R register
#define I inline
#define ull unsigned long long
using namespace std;
ll tree[27];
short sum[N],js[27],qz;
ull hx1[N],hx2[N];
ull mi1,mi2,g1;
char c[N];
int main()
{
   
   
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
	R int cs;
	scanf("%d\n",&cs);
	while (cs--)
	{
   
   
		scanf("%s\n",c+1);
		R int n=strlen(c+1);memset(tree,0,sizeof(tree));memset(js,0,sizeof(js));
		R ll ans=0;
		sum[n+1]=0;
		for (R int i=1;i<=n;i++) hx1[i]=hx1[i-1]*27+(c[i]-'a');
		for (R int i=n;i>=1;i--) 
		{
   
   
			js[c[i]-'a']^=1;	
			sum[i]=sum[i+1]+(js[c[i]-'a']%2?1:-1);
		} memset(js,0,sizeof(js));
		js[0]=0,js[c[1]-'a']=1;
		for (R int i=1;i<=26;i++) tree[i]++;
		qz=1;mi1=mi2=27;
		for (R int i=2;i<=n-1;i++)
		{
   
   
			g1=0;
			mi1=mi1*27;
			for (R int j=1;j<=n/i;j++)
			{
   
   
				g1=g1*mi1+hx1[i];
				if (j*i>=n) break;
				if (g1==hx1[j*i])
				{
   
   
					ans+=tree[sum[j*i+1]];
				} else break;
			}
			js[c[i]-'a']^=1;
			qz+=(!(js[c[i]-'a']&1))?-1:1;
			for (R int j=qz;j<=26;j++) tree[j]++;
		}
		printf("%lld\n",ans);
	}
	return 0;
}












版权声明
本文为[osc_8o71811p]所创,转载请带上原文链接,感谢
https://my.oschina.net/u/4321646/blog/4812784