【OK】2010 Europe - Northwestern

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

2010 Europe - Northwestern

开的比赛地址：HUST VJ

UVALive 题目链接：here

A:

Fair Division

题目是给n个数，要在每一个数里面取出一部分来，组成和为p的。 尽量平分， 数值大、排在前面的先出。 直接暴力搞就可以了。

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

Author        :kuangbin

Created Time  :2014/5/3 22:57:22

File Name     :E:\2014ACM\区域赛练习\2010\2010NWERC\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;

int a[110];

int order[110];

bool cmp(int t1,int t2)

{

	if(a[t1] != a[t2])return a[t1] > a[t2];

	else return t1 < t2;

}

int b[110];

int main()

{

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

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

    int T;

	int p,n;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d%d",&p,&n);

		int sum = 0;

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

		{

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

			sum += a[i];

		}

		if(sum < p)

		{

			printf("IMPOSSIBLE\n");

			continue;

		}

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

			order[i] = i;

		sort(order,order+n,cmp);

		int t = p/n;

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

		{

			b[i] = min(a[i],t);

			p -= b[i];

		}

		int i = 0;

		while(p)

		{

			while(b[order[i]] == a[order[i]])

				i = (i+1)%n;

			b[order[i]]++;

			i = (i+1)%n;

			p--;

		}

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

		{

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

			if(i < n-1)printf(" ");

			else printf("\n");

		}

	}

    return 0;

}

B：

Free Goodies

