bef-> NO.36

Veröffentlicht am

NOIp 2015 D2T2 子串

题目描述

有两个仅包含小写英文字母的字符串 AA 和 BB。

现在要从字符串 AA 中取出 kk 个互不重叠的非空子串，然后把这 kk 个子串按照其在字符串 AA 中出现的顺序依次连接起来得到一个新的字符串。请问有多少种方案可以使得这个新串与字符串 BB 相等？

注意：子串取出的位置不同也认为是不同的方案。

输入输出格式

输入格式：

第一行是三个正整数 n,m,k，分别表示字符串 AA 的长度，字符串 BB 的长度，以及问题描述中所提到的 kk，每两个整数之间用一个空格隔开。

第二行包含一个长度为 nn 的字符串，表示字符串 AA。

第三行包含一个长度为 mm 的字符串，表示字符串 BB。

输出格式：

一个整数，表示所求方案数。

由于答案可能很大，所以这里要求输出答案对 1000000007 取模的结果。

输入输出样例

输入样例#1：

1
2
3
6 3 1 
aabaab 
aab

输出样例#1：

1
2

输入样例#2：

1
2
3
6 3 2 
aabaab 
aab

输出样例#2：

1
7

输入样例#3：

1
2
3
6 3 3 
aabaab 
aab

输出样例#3：

1
7

说明

img
对于所有 10 组数据:

题解

一道非常好的计数dp题。

可惜我用将近两个小时设计出状态写出转移只有20分， 离正解很接近，觉得非常可惜。

对母串中的那一位记录选或不选才好转移。

其实我一开始思路是这样的：

表示母串中用k个子串匹配到模式串第j位的方案数。

转移：

如果

不相等就去掉前面的求和式，复杂度

是可以获得70分的好成绩的。

1541402191242

上面那个说的就是我最初能做的。

然后我觉得很麻烦，就猜这个东西有继承性，然后只需要关注前一位，像扫描线（或者说前缀和？）一样

猜成：

很可惜，离正解很接近，但是是错误的，跑样例输出状态值然后自己算就能明白为什么，前一位能不能选不一定是继承所有的方案。

然后变成了20pts。。。考场上一定要写有把握有理有据的算法。

然而我居然没想到常用套路：加一维0/1表示母串当前位选不选，那样我就发现可以转移了。。

首先假设母串当前位不选，那么不管枚举到的匹配对是否相等，都有

考虑当前位相等并且选择母串当前位匹配模式串的话（用递推那种分类讨论的思想！）

  • 当前匹配位独立出一个子串。（上一位不一定选）
  • 当前匹配位与上一个子串合并（要求上一位必须选）。

滚动数组后可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
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 1005
#define maxk 205
#define mod 1000000007
int n , m , k;
long long f[2][maxk][maxk][2];
char s1[maxn] , s2[maxn];
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	getchar();
	scanf("%s",s1+1);
	scanf("%s",s2+1);
	for(int i = 1 ; i <= n ; ++i){
		int now = i & 1;
		std::memset(f[now],0,sizeof(f[now]));
		f[now^1][0][0][0] = 1;
		for(int j = 1 ; j <= m ; ++j){
			for(int t = 1 ; t <= k ; ++t){
				if(s1[i] == s2[j]){
					(f[now][j][t][1] = f[now^1][j-1][t-1][0] + f[now^1][j-1][t][1] + f[now^1][j-1][t-1][1]) %= mod;
					(f[now][j][t][0] = f[now^1][j][t][0] + f[now^1][j][t][1]) %= mod ;
				}
				else{
					f[now][j][t][1] = 0;
					f[now][j][t][0] = f[now^1][j][t][1] + f[now^1][j][t][0];
				}
			}
		}
	}
    printf("%lld",(f[n&1][m][k][0] + f[n&1][m][k][1]) % mod);
}

NOIp 2017 D1T2 时间复杂度

题目描述

小明正在学习一种新的编程语言 A++，刚学会循环语句的他激动地写了好多程序并 给出了他自己算出的时间复杂度，可他的编程老师实在不想一个一个检查小明的程序， 于是你的机会来啦！下面请你编写程序来判断小明对他的每个程序给出的时间复杂度是否正确。

A++语言的循环结构如下：

1
2
3
F i x y
    循环体
E

其中F i x y表示新建变量 ii（变量 ii 不可与未被销毁的变量重名）并初始化为 xx， 然后判断 ii 和 yy 的大小关系，若 ii 小于等于 yy 则进入循环，否则不进入。每次循环结束后 ii 都会被修改成 i +1i+1，一旦 ii 大于 yy 终止循环。

