9.1学习报告

写写AC自动机，可持久化KMP和KMP自动机吧
写起来这三个东西还是要从一个题说起

E. Prefix Function Queries

题意：给定一个字符串s，每次往后面加上一个字符串t，输出拼接后字符串t的next数组，输出之后将t从这个拼接的字符串上拿走。

首先，这个题如果你没学过kmp肯定是不会，

其次，你学过kmp估计你也不会。

从题目上听起来，这是要实现一个可持久化的字符串s的next数组，所以学习一波可持久化kmp，貌似和z（求lcp）函数一样是个很板的东西

具体使用起来在代码里有注释，我默认s是模式串，t是文本串。

#include
#include
using namespace std;
using LL = long long;
const int maxn = 2e6 + 5;
int ne[maxn], pre[maxn];
char s[maxn], t[maxn];
int last;
void add(char x)
{
    int j = last;
    while(j&&s[ne[j]+1]!=x)
        j = pre[j];
    s[++last]=x;
    j=ne[j]+1;
    if(last==1)
        ne[1]=pre[1]=0;
    else if(s[j]==x)
    {
        ne[last] = j;
        if (s[ne[j] + 1] == s[j + 1])
        pre[last] = pre[j];
        else
        pre[last] = j;
    }
    else
    ne[last]=pre[last]=0;
}
int main(){
 
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin >>t+1;//输入文本串（我为什么要解释这个？）
    for(int i=1;t[i];i++)
        add(t[i]);//构建了文本串的next
    int n;
    cin>>n;
    while(n--)
    {
        cin>>s+1;
        int len=strlen(s + 1);
        for(int i = 1; i <= len; i++)
        {
            add(s[i]);
            cout << ne[last]<<' ';
        }
        cout << '\n';
        last -= len;//last就是最末尾的，你减去len，下一次就从头覆盖，相当于删掉了字符串t
    }
    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

好的再来看一个东西：kmp自动机

我们知道kmp的next数组是在失配情况下选择让模式串向前移动一定的距离，也就相当于优化过后的暴力跳。

但是如果要是这样的串呢？

文本串:bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
模式串:aaaaaaaaaa
按道理讲，我们第二次就应该结束匹配了，但是如果按照传统kmp算法，最坏的复杂度就是O(M*N)
讲道理，十分低效。

那么可以想的优化就是：我们将next数组优化，指明下一项最优应该匹配那个位置。

例题
G. Anthem of Berland

#include 
 
using namespace std;
 
const int N=1e7+1000;
const int M=1e5+100;
 
char s[M],t[M];//模式串和文本串
//int f[2][N];//s和t不固定，而且空间过大，采用滚动数组优化空间
int ne[M];//文本串的kmp中的fail数组
int to[M][26];//如果前i个字符都匹配了，先要匹配字符j，那么我们应该用什么位置去应对，显然i等于m+1
int n,m;//模式串长度和文本串长度
 
int main()
{
    cin>>(s+1)>>(t+1);
    n=strlen(s+1);
    m=strlen(t+1);
    int f[n+1][m+1];
    //板子
    for(int i=2,j=0;i<=m;i++)//从长度为2开始，因为下标从1开始的
    {
        while(j&&t[j+1]!=t[i])
        j=ne[j];
        if(t[i]==t[j+1])j++;
        ne[i]=j;
    }
    for(int i=0;i<=m;i++)//已经处理好的长度自然是从 0到m 这样来判断，当然，0和m的情况下都应该重新匹配了。
    {
        for(int j=0;j<26;j++)
        {
            if(i&&t[i+1]-'a'!=j)
             to[i][j]=to[ne[i]][j];
            else
            {
                if(t[i+1]-'a'==j)
                    to[i][j]=i+1;
                else
                    to[i][j]=i;
            }
        }
    }
    //板子
    memset(f, -0x3f, sizeof f);
    f[0][0] = 0;
    for(int i=1;i<=n;i++)
    {
       // int i=i&1,pre=i^1;
        for(int j=0;j<=m;j++)
            f[i][j]=-1e9;
        for(int j=0;j<=m;j++)
        {
            if(s[i]=='?')
            {
                for(int k=0;k<26;k++)
                    f[i][to[j][k]]=max(f[i][to[j][k]],f[i-1][j]+(to[j][k]==m));
            }
            else
            {
                int k = s[i] - 'a';
                f[i][to[j][k]] = max(f[i][to[j][k]], f[i-1][j] +(to[j][k]==m));
            }
        }
    }
    int res = 0;
    for (int j = 0; j <= m; j++)
        res = max(res, f[n][j]);
    printf("%d\n", res);
    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

AC自动机

这个东西也有上面讲到的KMP自动机的情况。
这次先做个加强版的。二次加强版的模板代码我还没彻底搞明白，但是大概知道了要用到类似于树上差分或者是拓扑排序的做法来避免暴力跳fail造成效率低下。

现在的模板可以说是说卡就卡了，等我琢磨明白那个AC自动机的fail树优化更新一下模板。

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

#include 
#define endl '\n'
using namespace std;
struct tree//字典树
{
    int fail;//失配指针
    int vis[26];
    int end;
};
struct Ans
{
    int num;
    int pos;
};
bool cmp(const Ans &a,const Ans &b)
{
    return a.num==b.num?a.pos<b.pos:a.num>b.num;
}
Ans ans[1000000];
tree AC[1000000];//Trie树,大小和取决于cnt的上限
string s[500];
int cnt;//Trie的指针
void init(int x)
{
    memset(AC[x].vis,0,sizeof(AC[x].vis));
    AC[x].fail=0;
    AC[x].end=0;
}
void add(string s,int num)
{
    int l=s.length();
    int now=0;//字典树的当前指针
    for(int i=0;i<l;++i)//构造Trie树
    {
        if(AC[now].vis[s[i]-'a']==0)//Trie树没有这个子节点
        {
            AC[now].vis[s[i]-'a']=++cnt;
            init(cnt);
        }
        now=AC[now].vis[s[i]-'a'];//向下构造
    }
    AC[now].end=num;//标记单词结尾
}

void Get_fail()//构造fail指针
{
    queue<int> Q;//队列
    for(int i=0;i<26;++i)//第二层的fail指针提前处理一下
    {
        if(AC[0].vis[i]!=0)
        {
            AC[AC[0].vis[i]].fail=0;//指向根节点
            Q.push(AC[0].vis[i]);//压入队列
        }
    }
    while(!Q.empty())//BFS求fail指针
    {
        int u=Q.front();
        Q.pop();
        for(int i=0;i<26;++i)//枚举所有子节点
        {
            if(AC[u].vis[i]!=0)//存在这个子节点
            {
                AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i];
                //子节点的fail指针指向当前节点的
                //fail指针所指向的节点的相同子节点
                Q.push(AC[u].vis[i]);
            }
            else//不存在这个子节点
            AC[u].vis[i]=AC[AC[u].fail].vis[i];
            //当前节点的这个子节点指向当
            //前节点fail指针的这个子节点
        }
    }
}
void AC_Query(string s)//AC自动机匹配
{
    int l=s.length();
    int now=0;
    for(int i=0;i<l;++i)
    {
        now=AC[now].vis[s[i]-'a'];//向下一层
        for(int t=now;t;t=AC[t].fail)//循环求解
        {
            ans[AC[t].end].num++;
        }
    }
}
int main()
{
     int n;
     while(cin>>n&&n)
     {

        cnt=0;
        init(0);
        for(int i=1;i<=n;i++)
        {
            cin>>s[i];
            ans[i].num=0;
            ans[i].pos=i;
            add(s[i],i);
        }
        Get_fail();
        cin>>s[0];
        AC_Query(s[0]);
        sort(ans+1,ans+n+1,cmp);
        cout<<ans[1].num<<endl;
        for(int i=1;i<=n;i++)
        {
            cout<<s[ans[i].pos]<<endl;
            if(ans[i+1].num!=ans[1].num)
                break;
        }
     }
     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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

以下就是日常思维训练搞得一些有趣的题
G. Two Merged Sequences

题意：给定一个数组，问能不能拆成一哥严格递增，一个严格递减的。。

思路：这题最优解是DP啦，但是2400的dp对我来讲还是有些难了，用贪心解吧。

对于每个数，这个数进入到递增或者是递减都决定了后面数的选择权。

比如a[i]>a[i+1]
这个时候如果a[i]只有一个选择，那必须先让a[i]选，如果有多个选择，那么a[i]必须进入递减数组，因为只有这样a[i+1]才可能也进入递减数组，否则就会砍掉a[i+1]的一个选择。

所以贪心策略就是：尽可能让后方数的选择权多一些。

#include
using namespace std;
const int N = 2e5+100;

int a[N],ans[N];
vector <int> des,ins;
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    a[n+1]=-1;
    des.push_back(1e9+100);
    ins.push_back(-1);
    for(int i=1;i<=n;i++)
    {
        int is=ins.back(),ds=des.back();
        bool falg1=0,falg2=0;
        if(a[i]>is)
            falg1=1;
        if(a[i]<ds)
            falg2=1;
        if(!falg1&&falg2)
            des.push_back(a[i]),ans[i]=1;
        if(falg1&&!falg2)
            ins.push_back(a[i]);
        if(!falg1&&!falg2)
        {
            cout<<"NO"<<endl;
            return 0;
        }
        if(falg1&&falg2)
        {
            if(a[i]<a[i+1])
                ins.push_back(a[i]);
            else if(a[i]>a[i+1])
                des.push_back(a[i]),ans[i]=1;
            else
                des.push_back(a[i]),ans[i]=1;
        }
    }
    cout<<"YES"<<endl;
    for(int i=1;i<=n;i++)
    {
        cout<<ans[i]<<" ";
    }
	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

E. Counting Rectangles

记录一下我洗的呆呆代码。

这个题正解是二维前缀和而已，我直接暴力+二分碾过去了。

#include 

using namespace std;
vector<int> v[1010];
vector<long long> vv[1010];
signed main()
{
    int t;
    for(cin>>t;t;t--)
    {
        int n,q;
        scanf("%d%d",&n,&q);
        for(int i=1;i<=1000;i++)
        {
            if(!v[i].size())
                continue;
            v[i].clear();
            vv[i].clear();
        }
        for(int i=1,h,w;i<=n;i++)
        {
            scanf("%d%d",&h,&w);
            v[h].push_back(w);
        }
        for(int i=1;i<=1000;i++)
        {
            if(!v[i].size())
                continue;
            sort(v[i].begin(),v[i].end());
            for(int j=0;j<v[i].size();j++)
            {
                vv[i].push_back(v[i][j]*i);
                if(j)
                vv[i][j]+=vv[i][j-1];
            }
        }
        for(int i=1,h1,w1,h2,w2;i<=q;i++)
        {
            scanf("%d%d%d%d",&h1,&w1,&h2,&w2);
            long long ans=0ll;
            for(int j=h1+1;j<=h2-1;j++)
            {
                int pos1=upper_bound(v[j].begin(),v[j].end(),w1)-v[j].begin();
                int pos2=lower_bound(v[j].begin(),v[j].end(),w2)-v[j].begin()-1;
                if(pos1>pos2)
                continue;
                if(pos1>0)
                    ans+=(vv[j][pos2]-vv[j][pos1-1]);
                else
                    ans+=vv[j][pos2];
            }
            printf("%lld\n",ans);
        }
    }
    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

比较思维的是这个题
G

题意很简单就不翻译了。

思路：既然奇偶位置异或答案相等，显然总体异或答案为0，将最后三个数流出来，记录前面1到n-3个数的异或值，让最后三个数的异或值和这个值异或起来等于0即可。

#include 

using namespace std;
void findArray(int N)
{
    int P = N - 2;
    int Q = N - 1;
    int VAL = 0;
    for(int i = 1; i <= (N - 3); i++)
    {
        cout << i << " ";
        VAL ^= i;
    }

    if(VAL == 0)
    {
      while((P ^ Q)<=P)
            Q++;
        cout << P << " " << Q<< " " << (P ^ Q) << " ";
    }
    else
    {
      while((P^VAL) <= N-3)
        {    P++;
        }
        cout << 0 << " " << P<< " " << (P^VAL) << " ";
    }
}

signed main()
{
    int t;
    for(cin>>t;t;t--)
    {
        int n;
        cin >> n;
        findArray(n);
        cout << endl;
    }
}
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

最后留给世人一个难题

这场div4的D我读错题了

错题意：从字符串中抽取k个字符，然后再插入到字符串当中，求插入后的价值最大值。