2002-2003 ACM-ICPC Northeastern European Regional Contest (NEERC 02)

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

做了几套题，先来总结一套题。 NEERC2002 题目链接：http://codeforces.com/gym/100002 A 题意：N个数，按照字典序进行排列。Q(N,K)表示数K的位置。 现在给出K,M。 求最小的N，使得 Q(N,K)=M. 不存在输出0. 很明显进行二分答案。然后求Q(N,K) 和 M去比较。 我是用了数位DP的方法去算的Q(N,K)。也可以直接去求。

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  :2015/2/26 22:05:49

File Name     :E:\2015ACM\比赛练习\GYM\NEERC02\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;

long long dp[100][100];

int bit1[100];

int bit2[100];

int cnt1,cnt2;

long long dfs(int tot,int pos,int cnt2,bool f1,bool f2){

	if(pos >= tot)return 1;

	if(pos >= cnt2 && f2)return tot==cnt2;

	if(!f1 && !f2 && dp[tot][pos] != -1)return dp[tot][pos];

	int end = 9;

	if(f1)end = min(end,bit1[tot-1-pos]);

	if(f2)end = min(end,bit2[cnt2-1-pos]);

	long long ans = 0;

	for(int i = 0;i <= end;i++){

		if(pos == 0 && i == 0)continue;

		ans += dfs(tot,pos+1,cnt2,f1 && i == bit1[tot-1-pos],f2 && i == bit2[cnt2-1-pos]);

	}

	if(!f1 && !f2)dp[tot][pos] = ans;

	return ans;

}

long long calc(long long n,long long K){

	cnt1 = 0;

	while(n){

		bit1[cnt1++] = n%10;

		n /= 10;

	}

	cnt2 = 0;

	while(K){

		bit2[cnt2++] = K%10;

		K /= 10;

	}

	long long ans = 0;

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

		ans += dfs(i,0,cnt2,i==cnt1,1);

	return ans;

}

int main()

{

    freopen("amusing.in","r",stdin);

    freopen("amusing.out","w",stdout);

    int K,M;

	while(scanf("%d%d",&K,&M) == 2){

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

		long long ans = 0;

		long long l = K;

		long long r = 1000000000000000000LL;

		while(l <= r){

			long long mid = (l+r)/2;

			long long tmp = calc(mid,K);

			if(tmp == M)ans = mid;

			if(tmp >= M)r = mid-1;

			else l = mid+1;

		}

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

	}

    return 0;

}

B： 题意：一个A*B*C的长方体。有一个D*E的口，深度无穷大的洞。 问这个长方体能不能放进洞里面。 其实很容易去发现放的最优方案肯定是直着放下去的。因为倾斜会导致增大。 所以取出最小的两条边。然后转化为二维的判断。就是A*B的矩形能不能放在D*E的矩形里面。 我的做法是让他们中心对齐，然后进行旋转放进去。 简单粗暴做法是枚举转的角度。然后乱搞判断。

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  :2015/2/27 12:29:16

File Name     :E:\2015ACM\比赛练习\GYM\NEERC02\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 double eps = 1e-8;

const double pi = acos(-1.0);

inline double sqr(double x){

	return x*x;

}

int sgn(double x){

	if(fabs(x) < eps)return 0;

	if(x < 0)return -1;

	else return 1;

}

bool check(double a,double b,double d,double e){

	if(sgn(a-d) <= 0 && sgn(b-e) <= 0)return true;

	double r = sqrt(sqr(a/2)+sqr(b/2));

	double tr = sqrt(sqr(d/2)+sqr(e/2));

	if(sgn(r-tr) > 0)return false;

	double st;

	if(sgn(r-d/2) <= 0)st = 0;

	else st = acos(d/2/r);

	double ed;

	if(sgn(r-e/2) <= 0)ed = pi/2;

	else ed = pi/2-acos(e/2/r);

	double jiao = 2*atan(a/b);

	double s1 = st+jiao;

	double e1 = ed+jiao;

	double s2 = pi-ed;

	double e2 = pi-st;

	if((sgn(s1-e2) > 0 || sgn(s2-e1) > 0) && (sgn(s1-ed) > 0 || sgn(st-e1) > 0))return false;

	else return true;

}

