​

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

AC自动机

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()
{
    queue<int>q;
    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;
}
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

P3796 【模板】AC 自动机（加强版）

利用结构体统计次数和标记位置。本题数据范围和题目给的不一样，总报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.pos<a2.pos;
    return a1.num>a2.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()
{
    queue<int>q;
    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<<ans[1].num<<endl;
        for(int i=1;ans[i].num==ans[1].num;i++)
            cout<<s[ans[i].pos]<<endl;
        init();
    }
    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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

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<<a[i]<<" ";
    cout<<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
50
51

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<<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

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<<endl;continue;
        }
        int ans=n/3;
        int g=n%3;
        if(g==1)
            ans+=1;
        else if(g==2)
            ans+=1;
        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

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<<n<<endl;
        for(int i=1;i<=n;i++)
            a[i]=i,cout<<i<<" ";
        cout<<endl;
        for(int i=2;i<=n;i++)
        {
            swap(a[1],a[i]);
            for(int i=1;i<=n;i++)
                cout<<a[i]<<" ";
            cout<<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