每日一题~ Birthday Cake+19浙江省赛 I（字符串哈希，匹配）(哈希判断回文串，奇偶性质的博弈)

添加链接描述
题意：
n 个字符串，两两组合，问有几对能形成 AA 串。
n<=4e5
。
分析：
符合条件的有两种
1.有多个A 串，对答案的贡献是 cnt*(cnt-1)/2
2.有形如 ABA 的串，这时，我们需要寻找 B 串的数量。对答案的贡献就是 B的数量。

我们使用哈希来处理字符串。

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define pii pair<ll,ll>
ll mod1=1e9+7,mod2=1e9+9;
ll bas=131;
const int maxn=4e5+5;
pii res[maxn];
map<pii,ll>mp;//计算 个数的
ll ha1[maxn],ha2[maxn],p1[maxn],p2[maxn];
ll get1(int l,int r)
{
    return (ha1[r]-ha1[l-1]*p1[r-l+1]%mod1+mod1)%mod1;
}
ll get2(int l,int r)
{
    return (ha2[r]-ha2[l-1]*p2[r-l+1]%mod2+mod2)%mod2;
}
pii get(int l, int r)
{
    return {get1(l,r),get2(l,r)};
}

void solve()
{
    int tot=0;
    p1[0]=p2[0]=1;
    for (int i=1;i<maxn;i++)
    {
        p1[i]=p1[i-1]*bas%mod1;
        p2[i]=p2[i-1]*bas%mod2;
     }
    
    int n;cin>>n;
    string t;
    while(n--)
    {
        cin>>t;
        int len=t.size();ha1[0]=ha2[0]=0;
        for (int i=1;i<=len;i++)
        {
            ha1[i]=ha1[i-1]*bas%mod1+t[i-1]-'a'+1;
            ha2[i]=ha2[i-1]*bas%mod2+t[i-1]-'a'+1;
            ha1[i]%=mod1;
            ha2[i]%=mod2;
        }
        mp[{ha1[len],ha2[len]}]++;
        // j 代表 偏移量，这里试图将 string t 拆成 ABA 类型的。
        //我们枚举两边的 A，将中间 的B放到数组中存起来。
        //  j 代表A的长度
        
        for (int j=1;j+j<len;j++)
        {
            
            if (get(1,j)==get(len-j+1,len))
                {
                    res[tot++]=get(j+1,len-j);

                }
        }
    }
   
    ll ans=0;
    for (int i=0;i<tot;i++){
        ans+=mp[res[i]];
    }
    

    for (auto i:mp){
       ans+=i.second*(i.second-1)/2;
    }
    cout<<ans<<"\n";
}
int  main()
{
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int t; t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

添加链接描述
题意：
有一个字符串
每一个人每轮 在字符串 的头部 或 尾部 删去一个字母。
未操作和操作之后，都认为a 拥有这个字符串
如果 a 拥有字符串的时候，是回文串，那么a输。
（换言之，如果一开始 是回文，那么先手输。之后谁操作之后是回文，谁输）。
n 长的字符串，q 次询问。
每次询问 l r。也就是这一局，两人玩的字符串是 [l r] 的子串。
问谁赢。
思考：
如果 一开始 字符串是 回文的，那么先手输。
如果一开始不是回文 ，
我们来考虑一下 一定失败的状态。本身的字符串不是回文，但是不论删除首字母还是尾字母。新的字符串都是回文。
我们可以列举一些 这样的字符串 ab baba 我们可以发现构造出来的都是偶数。
奇数的出不来。可以自己构造一下3个长度的 字符串。
所以我们可以判断 初始的串的长度的奇偶性。
如果一开始 是奇数，那么先手操作的时候一定是奇数。后手操作的时候一定是偶数。
所以 如果为奇数，先手输。否则 后手输。
通过哈希来判断回文 ，主要是 处理一个 ha[N] 和一个 rha[N] 数组。
rha 里面存储的是 倒叙，如果两者相等，那么说明是 回文的。

原文地址：https://blog.csdn.net/x1653673086/article/details/140595147

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！