8/5 基础思维（div2 A、B、C、D）+dp+AC自动机

​

活动地址：CSDN21天学习挑战赛

https://www.bilibili.com/video/BV1tF41157Dy?spm_id_from=333.999.0.0&vd_source=91973ada1213cf6ba2cbb43a2bebd2e8

题意:给定n个模式串和一个主串，查找有多少个模式串再主串中出现过

int ch[N][26],cnt[N],idx;
int ne[N];
void ins(char *s)
{
    int p=0;
    for(int i=0;s[i];i++)
    {
        int j=s[i]-'a';
        if(!ch[p][j]) ch[p][j]=++idx;
        p=ch[p][j];
    }
    cnt[p]++;
}
void build()
{
    queueq;
    for(int i=0;i<26;i++)
        if(ch[0][i]) q.push(ch[0][i]);
    while(q.size())
    {
        int u=q.front();q.pop();
        for(int i=0;i<26;i++)
        {
            int v=ch[u][i];
            if(v) ne[v]=ch[ne[u]][i],q.push(v);
            else ch[u][i]=ch[ne[u]][i];
        }
    }
}
int query(char *s)
{
    int ans=0;
    for(int k=0,i=0;s[k];k++)
    {
        i=ch[i][s[k]-'a'];
        for(int j=i;j&&~cnt[j];j=new[j])
            ans+=cnt[j],cnt[j]=-1;
    }
    return ans;
}

利用结构体统计次数和标记位置。本题数据范围和题目给的不一样，总报re。
由于找出哪些模式串在文本串 T 中出现的次数最多
1.统计以idx节点结尾的字符串数量，本题固定是1.
2.文本串T在查询中，根据建立的字典树，通过回跳边和转一边迅速得到模式串位置。
回跳边：指向父节点回跳边所指节点的儿子。回跳边所指结点一定是当前结点的最长后缀。
转移边：当前结点所指结点回跳边的儿子。转移边所指结点一定是当前结点的最短路。

