运气最差的一集--神秘哈希

T1

这道题很简单。不过因为我手动把整数数组改成了字符数组去搞哈希，然后只拿了90分

这道题只是一个普通的哈希题，核心代码就一小段：

CPP

unsigned long long get_hash(int l,int r)
{
	return hs[r]-hs[l-1]*pw[r-l+1]; 
}

是真的，我们只需要把输入的转成哈希值，二分枚举重复不少于

k

次的最大子串长度即可。枚举长度，然后跑一遍

1

到

n

的循环。长度固定，循环的

i

就是这段区间的起点。保证这一段区间不超过

n

，用一个

map

将这一段区间对应哈希值+1表示出现了一次，只要出现次数不少于 $k$ ，我们就认为这个区间长度是可以的。一直增加区间长度，在符合条件的区间长里取最大就行。

T2

CPP

un get_hash(int l,int r)
{
	return hs[r]-hs[l-1]*pw[r-l+1]; 
}
un get_hash_r(int l,int r)
{
	return ht[l]-ht[r+1]*pw[r-l+1];
}

un表示unsigned long long。只要使用这两段函数，我们用

O(1)

的时间就可以求出一段区间内字符串的前缀&后缀哈希值。又因为当一段区间的字符串前后缀哈希值一致时，这个字符串回文，所以我们想的简单点，直接暴力四重循环可以拿

50

分。

CPP

for(int i=1;i<s.size();i++)
	{
		for(int j=i;j<s.size();j++)
		{
			for(int l=j+1;l<s.size();l++)
			{
				for(int r=l;r<s.size();r++)
				{
					if(get_hash(i,j)==get_hash_r(i,j)&&get_hash(l,r)==get_hash_r(l,r))
					{
						cnt++;
					}
				}
			}
		}
	}

但是，这显然不够，还能优化。

维护 $cnt[i]$ 表示以点 $i$ 开头的回文串的数量
维护 $suf[i]$ 表示从点 $i$ 以及 $i$ 之后开头的回文串的数量。 $suf[i]=suf[i+1]+cnt[i]$
枚举 $[l1,r1]$ 命名为 $A$ 串，那么与 $A$ 串形成四元组的字符串有 $suf[r1+1]$ 个

那我们二重循环，

n-l1

与

r1-n

。每当

[l1,r1]

为回文串时，维护

cnt[l1]

并答案+

suf[r1+1]

。另外，

suf[l1]=suf[l1+1]+cnt[l1]

T3

写这题是答案没开long long，炸了，本来可以全对的。

我们不妨先找出已经回文的前后缀长度

len

，截取头尾之间的

len

，并设截取后的字符串子串为

t

，且删除的子串只会是

t

的前缀或者后缀。我们发现，在删除前缀时，如果这个前缀已经证明这是回文串，那么删掉它并不会使答案更优。

我们可以考虑删除子串

t

的前缀，枚举剩下来的长度

i

，剩余部分回文长度用哈希统计。对于后缀部分，我们可以翻转字符串，使后缀变为前缀，于是同上处理。答案只需要加上这两部分贡献即可

T4

这道题不过是把回文串包装成了反对称，感觉和前面的题难度差不多。

我们仔细想一想，如果一个字符串在区间

[l,r]

回文，那么区间

[l+1,r-1]

也肯定回文。

也就是说，区间

[l+1,r-1]

回文是区间

[l,r]

回文的必要条件。而区间

[l,r]

回文是区间

[l+1,r-1]

回文的充分条件

所以，我们不妨枚举回文字符串的对称轴，然后二分它能向左右延伸的最大长度

L

，此长度就是此对称轴对答案的贡献

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,base=13331;
int n;
unsigned long long hs[N],ht[N],pw[N];
string s;
unsigned long long get_hash(unsigned long long h[],int l,int r)
{
	return h[r]-h[l-1]*pw[r-l+1];
} 
unsigned long long get_hash_r(unsigned long long h[],int l,int r)
{
	return h[l]-h[r+1]*pw[r-l+1];
}
bool check(int x,int len)
{
	int st=x-len+1,ed=x+len;
	return get_hash(hs,st,ed)==get_hash_r(ht,st,ed);
}
int main()
{
	cin>>n>>s;
	s=" "+s;
	for(int i=1;i<=n;i++)
		hs[i]=hs[i-1]*base+(s[i]=='1');
	for(int i=n;i>=1;i--)
		ht[i]=ht[i+1]*base+(s[i]=='0');
	pw[0]=1;
	for(int i=1;i<=n;i++)
		pw[i]=pw[i-1]*base;
	long long ans=0;
	for(int i=1;i<n;i++)
	{
		int l=0,r=min(i,n-i)+1;
		while(l+1<r)
		{
			int mid=(l+r)/2;
			if(check(i,mid)==true)
				l=mid;
			else
				r=mid;
		}
		ans+=l;
	}
	cout<<ans;
}

运气最差的一集--神秘哈希

文章操作

T1

T2

T3

T4

相关推荐

评论

运气最差的一集--神秘哈希