int main()

{

    freopen("bricks.in","r",stdin);

    freopen("bricks.out","w",stdout);

    double a,b,c,d,e;

	while(scanf("%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e) == 5){

		if(a > b)swap(a,b);

		if(a > c)swap(a,c);

		if(b > c)swap(b,c);

		if(d > e)swap(d,e);

		if(check(a,b,d,e))printf("YES\n");

		else printf("NO\n");

	}

    return 0;

}

C： 题意：在W*H的格点中，有一些格点有树。要找一个最大的正方形，不包含树。 点比较少，可以进行离散化，得到一些关键的x坐标和y坐标。 然后枚举每个点作为左下角， 然后枚举每个点就可以了。 水题。

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

Author        :kuangbin

Created Time  :2015/2/26 20:04:17

File Name     :E:\2015ACM\比赛练习\GYM\NEERC02\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;

int N,W,H;

pair<int,int>p[110];

int x[110],y[110];

bool check(int x0,int y0,int L){

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

		if(p[i].first > x0 && p[i].first < x0+L && p[i].second > y0 && p[i].second < y0+L)

			return false;

	return true;

}

int main()

{

    freopen("cricket.in","r",stdin);

    freopen("cricket.out","w",stdout);

    while(scanf("%d%d%d",&N,&W,&H) == 3){

		int cnt1 = 0, cnt2 = 0;

		for(int i = 0;i < N;i++){

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

			x[cnt1++] = p[i].first;

			y[cnt2++] = p[i].second;

		}

		x[cnt1++] = 0;

		x[cnt1++] = W;

		y[cnt2++] = 0;

		y[cnt2++] = H;

		sort(x,x+cnt1);

		sort(y,y+cnt2);

		cnt1 = unique(x,x+cnt1)-x;

		cnt2 = unique(y,y+cnt2)-y;

		int ansx,ansy;

		int L = 0;

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

			for(int j = 0;j < cnt2;j++){

				int x0 = x[i];

				int y0 = y[j];

				int l = 0;

				int r = min(W-x0,H-y0);

				int ans = 0;

				while(l <= r){

					int mid = (l+r)/2;

					if(check(x0,y0,mid)){

						ans = mid;

						l = mid+1;

					}

					else r = mid-1;

				}

				if(ans > L){

					ansx = x0;

					ansy = y0;

					L = ans;

				}

			}

		printf("%d %d %d\n",ansx,ansy,L);

	}

    return 0;

}

D： 题意很长。就是进行了异或编码。然后前面加了一个32，要求密匙。 直接搞就是了。阅读理解题。

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

Author        :kuangbin

Created Time  :2015/2/26 19:44:14

File Name     :E:\2015ACM\比赛练习\GYM\NEERC02\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 = 20010;

char str1[MAXN],str2[MAXN];

int a[MAXN];

int b[MAXN];

int c[MAXN];

int get(char ch){

	if(ch >= '0' && ch <= '9')return ch-'0';

	else return ch-'A'+10;

}

int main()

{

    freopen("decode.in","r",stdin);

    freopen("decode.out","w",stdout);

    while(scanf("%s%s",str1,str2) == 2){

		int n = strlen(str1);

		n /= 2;

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

			a[i] = 16*get(str1[2*i])+get(str1[2*i+1]);

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

			b[i] = 16*get(str2[2*i])+get(str2[2*i+1]);

		c[0] = 32^b[0];

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

			c[i] = c[i-1]^a[i-1]^b[i];

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

			printf("%X%X",c[i]/16,c[i]%16);

		}

		printf("\n");

	}

    return 0;

}