xx 和 yy 可以是正整数（xx 和 yy 的大小关系不定）或变量 nn。nn 是一个表示数据规模的变量，在时间复杂度计算中需保留该变量而不能将其视为常数，该数远大于 100100。

“E”表示循环体结束。循环体结束时，这个循环体新建的变量也被销毁。

注：本题中为了书写方便，在描述复杂度时，使用大写英文字母“O”表示通常意义下“Θ”的概念。

输入输出格式

输入格式：

输入文件第一行一个正整数 tt，表示有 tt（t \le 10t≤10）个程序需要计算时间复杂度。 每个程序我们只需抽取其中 F i x y和E即可计算时间复杂度。注意：循环结构 允许嵌套。

接下来每个程序的第一行包含一个正整数 LL 和一个字符串，LL 代表程序行数，字符 串表示这个程序的复杂度，O(1)表示常数复杂度，O(n^w)表示复杂度为n^wnw，其 中w是一个小于100的正整数（输入中不包含引号），输入保证复杂度只有O(1)和O(n^w) 两种类型。

接下来 LL 行代表程序中循环结构中的F i x y或者 E。 程序行若以F开头，表示进入一个循环，之后有空格分离的三个字符（串）i x y， 其中 ii 是一个小写字母（保证不为nn），表示新建的变量名，xx 和 yy 可能是正整数或 nn ，已知若为正整数则一定小于 100。

程序行若以E开头，则表示循环体结束。

输出格式：

输出文件共 tt 行，对应输入的 tt 个程序，每行输出Yes或No或者ERR（输出中不包含引号），若程序实际复杂度与输入给出的复杂度一致则输出Yes，不一致则输出No，若程序有语法错误（其中语法错误只有: ① F 和 E 不匹配 ②新建的变量与已经存在但未被销毁的变量重复两种情况），则输出ERR 。

注意：即使在程序不会执行的循环体中出现了语法错误也会编译错误，要输出 ERR。

输入输出样例

输入样例#1：

复制

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
8
2 O(1)
F i 1 1
E
2 O(n^1)
F x 1 n
E
1 O(1)
F x 1 n
4 O(n^2)
F x 5 n
F y 10 n
E
E
4 O(n^2)
F x 9 n
E
F y 2 n
E
4 O(n^1)
F x 9 n
F y n 4
E
E
4 O(1)
F y n 4
F x 9 n
E
E
4 O(n^2)
F x 1 n
F x 1 10
E
E

输出样例#1：

复制

1
2
3
4
5
6
7
8
Yes
Yes
ERR
Yes
No
Yes
Yes
ERR

说明

【输入输出样例解释1】

第一个程序 ii 从 1 到 1 是常数复杂度。

第二个程序 xx 从 1 到 nn 是 nn 的一次方的复杂度。

第三个程序有一个 F 开启循环却没有 E 结束，语法错误。

第四个程序二重循环，nn 的平方的复杂度。

第五个程序两个一重循环，nn 的一次方的复杂度。

第六个程序第一重循环正常，但第二重循环开始即终止（因为nn远大于100，100大于4）。

第七个程序第一重循环无法进入，故为常数复杂度。

第八个程序第二重循环中的变量 xx 与第一重循环中的变量重复，出现语法错误②，输出 ERR。

【数据规模与约定】

对于 30\%30%的数据：不存在语法错误，数据保证小明给出的每个程序的前 L/2L/2 行一定为以 F 开头的语句，第 L/2+1L/2+1 行至第 LL 行一定为以 EE 开头的语句，L \le 10L≤10，若 xx、yy 均 为整数，xx 一定小于 yy，且只有 yy 有可能为 nn。

对于 50\%50%的数据：不存在语法错误，L \le 100L≤100，且若 xx、yy 均为整数，xx 一定小于 yy， 且只有 yy 有可能为 nn。

对于 70\%70%的数据：不存在语法错误，L \le 100L≤100。

对于 100\%100%的数据：L \le 100L≤100。

题解

这道模拟题很考验代码能力，写完之后我感觉有些地方一定要注意。

考虑到每年的NOIp都会有模拟题，而且去年难度（也就是本题）相当高。

对于大模拟，能写成函数的一定要写成函数。功能性的并且重用性高的代码一定也要写成函数。这样子就算程序会变长，但是调试会变得非常轻松！！

