Post 5

Veröffentlicht am | Edited on

忍耐，也是一件美好的事，但前提是你有非常清晰的未来版图，你知道忍耐这一段后，会有什么等着你，你愿意为此暂时收起自己的羽毛。

「一本通 2.4 练习 1」玄武密码

题目描述

原题来自：JSOI 2012

在美丽的玄武湖畔，鸡鸣寺边，鸡笼山前，有一块富饶而秀美的土地，人们唤作进香河。相传一日，一缕紫气从天而至，只一瞬间便消失在了进香河中。老人们说，这是玄武神灵将天书藏匿在此。

很多年后，人们终于在进香河地区发现了带有玄武密码的文字。更加神奇的是，这份带有玄武密码的文字，与玄武湖南岸台城的结构有微妙的关联。于是，漫长的破译工作开始了。

经过分析，我们可以用东南西北四个方向来描述台城城砖的摆放，不妨用一个长度为 NN 的序列来描述，序列中的元素分别是 E，S，W，N，代表了东南西北四向，我们称之为母串。而神秘的玄武密码是由四象的图案描述而成的 M 段文字。这里的四象，分别是东之青龙，西之白虎，南之朱雀，北之玄武，对东南西北四向相对应。

现在，考古工作者遇到了一个难题。对于每一段文字，其前缀在母串上的最大匹配长度是多少呢？

输入格式

第一行有两个整数，N 和 M，分别表示母串的长度和文字段的个数；
第二行是一个长度为 N 的字符串，所有字符都满足是 E，S，W 和 N 中的一个；
之后 M 行，每行有一个字符串，描述了一段带有玄武密码的文字。依然满足，所有字符都满足是 E，S，W 和 N 中的一个。

输出格式

输出有 MM 行，对应 MM 段文字。
每一行输出一个数，表示这一段文字的前缀与母串的最大匹配串长度。

样例

样例输入

1
2
3
4
5
7 3
SNNSSNS
NNSS
NNN
WSEE

样例输出

1
2
3
4
2
0

数据范围与提示

对于全部数据，

，保证每一段文字的长度均小于等于 100。

题解

还是比较简单的一道AC自动机 + DP（调了3个小时）

本来我想直接写个普通的不带Trie图优化的AC自动机然后直接在Trie树上DP，结果惊讶的发现写错了，还调不出来，甚至怀疑自己学了假的AC自动机。

既然这样就在保留一颗没有变成Trie图的Trie树用来DP就好了。

我们在Trie树上进行AC自动机匹配，由AC自动机原理可知所有访问过的编号大于1的点都是能够在原串上匹配到的字符串，我们把这些点都标记一下。

接下来应该让每个模式串结尾的Trie上节点都向上跳到最深被标记的节点，显然不能暴力跳。

那就从根节点向下递推就好了，设

表示节点k跳到的深度最大的标记点。对于被标记的点，

没被标记的

但是要注意，模式串有重复！！各种调试最终找到了这个错误。

所以标记要用vector存。

时间复杂度显然是

