Regionals 2011 :: Europe - Northeastern

发表于 | 更新于 | 分类于 ， ， ， | 评论数： | 阅读次数：

题目链接：UVALive 开的比赛链接：VJ A:

ASCII Area

水题。 遇到\或者/就加0.5 当时 . 的时候，要判断是里面还是外面，可以用射线法。

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

Author        :kuangbin

Created Time  :2014/6/28 22:39:40

File Name     :E:\2014ACM\区域赛练习\2011\2011NEERC\A.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

char str[110][110];

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    int n,m;

	while(scanf("%d%d",&n,&m) == 2)

	{

		for(int i = 0;i < n;i++)scanf("%s",str[i]);

		int ans = 0;

		for(int i = 0;i < n;i++)

			for(int j = 0;j < m;j++)

			{

				if(str[i][j] != '.')ans++;

				else

				{

					int cnt = 0;

					for(int k = 0;k < j;k++)

						if(str[i][k] != '.')

							cnt++;

					if(cnt&1)ans += 2;

				}

			}

		printf("%d\n",ans/2);

	}

    return 0;

}
B：

Binary Encoding

很简答的题。 先求出k, 是的 $2^{k}<=m$然后其实用k位表示的有$2*m-2^{k}$个，其余是用k-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
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
/* ***************

Author        :kuangbin

Created Time  :2014/6/28 22:53:11

File Name     :E:\2014ACM\区域赛练习\2011\2011NEERC\B.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

void ouput(int n,int m)

{

	for(int i = m-1;i >= 0;i--)

		if(n&(1<<i))

			printf("1");

		else printf("0");

	printf("\n");

}

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    int m;

	while(scanf("%d",&m) == 1)

	{

		int k = 0;

		while((1<<k) < m)k++;

		int cnt = 2*m - (1<<k);

		for(int i = 0;i < m-cnt;i++)ouput(i,k-1);

		for(int i = m-cnt;i < m;i++)ouput((1<<k) - (m-i),k);

	}

    return 0;

}

C:

Caption

题目比较长，主要是读懂题目，然后去DP。

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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
/* ***************

Author        :kuangbin

Created Time  :2014/7/3 19:35:47

File Name     :E:\2014ACM\区域赛练习\2011\2011NEERC\C.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

char letter[30][33][33];

char cur[33][2020];

char str1[33][1000];

char str[100];

int a[100];

int f1[2010][2020];//表示i-j变为空需要的变换次数

int f2[2010][33];//f2[i][j]表示从第i列开始放第j个字符需要的改变

int dp[2010][33];//dp[i][j]表示第j个字符在第i列开始，前j个字符需要的改变

int pre[2010][33];//记录路径

int num[2010];

int ans[33];

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    int m,n,k,smin,smax;

	while(scanf("%d%d%d%d%d",&m,&n,&k,&smin,&smax) == 5)

	{

		gets(str1[0]);

		for(int i = 0;i < m;i++)

			gets(str1[i]);

		int len = strlen(str1[0]);

		for(int i = 0;i < (len+1)/(k+3);i++)

		{

			for(int x = 0;x < m;x++)

				for(int y = 0;y < k;y++)

					letter[str1[0][i(k+3)]-'A'][x][y] = str1[x][i(k+3)+y+2];

		}

		gets(str);

		int c_cur = strlen(str);

		for(int i = 0;i < m;i++)

			for(int j = 0;j < n;j++)

				cur[i][j] = '.';

		for(int i = 0;i < c_cur;i++)

			scanf("%d",&a[i]);

		int dd = 0;

		for(int i = 0;i < c_cur;i++)

		{

			if(i == 0)dd += a[i];

			else dd += a[i]+k;

			if(str[i] == ' ')continue;

			for(int x = 0;x < m;x++)

				for(int y = 0;y < k;y++)

					cur[x][dd+y] = letter[str[i]-'A'][x][y];

		}

		memset(f1,0,sizeof(f2));

		memset(num,0,sizeof(num));

		for(int i = 0;i < n;i++)

			for(int j = 0;j < m;j++)

				if(cur[j][i] == '*')

					num[i]++;

		for(int i = 0;i < n;i++)

			for(int j = i;j < n;j++)

			{

				if(j == i)f1[i][j] = num[i];

				else f1[i][j] = f1[i][j-1] + num[j];

			}

		gets(str);

		gets(str);

		len = strlen(str);

		for(int i = 0;i <= n-k;i++)

			for(int j = 0;j < len;j++)

			{

				if(str[j] == ' ')f2[i][j] = f1[i][i+k-1];

				else

				{

					f2[i][j] = 0;

					for(int x = 0;x < m;x++)

						for(int y = 0;y < k;y++)

							if(cur[x][i+y] != letter[str[j]-'A'][x][y])

								f2[i][j]++;

				}

			}

		memset(dp,-1,sizeof(dp));

		for(int i = 0;i <= n-k;i++)

		{

			dp[i][0] = f2[i][0] ;

			if(i > 0)dp[i][0] += f1[0][i-1];

			pre[i][0] = -1;

		}

		for(int i = 0;i <= n-k;i++)

			for(int j = 1;j < len;j++)

			{

				for(int x = i - smax - k;x <= i - smin - k;x++)

					if(x >= 0 && dp[x][j-1] != -1)

					{

						int tmp = dp[x][j-1] + f1[x+k][i-1] + f2[i][j];

						if(j == len-1)

							tmp += f1[i+k][n-1];

						if(dp[i][j] == -1 || dp[i][j] > tmp)

						{

							dp[i][j] = tmp;

							pre[i][j] = x; 

						}

					}

			}

		int now = -1;

		for(int i = 0;i <= n;i++)

			if(dp[i][len-1] != -1)

			{

				if(now == -1 || dp[now][len-1] > dp[i][len-1])

					now = i;

			}

		//cout<<now<<endl;

		for(int i = len-1;i > 0;i--)

		{

			ans[i] = now - pre[now][i] - k;

			now = pre[now][i];

		}

		ans[0] = now;

		for(int i = 0;i < len;i++)

		{

			printf("%d",ans[i]);

			if(i == len-1)printf("\n");

			else printf(" ");

		}

	}

    return 0;

}

D:

Dictionary Size

一个字符串前缀后缀的题目。 给了n个字符串。 a dictionary word 就是一个原来的字符串，或者是非空前缀+后缀。 比较难想。 首先肯定是前缀和后缀都建一个字典树。 那么总数就是cnt1*cnt2 (cnt1和cnt2都不包含那个空点。) 这个总数其实不包含 原来字符串的情况。 然后需要排除掉一些重复的。 需要使用等价的思想去排除掉重复的。 看到个证明比较好的。here 这个说明一部分问题，但是并没有完全说明。 注意原串是可以的，但是前缀或者后缀是不可以的。 去重的时候，不要算第一个点。 这样做过去其实刚好把原串的个数加上了。 

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
163
164
165
166
167
/* ***************

Author        :kuangbin

Created Time  :2014/7/3 22:30:10

File Name     :E:\2014ACM\区域赛练习\2011\2011NEERC\D.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

struct Trie

{

	int next[400010][26];

	int root,L;

	int num[26];

	int newnode()

	{

		for(int i = 0;i < 26;i++)next[L][i] = -1;

		return L++;

	}

	void init()

	{

		L = 0;

		root = newnode();

		memset(num,0,sizeof(num));

	}

	void insert(char buf[])

	{

		int len = strlen(buf);

		int now = root;

		for(int i = 0;i < len;i++)

		{

			if(next[now][buf[i]-'a'] == -1)

			{

				next[now][buf[i]-'a'] = newnode();

				if(i > 0)

					num[buf[i]-'a']++;

			}

			now = next[now][buf[i]-'a'];

		}

	}

}tree1,tree2;

char str[100];

int one[100];

int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    int n;

	while(scanf("%d",&n) == 1)

	{

		tree1.init();

		tree2.init();

		memset(one,0,sizeof(one));

		while(n--)

		{

			scanf("%s",str);

			int len = strlen(str);

			if(len == 1)

			{

				one[str[0]-'a']++;

			}

			tree1.insert(str);

			reverse(str,str+len);

			tree2.insert(str);

		}

		long long ans = (long long)(tree1.L-1)*(tree2.L-1);

		for(int i = 0;i < 26;i++)

		{

			if(one[i])ans++;

			ans -= (long long)tree1.num[i]*tree2.num[i];

		}

		cout<<ans<<endl;

	}

    return 0;

}

E:

Eve

题目意思很长，主要是读懂题目 题意不赘述了。 并查集胡搞。

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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
/* ***************

Author        :kuangbin

Created Time  :2014/7/3 22:49:15

File Name     :E:\2014ACM\区域赛练习\2011\2011NEERC\E.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

const int MAXN = 500010;

int F[MAXN];

int find(int x)

{

	if(F[x] == -1)return x;

	return F[x] = find(F[x]);

}

bool alive[MAXN];

int sex[MAXN];

char str[10];

void bing(int u,int v)

{

	int t1 = find(u);

	int t2 = find(v);

	if(t1 != t2)F[t1] = t2;

}

pair<int,int>p[200010];

int a[200010];

int main()

{

	//freopen("in.txt","r",stdin);

	//freopen("out.txt","w",stdout);

	int n;

	while(scanf("%d",&n) == 1)

	{

		memset(F,-1,sizeof(F));

		for(int i = 1;i <= n;i++)

		{

			scanf("%s",str);

			if(str[0] == 'M')sex[i] = 0;

			else sex[i] = 1;

			alive[i] = true;

		}

		int m;

		scanf("%d",&m);

		int id = n;

		for(int i = n+1;i <= n+m;i++)

		{

			int u,v;

			scanf("%d",&u);

			if(u < 0)

			{

				alive[-u] = false;

				continue;

			}

			scanf("%d%s",&v,str);

			++id;

			if(str[0] == 'M')sex[id] = 0;

			else sex[id] = 1;

			alive[id] = true;

			bing(id,v);

		}

		int k;

		scanf("%d",&k);

		int cnt = 0;

		for(int i = 0;i < k;i++)

		{

			scanf("%d%d",&p[i].first,&p[i].second);

			a[cnt++] = p[i].second;

		}

		map<int,int>mp;

		mp.clear();

		sort(a,a+cnt);

		cnt = unique(a,a+cnt) - a;

		for(int i = 0;i < cnt;i++)

			mp[a[i]] = i;

		for(int i = 0;i < k;i++)

		{

			bing(p[i].first,mp[p[i].second]+1+n+m);

		}

		cnt = 0;

		int num = 0;

		for(int i = 1;i <= id;i++)

			if(alive[i])

			{

				a[cnt++] = find(i);

				num++;

			}

		sort(a,a+cnt);

		cnt = unique(a,a+cnt) - a;

		if(cnt == 1)

		{

			printf("YES\n");

			continue;

		}

		int tmp = 0;

		for(int i = 0;i < cnt;i++)

			if(a[i] > n+m)

				tmp++;

		if(tmp > 1)printf("NO\n");

		else printf("POSSIBLY\n");

	}

	return 0;

}

K:

Kingdom Roadmap

题意：给了一颗树，让你加最少的边，使得不存在桥。 很明显需要加的边的数量就是 (leaf + 1)/2 然后需要构造解。 解的构造可以使用类似树形DP的思路。 对于每颗子树，如果有奇数个叶子节点，那么提供1个叶子出来，其余叶子两两连边。 如果有偶数个叶子节点，提供2个叶子出来，其余内部解决。

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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#include <stdio.h>

#include <algorithm>

#include <iostream>

#include <queue>

#include <set>

#include <string.h>

#include <map>

#include <vector>

#include <string>

#include <math.h>

using namespace std;

const int MAXN = 100010;

int ind[MAXN];

struct Edge

{

	int to,next;

}edge[MAXN*2];

int head[MAXN],tot;

void init()

{

	tot = 0;

	memset(head,-1,sizeof(head));

}

void addedge(int u,int v)

{

	edge[tot].to = v;

	edge[tot].next = head[u];

	head[u] = tot++;

}

int size[MAXN];

int one[MAXN],two[MAXN];

int c[MAXN*2];

void dfs(int u,int pre)

{

	size[u] = 0;

	if(ind[u] == 1)

	{

		size[u] = 1;

		one[u] = u;

		two[u] = -1;

		return;

	}

	for(int i = head[u];i != -1;i = edge[i].next)

	{

		int v = edge[i].to;

		if(pre == edge[i].to)continue;

		dfs(edge[i].to,u);

		size[u] += size[edge[i].to];

		

    }
    int cnt = 0;
    for(int i = head\[u\];i != -1;i = edge\[i\].next)
    {
    	int v = edge\[i\].to;
    	if(v == pre)continue;
        if(size\[v\]&1)
    	{
    		c\[cnt++\] = one\[v\];
    	}
    }
    for(int i = head\[u\];i != -1;i = edge\[i\].next)
    {
    	int v = edge\[i\].to;
    	if(v == pre)continue;
    	if((size\[v\]&1) == 0)
    	{
    		c\[cnt++\] = one\[v\];
    		c\[cnt++\] = two\[v\];
    	}
    }
    if(size\[u\] & 1)
    {
    	one\[u\] = c\[cnt-1\];
    	for(int i = 0;i+1 < cnt-1;i+=2)
    	{
    		printf("%d %d\\n",c\[i\],c\[i+1\]);
    	}
    }
    else
    {
    	one\[u\] = c\[cnt-1\];
    	two\[u\] = c\[0\];
    	for(int i = 1;i+1 < cnt-1;i+=2)
    	{
    		printf("%d %d\\n",c\[i\],c\[i+1\]);
    	}
    }
    if(pre == -1)
    {
    	if(size\[u\]&1)printf("%d %d\\n",u,one\[u\]);
    	else printf("%d %d\\n",one\[u\],two\[u\]);
    }

}

int main()

{

	//freopen("in.txt","r",stdin);

	//freopen("out.txt","w",stdout);

    int n, a, b;
    while(scanf("%d",&n) == 1)
    {
    	memset(ind, 0, sizeof ind);
    	init();
    	for(int i=0; i<n-1; i++){
    		scanf("%d%d",&a,&b);
    		ind\[a\] ++;
    		ind\[b\] ++;
    		addedge(a,b);
    		addedge(b,a);
    	}
    	int ans = 0;
    	vector<int> vs;
    	vs.clear();
    	for(int i=1; i<=n; i++){
    		if(ind\[i\] == 1){
    		   	ans++;
    		}
    	}
    	printf("%d\\n",(ans+1)/2);
    	if(n == 2)
    	{
    		printf("1 2\\n");
    		continue;
    	}
    	for(int i = 1;i <= n;i++)
    		if(ind\[i\] > 1)
    		{
    			dfs(i,-1);
    			break;
    		}
    }
    return 0;

}
------ 本文结束------
  • 本文作者： kuangbin
  • 本文链接： 197.html
  • 版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！
0%