|
今天打了一场没啥意思的牛客，只有一个知识点需要注意一下。
回文自动机
回文自动机是一种类似于字典树和ac自动机的数据结构，能够在O（n）级别求解出：以某个字符为结尾的本质不同回文串个数，以某个字符为结尾的最长回文串长度，以某个字符为结尾的回文串出现的次数等等。
等到有时间专门写个PAM专题吧
首先是模板题，结合代码讲一下每个变量代表的意义。
P5496 【模板】回文自动机（PAM）
#include<iostream>
#include<cstdio>
#include<cstring>
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;
}
len[i]：树中i节点代表的回文串的长度。值得注意的是，我们对于回文串分长度的奇偶情况，所以len[1]代表奇数长度的子树，len[0]代表偶数长度的子树。
num[i]：节点i为结尾的回文串有多少个
fail[i]：节点i失配后指向的节点满足：以此节点为结尾的回文串是节点i的最长回文后缀。
P3649 [APIO2014] 回文串
看一看这个。
根据板子只有一个点：统计每个回文子串出现了几次。
比如www这个串中ww回文串就出现了两次
#include<iostream>
#include<cstdio>
#include<cstring>
#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;
}
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 <iostream>
#include <algorithm>
#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;
}
D. Magical Array
题意：给定n个长度为m的数组，这些数组初始完全一样，经过了k次变化后有一个特殊数组与众不同。
变化：
普通数组：选定一对(i,j),i<j ，让a[i],a[j]减少1，a[i - 1],a[j + 1]增加1
特殊数组：选定一对(i,j),i<j ，让a[i],a[j]减少1，a[i - 1],a[j + 2]增加1
思路：从前缀和角度去分析，发现普通数组的前缀和的和不会发生变化，而特殊数组由于空了一个所以前缀和的和每进行一次操作就-1。
#include <bits/stdc++.h>
#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;
}
|