Code:
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
#define maxn 10000007
int id[205] , idx = -1 , cur , ans[100005] , n , m;
char s[maxn] , p[100005][105];
struct Trie
{
	int tr[maxn][4] , tot ;
    std::vector<int> mark[maxn];
	Trie(){
		tot = 1;
	}
	inline void insert(char* s , int num)
	{
		int u = 1 , len = std::strlen(s);
		for(int i = 0 ; i < len ; ++i)
		{
			int c = id[s[i]];
			if(!tr[u][c]) tr[u][c] = ++tot;
			u = tr[u][c];
		}
		mark[u].push_back(num);
	}
	inline int* operator[](int x){
		return tr[x];
	}
};
struct AC_Automaton
{
	int next[maxn] , dep[maxn] , g[maxn] , sz[maxn] ;
	bool vis[maxn];
	Trie tr , base;
	inline void insert(char* s , int num)
	{
		tr.insert(s , num);
	}
	inline void getFail()
	{
		base = tr;
		std::queue<int> q;
		for(int i = 0 ; i < 4 ; ++i)
			tr[0][i] = 1;
		q.push(1) , next[1] = 0;
		while(!q.empty())
		{
			int u = q.front();
			q.pop();
			for(int c = 0 ; c < 4 ; ++c)
			{
				if(!tr[u][c]) tr[u][c] = tr[next[u]][c];
				else	q.push(tr[u][c]) , next[tr[u][c]] = tr[next[u]][c];
			}
		}
	}
	inline int find(char* s)
	{
		int u = 1 , len = std::strlen(s);
		for(int i = 0 ; i < len ; ++i)
		{
			int c = id[s[i]] , k = tr[u][c];
			while(k > 1)
			{
				vis[k] = true;
				k = next[k];
			}
			u = tr[u][c];
		}
	}
	void getSize(int x , int d)
	{
		sz[x] = 1;
		dep[x] = d;
		for(int i = 0 ; i < 4 ; ++i)
			if(base[x][i])
				getSize(base[x][i] , d + 1) , sz[x] += sz[base[x][i]];
	}
	inline void pre()
	{
		getSize(1 , 0);
		std::queue<int> q;
		for(int i = 1 ; i <= base.tot ; ++i)
			if(sz[i] == 1)	q.push(i);
		q.push(1);
		while(!q.empty())
		{
			int k = q.front();
			q.pop();
			if(vis[k]) g[k] = dep[k];
			for(int i = 0 ; i < 4 ; ++i)
			{
				if(!base[k][i]) continue;
				if(!vis[base[k][i]]) g[base[k][i]] = g[k];
			    q.push(base[k][i]);
			}
		}
	}
	void getPrintTrie(int x , int c)
	{
		printf("%d %d\n",x,c);
		for(int i = 0 ; i < 4 ; ++i)
			if(base[x][i])
				getPrintTrie(base[x][i] , i);
	}
	inline void print()
	{
		puts("The trie:");
		getPrintTrie(1 , 'B');
		for(int i = 1 ; i <= base.tot ; ++i)
			printf("%d ", next[i]);
		puts("Debug finished");
	}
}aton;
int main()
{
	id['N'] = 0 , id['W'] = 1 , id['E'] = 2 , id['S'] = 3;
	scanf("%d%d",&n,&m);
	scanf("%s",s+1);
	for(int i = 1 ; i <= m ; ++i)
	{
		++cur;
		scanf("%s",p[cur]+1);
		aton.insert(p[cur]+1,i);
	}
	aton.getFail();
	//aton.print();
	aton.find(s+1);
	aton.pre();
	for(int i = 1 ; i <= aton.base.tot ; ++i)
		if(aton.base.mark[i].size())	
			for(int j = 0 ; j < aton.base.mark[i].size() ; ++j)
				ans[aton.base.mark[i][j]] = aton.g[i];
	for(int i = 1 ; i <= m ; ++i)
		printf("%d\n",ans[i]);
}

终于把不带任何优化，完全按照原理匹配的AC自动机调出来了。。。仅仅是因为一个很sb的匹配的错误：

AC：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
inline void find(char* s)
 {
     int len = std::strlen(s + 1);
     int u = 1;
     for(int i = 1 ; i <= len ; ++i){
         int c = s[i] - 97;
         while(!tr[u][c] && u > 1) u = next[u];
         if(u > 1) u = tr[u][c];
         else if(u == 1 && tr[u][c]) u = tr[u][c];
         else u = 1;
         if(u > 1)
         {
             int k = u;
             while(k > 1)
             {
                 ans[k] += Ma[k];
                 k = next[k];
             }
         }
     }
 }

WA：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
inline void find(char* s)
 {
     int len = std::strlen(s + 1);
     int u = 1;
     for(int i = 1 ; i <= len ; ++i){
         int c = s[i] - 97;
         while(!tr[u][c] && u > 1) u = next[u];
         if(u > 1)
         {
             int k = u;
             while(k > 1)
             {
                 ans[k] += Ma[k];
                 k = next[k];
             }
         }
         if(u > 1) u = tr[u][c];
         else if(u == 1 && tr[u][c]) u = tr[u][c];
         else u = 1;
     }
 }

显然在u转移之后才能统计啊。。不然第一个字符永远没法匹配当然挂了。

以后把bug代码贴出来似乎是个不错的主意。

话说更令人惊奇的是，不带优化的AC自动机比Trie图快了整整两秒。。。怕不是逆优化。

完整的按原理的AC自动机

