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

· · 个人记录

T1

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

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

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

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分。

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++;
                    }
                }
            }
        }
    }

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

那我们二重循环，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，此长度就是此对称轴对答案的贡献

#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;
}