题目意思是：有n个东西，Petra and Jan两个人轮流取。 每个东西对两个人各有一个价值。 Petra每次取得原则是取对自己价值最大的，如果相同则取对Jan价值最小的。 Jan取得原则是让最后自己的总价值最大，相同的时候让Prtra的总价值最大。 题目输入了谁先取，以及每个东西对各个人的价值。 求最后他们得到的价值和。 这题其实重要的是Prtea取法简单。 可以把东西按照对Petra价值从大到小，相等则Jan价值从小到大。 然后进行DP， Jan 取得最大价值，前i个里面，Jan最多取一半。 然后进行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
/* ***************

Author        :kuangbin

Created Time  :2014/5/3 23:09:10

File Name     :E:\2014ACM\区域赛练习\2010\2010NWERC\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;

const int MAXN = 1010;

struct Node

{

	int p,j;

	void input()

	{

		scanf("%d%d",&p,&j);

	}

}node[MAXN];

bool cmp(Node a,Node b)

{

	if(a.p != b.p)return a.p > b.p;

	else return a.j < b.j;

}

int dp1[MAXN][MAXN];

int dp2[MAXN][MAXN];

int main()

{

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

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

    int T;

	int n;

	char name[20];

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d%s",&n,name);

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

			node[i].input();

		sort(node+1,node+n+1,cmp);

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

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

		dp1[0][0] = 0;

		dp2[0][0] = 0;

		if(name[0] == 'P')

		{

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

				for(int j = 0;j <= i/2;j++)

				{

					if(j > 0)

					{

						if(dp1[i][j] < dp1[i-1][j-1] + node[i].j || (dp1[i][j] == dp1[i-1][j-1] + node[i].j && dp2[i][j] > dp2[i-1][j-1] + node[i].p))

						{

							dp1[i][j] = dp1[i-1][j-1] + node[i].j;

							dp2[i][j] = dp2[i-1][j-1] + node[i].p;

						}

					}

					if(j <= (i-1)/2)

					{

						if(dp1[i][j] < dp1[i-1][j] || (dp1[i][j] == dp1[i-1][j] && dp2[i][j] > dp2[i-1][j]))

						{

							dp1[i][j] = dp1[i-1][j];

							dp2[i][j] = dp2[i-1][j];

						}

					}

				}

			int sum = 0;

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

				sum += node[i].p;

			printf("%d %d\n",sum-dp2[n][n/2],dp1[n][n/2]);

		}

		else

		{	

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

				for(int j = 0;j <= (i+1)/2;j++)

				{

					if(j > 0)

					{

						if(dp1[i][j] < dp1[i-1][j-1] + node[i].j || (dp1[i][j] == dp1[i-1][j-1] + node[i].j && dp2[i][j] > dp2[i-1][j-1] + node[i].p))

						{

							dp1[i][j] = dp1[i-1][j-1] + node[i].j;

							dp2[i][j] = dp2[i-1][j-1] + node[i].p;

						}

					}

					if(j <= (i)/2)

					{

						if(dp1[i][j] < dp1[i-1][j] || (dp1[i][j] == dp1[i-1][j] && dp2[i][j] > dp2[i-1][j]))

						{

							dp1[i][j] = dp1[i-1][j];

							dp2[i][j] = dp2[i-1][j];

						}

					}

				}

			int sum = 0;

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

				sum += node[i].p;

			printf("%d %d\n",sum-dp2[n][(n+1)/2],dp1[n][(n+1)/2]);

		}

	}

    return 0;

}

C:

High Score

需要将一个全A的字符串，变换为目标串。 现在的位置在第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
82
83
84
85
86
87
88
89
/* ***************

Author        :kuangbin

Created Time  :2014/5/3 23:28:19

File Name     :E:\2014ACM\区域赛练习\2010\2010NWERC\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 str[1010];

int main()

{

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

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

    int T;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%s",str);

		int n = strlen(str);

		int ans1 = 0;

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

			ans1 += min(str[i] - 'A','Z' - str[i] + 1);

		int ans = ans1 + n-1;

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

			if(str[i] == 'A')

			{

				int j = i;

				while(j < n && str[j] == 'A')j++;

				ans = min(ans,ans1 + max(0,i-1)*2 + n - j);

				ans = min(ans,ans1 + max(0,i-1) + 2*(n-j));

			}

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

	}

    return 0;

}

D:

Hill Driving

二分+判断。 二分速度，然后进行判断。 注意下坡的情况。 这题要1e-10才能A， 1e-8WA了好久。

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

Author        :kuangbin

Created Time  :2014/6/5 23:38:01

File Name     :E:\2014ACM\区域赛练习\2010\2010NWERC\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;

const int MAXN = 10010;

const double eps = 1e-10;

const double INF = 1e30;

double x[MAXN],y[MAXN];

int main()

{

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

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

    double a,b,v,f;

	int n;

	int T;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%lf%lf%lf%lf",&a,&b,&v,&f);

		scanf("%d",&n);

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

		{

			scanf("%lf%lf",&x[i],&y[i]);

			x[i] /= 1000;

			y[i] /= 1000;

		}

		double l = 0, r = v;

		double ans = INF;

		bool find = false;

		while(r - l >= eps)

		{

			double mid = (l+r)/2;

			double cost = 0.0;

			double t = 0.0;

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

			{

				if(y[i] >= 0)

				{

					cost += (a*mid+b*y[i]/x[i])*hypot(x[i],y[i]);

					t += hypot(x[i],y[i])/mid;

				}

				else

				{

					cost += max(0.0,a*mid+b*y[i]/x[i])*hypot(x[i],y[i]);

					if( (a*mid+b*y[i]/x[i]) < eps )

						t += hypot(x[i],y[i])/min(v,-b*y[i]/x[i]/a);

					else

						t += hypot(x[i],y[i])/mid;

				}

			}

			//printf("%lf  %lf %lf\n",mid,cost,t);

			if(cost <= f)

			{

				find = true;

				ans = min(ans,t);

				l = mid;

			}

			else r = mid;

		}

		if(!find)printf("IMPOSSIBLE\n");

		else printf("%.8lf\n",ans);

	}

    return 0;

}
E：

Rankings

这题不会有不确定的情况。 因为任意两个之间的先后顺序都是知道的，进行拓扑排序，就可以判断是不是存在了，按照顺序输出就是答案了。

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

Author        :kuangbin

Created Time  :2014/5/6 22:57:39

File Name     :E:\2014ACM\区域赛练习\2010\2010NWERC\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 = 550;

int g[MAXN][MAXN];

int in[MAXN];

bool f[MAXN][MAXN];

int rank[MAXN];

vector<int>ans;

bool used[MAXN];

bool solve(int n)

{

	ans.clear();

	memset(used,false,sizeof(used));

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

	{

		int k = -1;

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

			if(!used[i] && in[i] == 0)

			{

				k = i;

				break;

			}

		if(k == -1)return false;

		used[k] = true;

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

			if(!used[i] && g[k][i])

				in[i]--;

		ans.push_back(k);

	}

	return true;

}

int main()

{

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

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

    int n;

	int T;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d",&n);

		memset(g,0,sizeof(g));

		memset(f,false,sizeof(f));

		int a;

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

		{

			scanf("%d",&a);

			rank[a] = i;

		}

		int m;

		int u,v;

		scanf("%d",&m);

		while(m--)

		{

			scanf("%d%d",&u,&v);

			f[u][v] = true;

		}

		memset(in,0,sizeof(in));

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

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

			{

				if(f[i][j])

				{

					if(rank[i] < rank[j])

					{

						g[i][j] = true;

						in[j]++;

					}

					else

					{

						g[j][i] = true;

						in[i]++;

					}

				}

				else

				{

					if(rank[i] > rank[j])

					{

						g[i][j] = true;

						in[j]++;

					}

					else

					{

						g[j][i] = true;

						in[i]++;

					}

				}

			}

		if(!solve(n))printf("IMPOSSIBLE\n");

		else

		{

			for(int i = ans.size()-1;i >= 0;i--)

			{

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

				if(i > 0)printf(" ");

				else printf("\n");

			}

		}

	}

    return 0;

}
F:

Risk

二分+ 最大流。 使用最大流去判断，经典的网络流构图。 注意二分上界的选取，不要选小了。

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
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
/* ***************

Author        :kuangbin

Created Time  :2014/6/8 10:39:09

File Name     :E:\2014ACM\区域赛练习\2010\2010NWERC\F.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 = 1000;

const int MAXM = 100000;

const int INF = 0x3f3f3f3f;

struct Edge

{

	int to,next,cap,flow;

}edge[MAXM];

int tol;

int head[MAXN];

int gap[MAXN],dep[MAXN],pre[MAXN],cur[MAXN];

void init()

{

	tol = 0;

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

}

void addedge(int u,int v,int w,int rw = 0)

{

	edge[tol].to = v;edge[tol].cap = w;edge[tol].next = head[u];

	edge[tol].flow = 0;head[u] = tol++;

	edge[tol].to = u;edge[tol].cap = rw;edge[tol].next = head[v];

	edge[tol].flow = 0;head[v] = tol++;

}

int sap(int start,int end,int N)

{

	memset(gap,0,sizeof(gap));

	memset(dep,0,sizeof(dep));

	memcpy(cur,head,sizeof(head));

	int u = start;

	pre[u] = -1;

	gap[0] = N;

	int ans = 0;

	while(dep[start] < N)

	{

		if(u == end)

		{

			int Min = INF;

			for(int i = pre[u];i != -1;i = pre[edge[i^1].to])

				if(Min > edge[i].cap - edge[i].flow)

					Min = edge[i].cap - edge[i].flow;

			for(int i = pre[u];i != -1;i = pre[edge[i^1].to])

			{

				edge[i].flow += Min;

				edge[i^1].flow -= Min;

			}

			u = start;

			ans += Min;

			continue;

		}

		bool flag = false;

		int v;

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

		{

			v = edge[i].to;

			if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u])

			{

				flag = true;

				cur[u] = pre[v] = i;

				break;

			}

		}

		if(flag)

		{

			u = v;

			continue;

		}

		int Min = N;

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

			if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min)

			{

				Min = dep[edge[i].to];

				cur[u] = i;

			}

		gap[dep[u]]--;

		if(!gap[dep[u]])return ans;

		dep[u] = Min+1;

		gap[dep[u]]++;

		if(u != start)u = edge[pre[u]^1].to;

	}

	return ans;

}

int a[110];

char g[110][110];

bool f[110];

int main()

{

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

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

    int n,T;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d",&n);

		for(int i = 0;i < n;i++)scanf("%d",&a[i]);

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

		memset(f,false,sizeof(f));

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

			if(a[i] == 0)

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

					if(g[i][j] == 'Y' && a[j] > 0)

						f[j] = true;

		int ans;

		int l = 1, r = 100000;

		while(l <= r)

		{

			int mid = (l+r)/2;

			init();

			int start = 2*n;

			int end = 2*n+1;

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

				if(a[i] > 0)

					addedge(start,2*i,a[i]);

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

				if(a[i] > 0)

					addedge(2*i,2*i+1,INF);

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

				if(a[i])

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

						if(a[j] && g[i][j] == 'Y')

							addedge(2*i,2*j+1,INF);

			int sum = 0;

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

				if(a[i])

				{

					if(f[i])

					{

						addedge(2*i+1,end,mid);

						sum += mid;

					}

					else

					{

						addedge(2*i+1,end,1);

						sum += 1;

					}

				}

			if(sap(start,end,2*n+2) == sum)

			{

				ans = mid;

				l = mid+1;

			}

			else r = mid-1;

		}

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

	}

    return 0;

}
G:

Selling Land

这题主要是要看懂题目。 看懂了发现就是DP。 对每个空格子进行DP，找一个以这个格子为右下角的周长最长的矩形。 这题使用单调队列进行优化的做法非常经典，赞！！！！！新技能get 具体看代码吧。

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

Author        :kuangbin

Created Time  :2014/6/8 23:04:48

File Name     :E:\2014ACM\区域赛练习\2010\2010NWERC\G.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 = 1010;

char str[MAXN][MAXN];

int up[MAXN][MAXN];

int ans[4*MAXN];

int que[MAXN];

int a[MAXN];

int id[MAXN];

int b[MAXN];

int main()

{

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

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

    int n,m;

	int T;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d%d",&n,&m);

		memset(ans,0,sizeof(ans));

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

		{

			scanf("%s",str[i]);

			int top = 0;

			id[top] = -1;

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

			{

				if(str[i][j] == '#')up[i][j] = 0;

				else

				{

					if(i == 0)up[i][j] = 1;

					else up[i][j] = up[i-1][j] + 1;

				}

				if(up[i][j] == 0)

				{

					top = 0;

					id[top] = j;

					continue;

				}

				while(top > 0 && a[top] >= up[i][j])top--;

				a[++top] = up[i][j];

				id[top] = j;

				b[top] = a[top] - id[top-1];

				if(top > 1)b[top] = max(b[top],b[top-1]);

				int tmp = 2*(j+b[top]);

				ans[tmp]++;

			}

		}

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

			if(ans[i])

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

	}

    return 0;

}

H: 就是简单的模拟，读懂题意就可以了。

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
#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <set>

#include <iostream>

#include <queue>

#include <map>

#include <math.h>

#include <string>

using namespace std;

struct Node

{

	int x,y;

	int type;

}node[1010];

char op[20];

int sell[1010];

int buy[1010];

int main()

{

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

	int T;

	int n;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d",&n);

		memset(sell,0,sizeof(sell));

		memset(buy,0,sizeof(buy));

		int last = -1;

		int ans1 = -1;

		int ans2 = -1;

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

		{

			scanf("%s %d shares at %d",op,&node[i].x,&node[i].y);

			if(op[0] == 's')node[i].type = 0;

			else node[i].type = 1;

			if(node[i].type == 0)sell[node[i].y] += node[i].x;

			else buy[node[i].y] += node[i].x;

			ans1 = -1;

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

				if(sell[j])

				{

					ans1 = j;

					break;

				}

			ans2 = -1;

			for(int j = 1000;j>=1;j--)

				if(buy[j])

				{

					ans2 = j;

					break;

				}

			while(ans1 != -1 && ans2 != -1&& ans2 >= ans1)

			{

				last = ans1;

				int tmp = min(sell[ans1],buy[ans2]);

				sell[ans1] -= tmp;

				buy[ans2] -= tmp;

				ans1 = -1;

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

					if(sell[j])

					{

						ans1 = j;

						break;

					}

				ans2 = -1;

				for(int j = 1000;j>=1;j--)

					if(buy[j])

					{

						ans2 = j;

						break;

					}

			}

			ans1 = -1;

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

				if(sell[j])

				{

					ans1 = j;

					break;

				}

			ans2 = -1;

			for(int j = 1000;j>=1;j--)

				if(buy[j])

				{

					ans2 = j;

					break;

				}

			if(ans1 == -1)printf("- ");

			else printf("%d ",ans1);

			if(ans2 == -1)printf("- ");

			else printf("%d ",ans2);

			if(last == -1)printf("-\n");

			else printf("%d\n",last);

		}

	}

	return 0;

}

I：

Telephone Network

题目意思大致是 看那个图就知道了。 N输入，N输出的网络。N = 2^k 不停地分层。 2^k 输入输出的网络分成两个2^(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
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
/* ***************

Author        :kuangbin

Created Time  :2014/6/14 10:49:42

File Name     :E:\2014ACM\区域赛练习\2010\2010NWERC\I.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;

pair<int,int>p[100010];

int Index[100010];

int tmpIndex[100010];

int ans[100010];

vector<int>vec[100010];

int color[100010];

bool dfs(int u,int col)

{

	color[u] = col;

	int sz = vec[u].size();

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

	{

		int v = vec[u][i];

		if(color[v] != -1)

		{

			if(color[v] == col)return false;

			continue;

		}

		if(!dfs(v,!col))return false;

	}

	return true;

}

struct Node

{

	int val;

	int id;

}node[100010];

bool cmp(Node a,Node b)

{

	return a.val < b.val;

}

void solve(int n,int l,int r)

{

	if(n == 0)return;

	if(l >= r)return;

	for(int i = l;i < r;i++)

		vec[i].clear();

	int cnt = 0;

	for(int i = l;i < r;i++)

	{

		node[cnt].val = (p[Index[i]].first & ((1<<(n-1))-1) );

		node[cnt].id = i;

		cnt++;

	}

	sort(node,node+cnt,cmp);

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

		if(node[i-1].val == node[i].val)

		{

			vec[node[i-1].id].push_back(node[i].id);

			vec[node[i].id].push_back(node[i-1].id);

		}

	cnt = 0;

	for(int i = l;i < r;i++)

	{

		node[cnt].val = (p[Index[i]].second & ((1<<(n-1))-1));

		node[cnt].id = i;

		cnt++;

	}

	sort(node,node+cnt,cmp);

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

		if(node[i-1].val == node[i].val)

		{

			vec[node[i-1].id].push_back(node[i].id);

			vec[node[i].id].push_back(node[i-1].id);

		}

	for(int i = l;i < r;i++)color[i] = -1;

	for(int i = l;i < r;i++)

		if(color[i] == -1)

			dfs(i,0);

	int cnt1 = l;

	for(int i = l;i < r;i++)

		if(color[i] == 0)

		{

			tmpIndex[cnt1++] = Index[i];

		}

	int cnt2 = cnt1;

	for(int i = l;i < r;i++)

		if(color[i] == 1)

		{

			tmpIndex[cnt2++] = Index[i];

			ans[Index[i]] += (1<<(n-1));

		}

	for(int i = l;i < r;i++)Index[i] = tmpIndex[i];

	solve(n-1,l,cnt1);

	solve(n-1,cnt1,r);

}

int main()

{

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

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

    int n,m;

	int T;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d%d",&n,&m);

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

		{

			Index[i] = i;

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

		}

		memset(ans,0,sizeof(ans));

		solve(n,0,m);

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

		{

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

			if(i < m-1)printf(" ");

			else printf("\n");

		}

	}

    return 0;

}
J：

Wormly

比较简单的题目，模拟下。 贪心往前移动就可以了。

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

Author        :kuangbin

Created Time  :2014/6/14 11:44:30

File Name     :E:\2014ACM\区域赛练习\2010\2010NWERC\J.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 = 1000010;

int loc[MAXN];

int pre[MAXN];

char str[MAXN];

int main()

{

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

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

    int L,b,n;

	int T;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d%d%d",&L,&b,&n);

		scanf("%s",str+1);

		int cnt = 0;

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

		{

			if(str[i] == '1')

			{

				loc[cnt] = i;

				cnt++;

			}

			if(cnt >= L)pre[i] = loc[cnt-L];

			else pre[i] = -1;

		}

		long long ans = 0;

		int now_head = b;

		if(pre[now_head] > 1)ans += L;

		while(now_head != n)

		{

			int tmp = pre[now_head];

			int next_head = min(n,tmp+b-1);

			if(next_head == now_head)break;

			ans += next_head - now_head;

			if(pre[next_head] > pre[now_head])

				ans += L;

			now_head = next_head;

		}

		if(now_head != n)printf("IMPOSSIBLE\n");

		else cout<<ans<<endl;

	}

    return 0;

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