讲真，一开始我注意这点的话，我可能在考场上两个小时之内切掉它，假如那样的话我就可以在顺利完成第一题的情况下写完第三题30分。第一天230的话啥都稳了（T3考场想不大出正解的感觉。。）

先上一开始写的狗屁不通还得了点分的程序。

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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <stack>
#define maxn 222
#define INF 101010101
int t , n , comp , ans , cur_ans;
std::string s[maxn] , p;
struct Node{
    char var;
    bool valid;
};
std::stack<Node> st;
bool ins[maxn];
inline void print()
{
    printf("%d ",n);
    std::cout<<p;
    putchar(10);
    for(int i = 1 ; i <= n ; ++i)
        std::cout << s[i] << std::endl;
}
inline int calc()
{
    int now = 0 , ans = -1;
    while(now < p.length()){
        while(p[now] == ' ' || p[now] == '\n')	++now;
        if(now == p.length())	break;
        if(p[now] == 'n')	ans = 1;
        if(p[now] >= '0' && p[now] <= '9'){
            if(ans == 1){
                ans = p[now] - 48;
            }
            else ans = 0;
        }
        ++now;
    }
    return ans;
}
inline bool isNum(char ch)
{
    if(ch == 'n' || (ch >= '9' && ch <= '0'))	return true;
    return false;
}
inline int getNum(std::string s , int& i)
{
    int x = 0;
    if(s[i] == 'n')	
        return INF;
    while(i < s.length() && s[i] >= '0' && s[i] <= '9'){
        x = (x << 3) + (x << 1) + s[i] - 48;
        ++i;
    }
    return x;
}
inline bool Constant(int x){
    return x != INF;
}
inline int getComplexity(std::string s)
{
    int ans = -1 , x1 = -1 , x2 = -1;
    for(int i = 0 ; i < s.length() ; ++i){
        if(isNum(s[i])){
            if(!(~x1))	x1 = getNum(s,i);
            else x2 = getNum(s,i);
        }
    }
//	printf("%d %d\n",x1,x2);
    if(x1 == INF)	return ans;
    else if(Constant(x1) && Constant(x2))	return ans = 0;
    else return ans = 1;
}
inline bool isVar(char ch)
{
    if(ch >= 97 && ch <= 122)	return true;
    return false;
}
inline char getName(std::string s)
{
    for(int i = 0 ; i < s.length() ; ++i)
        if(isVar(s[i]))
            return s[i];
}
inline int Mark(char var){
    if(ins[var])	return -1;
    ins[var] = true;
    return 0;
}
inline int Process(int num)
{
    int cur = 0 , pw = -1 , var = -1;
    var = getName(s[num]);
    pw = getComplexity(s[num]);
    int k = Mark(var);
    if(!(~k))	return -1;
    if(pw == -1){
        st.push((Node){var,false});
    }
    else if(pw == 0){
        if(st.size() && st.top().valid == false)	st.push((Node){var , false});
        else st.push((Node){var , true});
    }
    else if(pw == 1){
        if(st.size() && st.top().valid == false)	st.push((Node){var,false});
        else ++cur_ans , ans = std::max(ans , cur_ans) , st.push((Node){var,true});
    }
    ans = std::max(ans , cur_ans);
    return 0;//Normal
}
inline void Expop()
{
    if(st.top().valid == true) --cur_ans;
    ins[st.top().var] = false;
    st.pop();
}
inline int getType(std::string s)
{
    for(int i = 0 ; i < s.length() ; ++i)
        if(s[i] == 'F')	return 1;
        else if(s[i] == 'E')	return 0;
}
inline void solve()
{
    int num = 1;
    while(num <= n){
        int type = getType(s[num]) , judge = 0;
        if(type == 1)
            judge = Process(num);
        else Expop();
        if(judge == -1)	{// from Process
            ans = -1 ; return ;
        }
        ++num;
    }
    if(!st.empty())	ans = -1;
}
int main()
{
    scanf("%d",&t);
    while(~(--t)){
        std::memset(ins,false,sizeof(ins));
        while(!st.empty())	st.pop();
        ans = cur_ans = 0;
        scanf("%d",&n);
        std::cin>>p;
        getchar();
        for(int i = 1 ; i <= n ; ++i)
            getline(std::cin,s[i]);
        comp = calc();
        solve();
        if(ans == -1){
            puts("ERR");
            continue;
        }
        if(ans == comp){
            puts("Yes");
        }
        else puts("No");
    }
}

