回文自动机+CodeTON Round 2 C,D

今天打了一场没啥意思的牛客，只有一个知识点需要注意一下。
回文自动机
回文自动机是一种类似于字典树和ac自动机的数据结构，能够在O（n）级别求解出：以某个字符为结尾的本质不同回文串个数，以某个字符为结尾的最长回文串长度，以某个字符为结尾的回文串出现的次数等等。
等到有时间专门写个PAM专题吧
首先是模板题，结合代码讲一下每个变量代表的意义。
P5496 【模板】回文自动机（PAM）

#include
#include
#include
using namespace std;
const int N = 5e5+100;
char s[N];
int len[N],n,num[N],fail[N],last,cur,pos,trie[N][26],tot=1;
int getfail(int x,int i)
{
	while(i-len[x]-1<0||s[i-len[x]-1]!=s[i])x=fail[x];
	return x;
}
void pam()
{
    fail[0]=1;
    len[1]=-1;
    for(int i=0;i<n;i++)
    {
        if(s[i]>=1)
            s[i]=(s[i]+last-97)%26+97;
    	pos=getfail(cur,i);
        if(!trie[pos][s[i]-'a'])
        {
        	fail[++tot]=trie[getfail(fail[pos],i)][s[i]-'a'];
        	trie[pos][s[i]-'a']=tot;
        	len[tot]=len[pos]+2;
            num[tot]=num[fail[tot]]+1;
		}
        cur=trie[pos][s[i]-'a'];
        last=num[cur];
        cout<<last<<" ";
	}
}
int main()
{
	cin>>s;
	n=strlen(s);
    pam();
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

len[i]：树中i节点代表的回文串的长度。值得注意的是，我们对于回文串分长度的奇偶情况，所以len[1]代表奇数长度的子树，len[0]代表偶数长度的子树。
num[i]：节点i为结尾的回文串有多少个
fail[i]：节点i失配后指向的节点满足：以此节点为结尾的回文串是节点i的最长回文后缀。

P3649 [APIO2014] 回文串

看一看这个。
根据板子只有一个点：统计每个回文子串出现了几次。

比如www这个串中ww回文串就出现了两次

#include
#include
#include
#define int long long
using namespace std;
const int N = 5e5+100;
char s[N];
int len[N],n,num[N],fail[N],last,pos,trie[N][26],tot=1;
int cnt[N];
int getfail(int x,int i)
{
	while(i-len[x]-1<0||s[i-len[x]-1]!=s[i])//我们跳到这样一个回文串
        x=fail[x];
	return x;
}
void pam()
{
    fail[0]=1;
    len[1]=-1;
    for(int i=0;i<=n-1;i++)
    {
    	pos=getfail(last,i);
        if(!trie[pos][s[i]-'a'])
        {
        	fail[++tot]=trie[getfail(fail[pos],i)][s[i]-'a'];
        	trie[pos][s[i]-'a']=tot;
        	len[tot]=len[pos]+2;
            num[tot]=num[fail[tot]]+1;
		}
        last=trie[pos][s[i]-'a'];
        cnt[last]++;
	}
}
signed main()
{
	cin>>s;
	n=strlen(s);
    pam();
    int ans=0;
    for(int i=tot;i>=1;i--)
    {
        cnt[fail[i]]+=cnt[i];
        ans=max(ans,cnt[i]*len[i]);
    }
    cout<<ans<<endl;
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

CodeTON Round 2
这俩题都挺直白的。

C. Virus
题意：给你n个马围一圈，一开始n个马有m个感染了病毒，每天病毒马都传染相邻的马，当然如果1 2 3这三匹马3感染病毒，2位置没有马，1位置有马，1和3不算相邻，所以1就不会被传染。
现在农夫每天可以在病毒传播之前牵走一批马隔离，问最少有多少匹马被感染。

思路：m匹马把环分割成m个区间，以一个n=10，m=2，初始感染的马是9 3为例，一个区间有3匹马，另一个有5匹，模拟一下就出做法了

#include 
#include 
#define int long long
using namespace std;
const int N = 1e5+100;

int a[N];
int b[N];
bool cmp(const int &a,const int &b)
{
    return a>b;
}
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int t;
    for(cin>>t;t;t--)
    {
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=m;i++)
        {
            cin>>a[i];
        }
        sort(a+1,a+m+1);
        b[1]=a[1]-1+n-a[m];
        for(int i=2;i<=m;i++)
        {
            b[i]=a[i]-a[i-1]-1;
        }
        sort(b+1,b+m+1,cmp);
        int cnt=0;
        int ans=0;
        for(int i=1;i<=m;i++)
        {
            if(b[i]-cnt>=2)
                ans+=b[i]-cnt-1;
            else if(b[i]-cnt==1)
                ans++;
            else
                break;
            cnt+=4;
        }
        cout<<n-ans<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

D. Magical Array
题意：给定n个长度为m的数组，这些数组初始完全一样，经过了k次变化后有一个特殊数组与众不同。
变化：
普通数组：选定一对(i,j),i 特殊数组：选定一对(i,j),i

思路：从前缀和角度去分析，发现普通数组的前缀和的和不会发生变化，而特殊数组由于空了一个所以前缀和的和每进行一次操作就-1。

#include 
#define int long long
using namespace std;
const int N = 1e5+100;
int pre[N];
signed main()
{
    int t;
    for(cin>>t;t;t--)
    {
        int n,m,maxx=-1,pos=0;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            int sum=0;
            for(int j=1,temp;j<=m;j++)
            {
                cin>>temp;
                sum+=temp;
                pre[i]+=sum;
            }
            maxx=max(maxx,pre[i]);
        }
        for(int i=1;i<=n;i++)
        {
            if(maxx!=pre[i])
            {
                pos=i;
                break;
            }
        }
        cout<<pos<<" "<<maxx-pre[pos]<<endl;
        for(int i=1;i<=n;i++)
            pre[i]=0;
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38