Code：

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>
#include <stack>
#define maxn 1000005
#define maxc 26
int cur = 1 ,  n , ans[maxn];
char s[maxn] , p[maxn];
struct AC_Automaton
{
    int tr[maxn][maxc] , tot , next[maxn] , Ma[maxn] , f[maxn] , g[maxn];
    bool vis[maxn];
    AC_Automaton(){
        tot = 1;
    }
    inline void init()
    {
        tot = 1;
        std::memset(tr,0,sizeof(tr));
        std::memset(next,0,sizeof(next));
        std::memset(Ma,0,sizeof(Ma));
        std::memset(f,0,sizeof(f));
        std::memset(g,0,sizeof(g));
    }
    inline void insert(char* s)
    {
        int len = std::strlen(s) , u = 1;
        for(int i = 0 ; i < len ; ++i){
            int c = s[i] - 97;
            if(!tr[u][c])	tr[u][c] = ++ tot; 
            f[tr[u][c]] = u , g[tr[u][c]] = c , u = tr[u][c];
        }
        Ma[u] ++;
    }
    inline void GetFail()
    {
        std::queue<int> q;
        for(int i = 0 ; i < 26 ; ++i)
            tr[0][i] = 1;
        q.push(1) , next[1] = 0;
        while(!q.empty())
        {
            int k = q.front();
            q.pop();
            for(int i = 0 ; i < 26 ; ++i){
                if(!tr[k][i]) continue;
                q.push(tr[k][i]);
                int u = next[k];
                while(u > 1 && !tr[u][i])	u = next[u];
                if(u > 1) next[tr[k][i]] = tr[u][i];
                else if(u == 1 && tr[u][i]) next[tr[k][i]] = tr[u][i];
                else next[tr[k][i]] = 1;
            }
        }
    }
    inline void find(char* s)
    {
        int len = std::strlen(s + 1);
        int u = 1;
        for(int i = 1 ; i <= len ; ++i){
            int c = s[i] - 97;
            while(!tr[u][c] && u > 1) u = next[u];
            if(u > 1) u = tr[u][c];
            else if(u == 1 && tr[u][c]) u = tr[u][c];
            else u = 1;
            if(u > 1)
            {
                int k = u;
                while(k > 1)
                {
                    ans[k] += Ma[k];
                    k = next[k];
                }
            }
        }
    }
    inline void print(int k)
    {
        std::stack<int> st;
        while(k > 1)
        {
            st.push(g[k]);
            k = f[k];
        }
        while(!st.empty())
            printf("%c",st.top()+97) , st.pop();
        putchar(10);
    }
    inline void DEBUG()
    {
        puts("Start Debug");
        for(int i = 2 ; i <= tot ; ++i)
        {
            puts("The string is");
            print(i);
            puts("The next string is");
            print(next[i]);
        }
        puts("End Debug");
    }
        
}aton;
int main()
{
    while(scanf("%d",&n) != EOF)
    {
        std::memset(ans,0,sizeof(ans));
        aton.init();
        cur = 1;
        if(n == 0) break;
        for(int i = 1 ; i <= n ; ++i)
        {
            scanf("%s",p+cur);
            aton.insert(p+cur);
            cur += std::strlen(p+cur);
        }
        aton.GetFail();
        scanf("%s",s+1);
        aton.find(s);
        //aton.DEBUG();
        int maxx = -0x7ffffff;
        std::queue<int> str;
        for(int i = 1 ; i <= aton.tot ; ++i)
            if(aton.Ma[i])
            {
                if(maxx < ans[i]){
                    while(!str.empty())	str.pop();
                    str.push(i);
                    maxx = ans[i];
                }
                else if(maxx == ans[i]) str.push(i);
            }
        printf("%d\n",maxx);
        while(!str.empty())
            aton.print(str.front()) , str.pop();
        
    }
}

「一本通 2.4 练习 2」Censoring

题目描述

原题来自：USACO 2015 Feb. Gold

有一个长度不超过 10^5105 的字符串 SS。Farmer John 希望在 SS 中删掉 nn 个屏蔽词（一个屏蔽词可能出现多次），这些词记为 t_1\sim t_nt1∼tn。

FJ 在 S 中从头开始寻找屏蔽词，一旦找到一个屏蔽词，FJ 就删除它，然后又从头开始寻找（而不是接着往下找）。FJ 会重复这一过程，直到 S 中没有屏蔽词为止。注意删除一个单词后可能会导致 S 中出现另一个屏蔽词。这 n 个屏蔽词不会出现一个单词是另一个单词子串的情况，这意味着每个屏蔽词在 S 中出现的开始位置是互不相同的，请帮助 FJ 完成这些操作并输出最后的 S。

输入格式

第一行包含一个字符串 S；
第二行包含一个整数 n；
接下来的 n 行，每行包含一个字符串，第 ii 行的字符串是 t_i。