考场上要头脑清醒。。

上面那个代码每一个函数都是错的。

然后上正确的代码，调试时间并不长，在考场有大样例的情况下最起码能得到80以上的分数。

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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <stack>
#define maxn 2222
#define INF 101010101
int t , n , comp , ans , cur_ans;
std::string s[maxn] , p;
struct Node{
	char var;
	bool valid , is_PWD;
};
std::stack<Node> st;
bool ins[maxn];
inline void print()
{
	printf("%d ",n);
	std::cout<<p;
	putchar(10);
	for(int i = 1 ; i <= n ; ++i)
		std::cout << s[i] << std::endl;
}
inline int getNum(std::string s , int& i)
{
	int x = 0;
	if(s[i] == 'n')	
		return INF;
	while(i < s.length() && s[i] >= '0' && s[i] <= '9'){
		x = (x << 3) + (x << 1) + s[i] - 48;
		++i;
	}
	return x;
}
inline bool isNum(char ch)
{
	if(ch == 'n' || (ch <= '9' && ch >= '0'))	return true;
	return false;
}
inline bool Constant(int x){
	return x != INF;
}
inline int calc()
{
	int now = 0 , ans = -1 , x1 = -1 , x2 = -1;
	for(int i = 0 ; i < p.length() ; ++i){
		if(isNum(p[i])){
			if(!(~x1))	x1 = getNum(p,i);
			else x2 = getNum(p,i);
		}
	}
	if(Constant(x1))	return 0;
	else return x2;
	return ans;
}
inline int getComplexity(std::string s)
{
	int ans = -1 , x1 = -1 , x2 = -1;
	for(int i = 0 ; i < s.length() ; ++i){
		if(isNum(s[i])){
			if(!(~x1))	x1 = getNum(s,i);
			else x2 = getNum(s,i);
		}
	}
	if(x1 > x2)	return -1;
	if(x1 == INF && x2 == INF)	return 0;
	if(Constant(x1) && Constant(x2))	return 0;
	else return ans = 1;
}
inline bool isVar(char ch)
{
	if(ch >= 97 && ch <= 122)	return true;
	return false;
}
inline char getName(std::string s)
{
	for(int i = 0 ; i < s.length() ; ++i)
		if(isVar(s[i]))
			return s[i];
}
inline int Mark(char var){
	if(ins[var])	return -1;
	ins[var] = true;
	return 0;
}
inline int Process(int num)
{
	int cur = 0 , pw = -1 , var = -1;
	var = getName(s[num]);
	pw = getComplexity(s[num]);
	int k = Mark(var);
	if(!(~k))	return -1;
	if(pw == -1){
		st.push((Node){var,false,false});
	}
	else if(pw == 0){
		if(st.size() && st.top().valid == false)	st.push((Node){var , false , false});
		else st.push((Node){var , true , false});
	}
	else if(pw == 1){
		if(st.size() && st.top().valid == false)	st.push((Node){var,false,false});
		else ++cur_ans , ans = std::max(ans , cur_ans) , st.push((Node){var,true,true});
	}
	ans = std::max(ans , cur_ans);
	return 0;//Normal
}
inline int Expop()
{
	if(st.empty())	return -1;
	if(st.top().valid == true && st.top().is_PWD == true) --cur_ans;
	ins[st.top().var] = false;
	st.pop();
	return 0;
}
inline int getType(std::string s)
{
	for(int i = 0 ; i < s.length() ; ++i)
		if(s[i] == 'F')	return 1;
		else if(s[i] == 'E')	return 0;
}
inline void solve()
{
	int num = 1;
	while(num <= n){
		int type = getType(s[num]) , judge = 0;
		if(type == 1)
			judge = Process(num);
		else judge = Expop();
		if(judge == -1)	{// from Process
			ans = -1 ; return ;
		}
		++num;
	}
	if(!st.empty())	ans = -1;
}
int main()
{
//	freopen("time.in","r",stdin);
	scanf("%d",&t);
	while(~(--t)){
		std::memset(ins,false,sizeof(ins));
		while(!st.empty())	st.pop();
		ans = cur_ans = 0;
		scanf("%d",&n);
		std::cin>>p;
		getchar();
		for(int i = 1 ; i <= n ; ++i)
			getline(std::cin,s[i]);
		comp = calc();
		solve();
//		print();
		if(ans == -1){
			puts("ERR");
			continue;
		}
		if(ans == comp){
			puts("Yes");
		}
		else puts("No");
	}
}