E： 题意：题意很长。其实就是一个最小费用最大流的模型。 然后给了一组方案，问是不是最优方案，如果不是，给我一组更优的方案就可以了。 这题我是直接粗暴地用最小费用最大流去搞，得到的最小费用和给出方案的最小费用进行比较。 其实可以直接在残留网络里面找一个负环，然后负环上面都+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
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
/* ***************

Author        :kuangbin

Created Time  :2015/2/27 14:46:37

File Name     :E:\2015ACM\比赛练习\GYM\NEERC02\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 = 220;

const int MAXM = 22000;

const int INF = 0x3f3f3f3f;

struct Edge{

	int to,next,cap,flow,cost;

	Edge(int _to = 0,int _next = 0,int _cap = 0,int _flow = 0,int _cost = 0):

		to(_to),next(_next),cap(_cap),flow(_flow),cost(_cost){}

}edge[MAXM];

struct ZKW_MinCostMaxFlow{

	int head[MAXN],tot;

	int cur[MAXN];

	int dis[MAXN];

	bool vis[MAXN];

	int ss,tt,N;

	int min_cost,max_flow;

	void init(){

		tot = 0;

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

	}

	void addedge(int u,int v,int cap,int cost){

		edge[tot] = Edge(v,head[u],cap,0,cost);

		head[u] = tot++;

		edge[tot] = Edge(u,head[v],0,0,-cost);

		head[v] = tot++;

	}

	int aug(int u,int flow){

		if(u == tt)return flow;

		vis[u] = true;

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

			int v = edge[i].to;

			if(edge[i].cap > edge[i].flow && !vis[v] && dis[u] == dis[v]+edge[i].cost){

				int tmp = aug(v,min(flow,edge[i].cap-edge[i].flow));

				edge[i].flow += tmp;

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

				cur[u] = i;

				if(tmp)return tmp;

			}

		}

		return 0;

	}

	bool modify_label(){

		int d = INF;

		for(int u = 0;u < N;u++)

			if(vis[u])

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

					int v = edge[i].to;

					if(edge[i].cap > edge[i].flow && !vis[v])

						d = min(d,dis[v]+edge[i].cost-dis[u]);

				}

		if(d == INF)return false;

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

			if(vis[i]){

				vis[i] = false;

				dis[i] += d;

			}

		return true;

	}

	pair<int,int> mincostmaxflow(int start,int end,int n){

		ss = start, tt = end, N = n;

		min_cost = max_flow = 0;

		for(int i = 0;i < n;i++)dis[i] = 0;

		while(1){

			for(int i = 0;i < n;i++)cur[i] = head[i];

			while(1){

				for(int i = 0;i < n;i++)vis[i] = false;

				int tmp = aug(ss,INF);

				if(tmp == 0)break;

				max_flow += tmp;

				min_cost += tmp*dis[ss];

			}

			if(!modify_label())break;

		}

		return make_pair(min_cost,max_flow);

	}

}solve;

struct Node{

	int x,y;

	int num;

	void input(){

		scanf("%d%d%d",&x,&y,&num);

	}

	int distance(Node b){

		return abs(x-b.x)+abs(y-b.y)+1;

	}

}node1[MAXN],node2[MAXN];

int a[MAXN][MAXN];

int id[MAXN][MAXN];

int main()

{

    freopen("evacuate.in","r",stdin);

    freopen("evacuate.out","w",stdout);

    int n,m;

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

		solve.init();

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

			node1[i].input();

			solve.addedge(0,i,node1[i].num,0);

		}

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

			node2[i].input();

			solve.addedge(n+i,n+m+1,node2[i].num,0);

		}

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

			for(int j = 1;j <= m;j++){

				id[i][j] = solve.tot;

				solve.addedge(i,n+j,INF,node1[i].distance(node2[j]));

			}

		int tmp = 0;

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

			for(int j = 1;j <= m;j++){

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

				tmp += a[i][j]*node1[i].distance(node2[j]);

			}

		pair<int,int>pp = solve.mincostmaxflow(0,n+m+1,n+m+2);

		if(pp.first == tmp)printf("OPTIMAL\n");

		else {

			printf("SUBOPTIMAL\n");

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

				for(int j = 1;j <= m;j++){

					printf("%d",edge[id[i][j]].flow);

					if(j < m)printf(" ");

					else printf("\n");

				}

			}

		}

	}

    return 0;

}

F： 题意：给了一个字符串。要把字符串进行压缩。 长度不超过100，直接进行区间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
/* ***************

Author        :kuangbin

Created Time  :2015/2/26 20:29:05

File Name     :E:\2015ACM\比赛练习\GYM\NEERC02\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 = 110;

string ss[MAXN][MAXN];

char str[MAXN];

void kmp_pre(char x[],int m,int next[]){

	int i,j;

	j = next[0] = -1;

	i = 0;

	while(i < m){

		while(-1 != j && x[i] != x[j])j = next[j];

		next[++i] = ++j;

	}

}

int next[MAXN];

char str2[MAXN];

string num2str(int n){

	string ret = "";

	while(n){

		ret = (char)('0'+n%10)+ret;

		n /= 10;

	}

	return ret;

}

int main()

{

    freopen("folding.in","r",stdin);

    freopen("folding.out","w",stdout);

    while(scanf("%s",str) == 1){

		int n = strlen(str);

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

			ss[i][i] = string("") + str[i];

		}

		for(int i = n-1;i >= 0;i--){

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

				ss[i][j] = "";

				int cnt = 0;

				for(int k = i;k <= j;k++){

					ss[i][j] += str[k];

					str2[cnt++] = str[k];

				}

				int len = j-i+1;

				kmp_pre(str2,len,next);

				if(next[len] > 0 && len%(len-next[len]) == 0){

					string tmp = "";

					tmp += num2str(len/(len-next[len]));

					tmp += '(';

					tmp += ss[i][i+len-next[len]-1];

					tmp += ')';

					if(tmp.length() < ss[i][j].length())

						ss[i][j] = tmp;

				}

				for(int k = i;k < j;k++){

					string tmp = ss[i][k]+ss[k+1][j];

					if(tmp.length() < ss[i][j].length())

						ss[i][j] = tmp;

				}

			}

		}

		cout<<ss[0][n-1]<<endl;

	}

    return 0;

}

G： 题意：三维空间里面，有一些球。这些球都在x>= 0,y>=0,z >=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
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
/* ***************

Author        :kuangbin

Created Time  :2015/2/28 0:00:57

File Name     :E:\2015ACM\比赛练习\GYM\NEERC02\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 double eps = 1e-8;

int sgn(double x){

	if(fabs(x) < eps)return 0;

	if(x < 0)return -1;

	else return 1;

}

struct Point3{

	double x,y,z;

	Point3(double _x = 0,double _y = 0,double _z = 0){

		x = _x; y = _y; z = _z;

	}

	double len(){

		return sqrt(x*x+y*y+z*z);

	}

	Point3 operator -(const Point3 &b)const{

		return Point3(x-b.x,y-b.y,z-b.z);

	}

	Point3 operator +(const Point3 &b)const{

		return Point3(x+b.x,y+b.y,z+b.z);

	}

	Point3 operator *(const double &k)const{

		return Point3(x*k,y*k,z*k);

	}

	double operator *(const Point3 &b)const{

		return x*b.x+y*b.y+z*b.z;

	}

	Point3 operator ^(const Point3 &b)const{

		return Point3(y*b.z-z*b.y,z*b.x-x*b.z,x*b.y-y*b.x);

	}

	Point3 trunc(double r){

		double l = len();

		if(!sgn(l))return *this;

		r /= l;

		return Point3(x*r,y*r,z*r);

	}

};

struct Node{

	Point3 p;

	double cosV;

}node[110];

int n;

vector<int>ans;

void check(Point3 p0){

	vector<int>tmp;

	tmp.clear();

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

		double tt = p0*node[i].p;

		if(sgn(tt-node[i].cosV) >= 0)

			tmp.push_back(i+1);

	}

	if(tmp.size() > ans.size())

		ans = tmp;

}

void check(int i,int j){

	double cos1 = node[i].p*node[j].p;

	if(sgn(cos1-1) == 0)return;

	double sin1 = sqrt(1-cos1*cos1);

	double c0 = (node[i].cosV-node[j].cosV*cos1)/sin1/sin1;

	double c1 = (node[j].cosV-node[i].cosV*cos1)/sin1/sin1;

	Point3 cen = (node[i].p*c0)+(node[j].p*c1);

	Point3 vp = node[i].p^node[j].p;

	double vplen = 1-cen.len()*cen.len();

	if(sgn(vplen) >= 0){

		if(vplen < 0)vplen = 0;

		vplen = sqrt(vplen);

		vp = vp.trunc(vplen);

		check(cen+vp);

		check(cen-vp);

	}

}

int main()

{

    freopen("ghosts.in","r",stdin);

    freopen("ghosts.out","w",stdout);

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

		Point3 p0;

		double r;

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

			scanf("%lf%lf%lf",&p0.x,&p0.y,&p0.z);

			scanf("%lf",&r);

			double d = p0.len();

			node[i].cosV = sqrt(d*d-r*r)/d;

			node[i].p = p0.trunc(1);

		}

		ans.clear();

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

			check(node[i].p);

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

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

				check(i,j);

		int sz = ans.size();

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

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

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

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

			else printf("\n");

		}

	}

    return 0;

}

H： 直接进行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
/* ***************

Author        :kuangbin

Created Time  :2015/2/28 1:11:39

File Name     :E:\2015ACM\比赛练习\GYM\NEERC02\H.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 n;

int HPH,MPH,HPM,NM,V,dH;

int L[20];

int dp[12][110][55][110];

int pre[12][110][55][110];

int solve(int now,int hph,int mph,int val){

	if(dp[now][hph][mph][val] != -1)

		return dp[now][hph][mph][val];

	if(mph == 0)return dp[now][hph][mph][val] = 0;

	int _now,_hph,_mph,_val;

	_now = now;

	_hph = hph;

	_mph = mph-1;

	_val = val-L[now];

	if(_val <= 0){

		pre[now][hph][mph][val] = -1;

		return dp[now][hph][mph][val] = 1;

	}

	\_now -= min(_now-1,V);

	if(_now == 1){

		\_hph -= (_val+HPM-1)/HPM;

	}

	if(_hph > 0 && solve(_now,_hph,_mph,_val)){

		pre[now][hph][mph][val] = -1;

		return dp[now][hph][mph][val] = 1;

	}

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

		_now = i;

		_hph = hph;

		_mph = mph-1;

		_val = val;

		\_now -= min(_now-1,V);

		if(_now == 1)

			\_hph -= (_val+HPM-1)/HPM;

		if(_hph > 0 && solve(_now,_hph,_mph,_val)){

			pre[now][hph][mph][val] = i;

			return dp[now][hph][mph][val] = 1;

		}

	}

	_now = now;

	_hph = min(HPH,hph+dH);

	_mph = mph-1;

	_val = val;

	\_now -= min(_now-1,V);

	if(_now == 1)

		\_hph -= (_val+HPM-1)/HPM;

	if(_hph > 0 && solve(_now,_hph,_mph,_val)){

		pre[now][hph][mph][val] = -2;

		return dp[now][hph][mph][val] = 1;

	}

	return dp[now][hph][mph][val] = 0;

}

int main()

{

    freopen("heroes.in","r",stdin);

    freopen("heroes.out","w",stdout);

    while(scanf("%d%d%d%d%d%d%d",&n,&HPH,&MPH,&HPM,&NM,&V,&dH) == 7){

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

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

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

		int now,hph,mph,val;

		now = n;

		hph = HPH;

		mph = MPH;

		val = HPM*NM;

		if(!solve(now,hph,mph,val))printf("DEFEATED\n");

		else {

			printf("VICTORIOUS\n");

			while(1){

				if(pre[now][hph][mph][val] == -1){

					printf("L\n");

					mph--;

					val -= L[now];

					if(val <= 0)break;

					now -= min(now-1,V);

					if(now == 1)

						hph -= (val+HPM-1)/HPM;

				}

				else if(pre[now][hph][mph][val] > 0){

					printf("T %d\n",pre[now][hph][mph][val]);

					now = pre[now][hph][mph][val];

					mph--;

					now -= min(now-1,V);

					if(now == 1)

						hph -= (val+HPM-1)/HPM;

				}

				else {

					printf("H\n");

					hph = min(HPH,hph+dH);

					mph--;

					now -= min(now-1,V);

					if(now == 1)

						hph -= (val+HPM-1)/HPM;

				}

			}

		}

	}

    return 0;

}

I： 题意：就是网格上交了一些垂直或者水平的线，还有一些45度的线。问可以分割出多少个等腰直接三角形。 枚举每个直角，往外扩展去判断。

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

Author        :kuangbin

Created Time  :2015/2/28 10:36:29

File Name     :E:\2015ACM\比赛练习\GYM\NEERC02\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;

int n,m,k;

bool horis[110][110];

bool verts[110][110];

bool dign1[110][110];

bool dign2[110][110];

bool hashoris[110];

bool hasverts[110];

bool hasdign1[220];

bool hasdign2[220];

bool inside(int x,int y){

	return x >= 0 && x <= n && y >= 0 && y <= m;

}

bool hasline(int x1,int y1,int x2,int y2){

	if(y1 == y2)return hashoris[y1];

	if(x1 == x2)return hasverts[x1];

	if(x1-y1 == x2-y2)return hasdign1[x1-y1+110];

	if(x1+y1 == x2+y2)return hasdign2[x1+y1];

}

//除了这个方向不能有其他线

bool check(int x,int y,int dx,int dy){

	if(dy == 0){

		if(verts[x][y] || dign1[x][y] || dign2[x][y])return false;

	}

	if(dx == 0){

		if(horis[x][y] || dign1[x][y] || dign2[x][y])return false;

	}

	if(dx == dy){

		if(horis[x][y] || verts[x][y] || dign2[x][y])return false;

	}

	if(dx == -dy){

		if(horis[x][y] || verts[x][y] || dign1[x][y])return false;

	}

	return true;

}

bool check(int x,int y,int dx1,int dy1,int dx2,int dy2){

	int x1 = x+dx1, y1 = y+dy1;

	int x2 = x+dx2, y2 = y+dy2;

	while(1){

		if(!inside(x1,y1) || !inside(x2,y2))return false;

		if(hasline(x1,y1,x2,y2))return true;

		if(!check(x1,y1,dx1,dy1) || !check(x2,y2,dx2,dy2))return false;

		x1 += dx1;

		y1 += dy1;

		x2 += dx2;

		y2 += dy2;

	}

	return false;

}

int main()

{

    freopen("inlay.in","r",stdin);

    freopen("inlay.out","w",stdout);

    while(scanf("%d%d%d",&n,&m,&k) == 3){

		n *= 2; m *= 2;

		memset(hashoris,0,sizeof(hashoris));

		memset(hasverts,0,sizeof(hasverts));

		memset(hasdign1,0,sizeof(hasdign1));

		memset(hasdign2,0,sizeof(hasdign2));

		int x1,y1,x2,y2;

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

			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

			x1 *= 2;

			y1 *= 2;

			x2 *= 2;

			y2 *= 2;

			if(y1 == y2)hashoris[y1] = true;

			if(x1 == x2)hasverts[x1] = true;

			if(x1-y1 == x2-y2)hasdign1[x1-y1+110] = true;

			if(x1+y1 == x2+y2)hasdign2[x1+y1] = true;

		}

		hashoris[0] = true;

		hashoris[m] = true;

		hasverts[0] = true;

		hasverts[n] = true;

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

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

				horis[i][j] = hashoris[j];

				verts[i][j] = hasverts[i];

				dign1[i][j] = hasdign1[i-j+110];

				dign2[i][j] = hasdign2[i+j];

			}

		int ans = 0;

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

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

				if(horis[i][j] && verts[i][j]){

					if(!dign1[i][j]){

						ans += check(i,j,1,0,0,1);

						ans += check(i,j,-1,0,0,-1);

					}

					if(!dign2[i][j]){

						ans += check(i,j,-1,0,0,1);

						ans += check(i,j,1,0,0,-1);

					}

				}

				if(dign1[i][j] && dign2[i][j]){

					if(!horis[i][j]){

						ans += check(i,j,1,1,1,-1);

						ans += check(i,j,-1,1,-1,-1);

					}

					if(!verts[i][j]){

						ans += check(i,j,1,1,-1,1);

						ans += check(i,j,1,-1,-1,-1);

					}

				}

			}

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

	}

    return 0;

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