输出格式

一行，输出操作后的 SS。保证 SS 不会变成空串。

样例

样例输入

1
2
3
4
begintheescapexecutionatthebreakofdawn
2
escape
execution

样例输出

1
beginthatthebreakofdawn

数据范围与提示

对于全部数据，

保证所有字符串只出现小写字母。

题解

感觉有点想法。

首先对模式串建立不带Trie图优化的AC自动机（以后再也不想写Trie图优化了）。。。

然后开始对母串匹配（母串一定要读一个字符串方便操作！qwq）

我们在匹配的时候记录母串当前点u匹配到的自动机上的点

，然后假如下一位匹配到了模式串我们用字符串函数将其删除，然后回跳指针至这个单词前一位，令匹配指针u指 向$g(u)$，继续完成匹配，和普通AC自动机匹配复杂度相同（每个点最多被访问和删除一次），为

结果写炸了，以后补代码（咕咕咕）吧。

斜率优化DP

先看一道题

「一本通 5.6 例 1」任务安排 1

题目描述

原题来自：JoyOI TYVJ 1098

有 NN 个任务排成一个序列在一台机器上等待执行，它们的顺序不得改变。机器会把这 NN 个任务分成若干批，每一批包含连续的若干个任务。从时刻 00 开始，任务被分批加工，执行第i个任务所需的时间是 T_iTi。另外，在每批任务开始前，机器需要 SS 的启动时间，故执行一批任务所需的时间是启动时间 SS 加上每个任务所需时间之和。

一个任务执行后，将在机器中稍作等待，直至该批任务全部执行完毕。也就是说，同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数 C_iCi。

请为机器规划一个分组方案，使得总费用最小。

输入格式

第一行是 N。第二行是 S。

下面 NN 行每行有一对正整数，分别为 T_i和 C_i，表示 ii 个任务单独完成所需的时间是 T_i及其费用系数 C_iCi。

输出格式

一个数，最小的总费用。

样例

样例输入

1
2
3
4
5
6
7
5
1
1 3
3 2
4 3
2 3
1 4

样例输出

1
153

样例说明

分组方案为 \{1,2\},\{3\},\{4,5\}则完成时间为 \{5,5,10,14,14\}费用 C=\{15,10,30,42,56\}总费用为 153。

数据范围与提示

对于全部数据

题解

很容易就想到一个

的做法

设

表示前n个任务分p段完成，枚举最后一段人数转移

Code:

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 5005
#define ll long long
ll f[maxn][maxn] , n , s[maxn] , t[maxn] , S;
int main()
{
	scanf("%lld%lld",&n,&S);
	for(int i = 1 ; i <= n ; ++i)
	{
		int x , y;
		scanf("%d%d",&y,&x);
		s[i] = s[i-1] + x , t[i] = t[i-1] + y;
	}
	std::memset(f,0x7f,sizeof(f));
	f[0][0] = 0;
	for(int i = 1 ; i <= n ; ++i)
		for(int j = 1 ; j <= i ; ++j)
			for(int k = 0 ; k <= i ; ++k)
				f[i][j] = std::min(f[i][j] , f[k][j-1] + 1ll * (s[i] - s[k]) * (t[i] + j * S));
	ll ans = 1ll*0x7fffffffff;
	for(int i = 1 ; i <= n ; ++i)
		ans = std::min(ans , f[n][i]);
	printf("%lld",ans);
}

这时有这样一种思想非常重要，在以前的贪心算法中也曾应用（比如种树），就是费用提前计算的思想。

我们设f(k)表示前k项分成若干段的最小费用。

枚举最后的一段转移。

让我再体会一下这种神奇的思想。

时间复杂度

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 5005
#define ll long long
ll f[maxn] , n , s[maxn] , t[maxn] , S;
int main()
{
	scanf("%lld%lld",&n,&S);
	for(int i = 1 ; i <= n ; ++i)
	{
		int x , y;
		scanf("%d%d",&y,&x);
		s[i] = s[i-1] + x , t[i] = t[i-1] + y;
	}
	std::memset(f,0x7f,sizeof(f));
	f[0] = 0;
	for(int i = 1 ; i <= n ; ++i)
		for(int j = 0 ; j <= i ; ++j)
			f[i] = std::min(f[i] , f[j] + S * (s[n] - s[j]) + t[i] * (s[i] - s[j]));
	printf("%lld",f[n]);
}