#include 
#define int long long
#define endl 'n'
using namespace std;
const int N =1e6+100;
const int mod=998244353;
const int inf=0x3f3f3f3f;
int ch[N][26],cnt[N],idx,n,tmp[N];
int ne[N];
string s[155],t;
struct Ans
{
    int num,pos;
}ans[N];
bool cmp(Ans a1,Ans a2)
{
    if(a1.num==a2.num)
        return a1.posa2.num;
}
void ins(string s,int g)
{
    int p=0;
    for(int i=0;s[i];i++)
    {
        int j=s[i]-'a';
        if(!ch[p][j]) ch[p][j]=++idx;
        p=ch[p][j];
    }
    cnt[p]++;
    tmp[p]=g;
}
void build()
{
    queueq;
    for(int i=0;i<26;i++)
        if(ch[0][i]) q.push(ch[0][i]);
    while(q.size())
    {
        int u=q.front();q.pop();
        for(int i=0;i<26;i++)
        {
            int v=ch[u][i];
            if(v) ne[v]=ch[ne[u]][i],q.push(v);
            else ch[u][i]=ch[ne[u]][i];
        }
    }
}
void query(string s)
{
    for(int k=0,i=0;s[k];k++)
    {
        i=ch[i][s[k]-'a'];
        for(int j=i;j;j=ne[j])
            ans[tmp[j]].num+=cnt[j];
    }

}
void init()
{
    for(int i=0;i<=idx;i++)
        tmp[i]=ne[i]=cnt[i]=0,ans[i].num=ans[i].pos=0;
    for(int i=0;i<=idx;i++)
        for(int j=0;j<26;j++)
        ch[i][j]=0;
    idx=0;
}
signed main()
{
    while(cin>>n)
    {
        if(n==0)    break;
        for(int i=1;i<=n;i++)
        {
            cin>>s[i];ins(s[i],i);
            ans[i].num=0;
            ans[i].pos=i;
        }
        build();
        cin>>t;
        query(t);
        sort(ans+1,ans+n+1,cmp);
        cout< 
D. Chip Move 
题意：1-n中，每个数的形成有几种方式。规则：从0开始，第一次相加的数必须被k除尽，第二次相加的数必须被k+1除尽。
 思路：两种做法，一种是dp思考状态转移；另一种可考虑用数组模拟，非常巧妙。
 1.预处理将k的倍数都加1，表示这些数都可在第一次时一次到达。k++
 2.k不断变化，利用两个数组分别模拟本次可到达的数。
 3.a数组通过累加b数组和c数组记录状态数。
 类似于模拟+dp中的状态数累加
 
#include 
#define int long long
#define endl 'n'

using namespace std;
const int N =2e5+100;
const int mod=998244353;
const int inf=0x3f3f3f3f;
int n,k,a[N],b[N],c[N];

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    for(int i=k;i<=n;i+=k)
        a[i]++,b[i]++;
    int g=2*k+1;
    k++;
    int flag=1;
    while(g<=n)
    {
        if(flag)
        {
            for(int i=g;i<=n;i++)
            {
                c[i]=(b[i-k]+c[i-k])%mod;
                a[i]=(a[i]+c[i])%mod;
            }
            for(int i=0;i<=n;i++)   b[i]=0;
        }
        else
        {
            for(int i=g;i<=n;i++)
            {
                b[i]=(b[i-k]+c[i-k])%mod;
                a[i]=(a[i]+b[i])%mod;
            }
            for(int i=0;i<=n;i++)   c[i]=0;
        }
        k++;
        g+=k;
        flag=1-flag;
    }
    for(int i=1;i<=n;i++)
        cout< 
C. Robot in a Hallway 
这几天做的最难的一个dp，光理解花了1个半小时。但还是有几处不懂，刚打的cf题解还是太少了，好难的dp，先放一下，过几天再回看。
 
思路：
 1.对于这张2行m列的图，要满足每个点都没遍历到，要么走蛇形，要么走环形，可先蛇形走到某个点再环形走
 2.预处理出若此点为环形终点，所要花费的时间。
 由三部分组成max({a[i][j]+2*(m-j+1),f[i][j+1]+1,a[3-i][j]+1})，取出一个最大值。
 3.在进行遍历，从哪一列开始走环形。若num>f[g][i],则说明后面无特殊格子阻碍。
 
#include 
#define int long long
#define endl 'n'
using namespace std;
const int N =1e5+100;
const int mod=998244353;
const int inf=0x3f3f3f3f;
int n,m,a[5][N],f[5][N];

signed main()
{
    int q;cin>>q;
    while(q--)
    {
        cin>>m;
        for(int i=1;i<=2;i++)
            for(int j=1;j<=m;j++)
                cin>>a[i][j];
        a[1][1]=-1;
        f[1][m+1]=f[2][m+1]=1;
        for(int j=m;j>=1;j--)
        {
            for(int i=1;i<=2;i++)
            f[i][j]=max({a[i][j]+2*(m-j+1),f[i][j+1]+1,a[3-i][j]+1});
        }
        int ans=inf,num=0;
        for(int i=1;i<=m;i++)
        {
            int g=3-(i%2+1);
            ans=min(ans,max(num,f[g][i]));
            num=max({num,a[g][i]+2*(m-i+1),a[3-g][i]+2*(m-i+1)-1});
        }
        cout< 
A. 2-3 Moves 
思路：
 1.n等于1是特例。
 2.n对3进行取模，若等于2，则填一个2就好，若等于1则需要把之前的一个3改为2.
 
#include 
#define int long long
#define endl 'n'
using namespace std;
const int N =1e6+100;
const int mod=998244353;
string t,s;
int n,cnt;

signed main()
{
    int q;cin>>q;
    while(q--)
    {
        int n;cin>>n;
        if(n==1)
        {
            cout<<2< 
B. Permutation Chain 
思路：第一个数字分别和2~n的数字调换顺序
 
#include 
#define int long long
#define endl 'n'
using namespace std;
const int N =1e6+100;
const int mod=998244353;
int n,a[105];

signed main()
{
    int q;cin>>q;
    while(q--)
    {
        int n;cin>>n;
        cout<
            swap(a[1],a[i]);
            for(int i=1;i<=n;i++)
                cout<