喜欢的话就坚持吧

分类目录
10月 15

题目大意:

给你一个字符串s,你可以对他进行一种操作,就是把串s的除最后一个字符翻转后接到s后面
比如s=’abcab’
那么操作完了就是abcabacba;
现在给你一个串r,是进行多次操作(可以不操作)后的s串的前缀,问初始s串的可能长度。(显然比r长的都有可能,你只需要输出小于等于r的)

继续阅读

  1. 本文由hatate创作采用 知识共享署名 4.0国际许可协议进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

9月 26

题目大意

找到一个字符串中所有前半等于后半的字符串,如abab,按长度从短到长删除其左半部分,如果长度相等,则先删最左边的。
输出删除后剩余的字符串。

继续阅读

  1. 本文由hatate创作采用 知识共享署名 4.0国际许可协议进行许可。 可自由转载、引用,但需署名作者且注明文章出处。

9月 26

题目大意:

给定一个长度为n的小写字母串。问你有多少对相交的回文子 串(包含也算相交),对p取模,1<=n<=2*10^6。

如题所说,我们要求香♂蕉的回文串。
思考我有什么关于字符串的算法,kmp?manacher?hash?
显然要用manacher。
想想manacher求了些什么?
最长回文串?每个点的回文半径?
考虑什么样的两个串是符合条件的,某个回文串的中心离另一个回文串的中心不超过他们两最大的回文半径。
emm…
大概O(n^2)
感觉不可做了。
这是一定有什么奇技淫巧?
我们考虑什么样的是不合条件的?
对于一个位置i
以i结尾的回文串和以i后面任意字符开头的回文串的组合都是合法的。
我们可以拿总数-不合法的=合法的。
挺简单?
没错。(其实我现学的manacher)

#include <cstdio>
#include <algorithm>
#include <cstring>

#define int long long
using namespace std;
const int N=4000005;
const int mod=51123987;

char s[N],s1[N];
int p[N],len,ans,tot,n;
int f[N][2];
inline int be()
{
    int len1=strlen(s);
    s1[0]='$';s1[1]='#';
    int j=2;
    for(int i=0;i<len1;++i)
    {
        s1[j++]=s[i];
        s1[j++]='#';
    }
    s1[j]='';
    return j;
}
inline void manacher()
{
    len=be();
    int max_len=-1;
    int id,mx=0;
    for(int i=1;i<len;++i)
    {
        if(i<mx) p[i]=min(p[2*id-i],mx-i);
        else p[i]=1;
        while(s1[i-p[i]]==s1[i+p[i]]) p[i]++;
        if(mx<i+p[i])
        {
            id=i;mx=i+p[i];
        }
        max_len=max(max_len,p[i]-1);
    }
}
signed main()
{
    scanf("%lld%s",&n,s);
    manacher();
    for(int i=2;i<len;++i)
    {
        int len1=p[i]/2,pos=i/2;
        if(len1==0) continue;tot+=len1;
        if(i&1)
        {
            f[pos-len1+1][1]++;f[pos+1][1]--;
            f[pos+1][0]++;f[pos+len1+1][0]--;
        }
        else
        {
            f[pos-len1+1][1]++;f[pos+1][1]--;
            f[pos][0]++;f[pos+len1][0]--;
        }
    }
    len=strlen(s);
    for(int i=1;i<=len;++i)
    {
        f[i][1]+=f[i-1][1];f[i][0]+=f[i-1][0];
    }f[len+1][1]=0;
    for(int i=1;i<=len;++i)
    {
        f[len-i+1][1]+=f[len-i+2][1];
    }
    for(int i=1;i<=len;++i)
    {
        ans+=f[i][0]*f[i+1][1];ans%=mod;
    }tot%=mod;
    printf("%lldn",((tot*(tot-1)/2)%mod+mod-ans)%mod);
}

  1. 本文由hatate创作采用 知识共享署名 4.0国际许可协议进行许可。 可自由转载、引用,但需署名作者且注明文章出处。