ACdream原创群赛(12)のBUAA选拔赛

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

链接： http://acdream.info/onecontest/1021#overview

水了一发这次的比赛，简单记录下题解吧!

A： 直接数学公式搞。 n个非负整数的和为m的解个数为C(n+m-1,n-1) 如果其中一个位置选择了i, 那么其余的就是C(n-1 + m-i - 1, n-2), 这就是这个位置i出现次数，  然后位置有n个，再乘以n   根据欧拉定理，指数对 1e9+6取模。      

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

Author        :kuangbin

Created Time  :2014/5/30 20:33:18

File Name     :E:\2014ACM\比赛\ACdream_20140530\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;

const int MOD = 1e9+7;

int C[2020][2020];

void init()

{

	C[0][0] = 1;

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

	{

		C[i][0] = C[i][i] = 1;

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

		{

			C[i][j] = C[i-1][j] + C[i-1][j-1];

			if(C[i][j] >= MOD-1)

				C[i][j] -= MOD-1;

		}

	}

}

long long pow_m(long long a,long long n)

{

	long long ret = 1;

	long long tmp = a%MOD;

	while(n)

	{

		if(n&1)

		{

			ret = ret*tmp%MOD;

		}

		tmp = tmp*tmp%MOD;

		n >>= 1;

	}

	return ret;

}

int main()

{

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

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

    int T;

	int n,m;

	scanf("%d",&T);

	init();

	while(T--)

	{

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

		if(n == 1)

		{

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

			continue;

		}

		long long ans = 1;

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

			{

				ans = pow_m(j,(long long)C[n-1+m-j-1][n-2]n%(MOD-1));

				ans %= MOD;

			}

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

	}

    return 0;

}
B: 就是相当于求一个顺时针的多边行包围的数的和。 我是直接看的横线，从左到右减一个矩形，从右到左加一个矩形。 累加起来就是答案了。   [![无标题](http://www.kuangbin.top/wp-content/uploads/2014/05/无标题-300x118.png)](http://www.kuangbin.top/wp-content/uploads/2014/05/无标题.png)   如上图，可以是 3的和  -  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
/* ***************

Author        :kuangbin

Created Time  :2014/5/30 21:27:59

File Name     :E:\2014ACM\比赛\ACdream_20140530\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;

int a[1010][1010];

long long sum[1010][1010];

pair<int,int>p[1010];

int main()

{

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

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

    int T;

	int n,m;

	scanf("%d",&T);

	while(T--)

	{

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

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

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

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

		memset(sum,0,sizeof(sum));

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

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

			{

				sum[i][j] = sum[i][j-1] + sum[i-1][j] + a[i][j] - sum[i-1][j-1];

			}

		int q;

		scanf("%d",&q);

		while(q--)

		{

			int k;

			scanf("%d",&k);

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

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

			long long ans = 0;

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

			{

				int x1,y1,x2,y2;

				x1 = p[i].first;

				y1 = p[i].second;

				x2 = p[(i+1)%k].first;

				y2 = p[(i+1)%k].second;

				swap(x1,y1);

				swap(x2,y2);

				if(x1 == x2)

				{

					ans += sum[x1][y1] - sum[x1][y2];

				}

			}

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

		}

	}

    return 0;

}

C： 一个有向图上的DP， 按照拓扑排序的顺序进行DP， DP出，到终点的最快路径，以及删掉一个的情况下最快到达。 对于点u 如果求u到终点的最快时间，直接转移就是了。 求u到终点可以删掉一条边的话， 那么有两种情况，一种是删掉和u相连的边。另外一种是删掉u下面的边。 对于每种情况，要走最快的路， 然后这些里面取最大值。 

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

Author        :kuangbin

Created Time  :2014/5/30 21:50:05

File Name     :E:\2014ACM\比赛\ACdream_20140530\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;

const int MAXN = 10010;

const int MAXM = 100010;

const int INF = 0x3f3f3f3f;

struct Edge

{

	int to,w;

	int next;

}edge[MAXM];

int head[MAXN],tot;

void init()

{

	tot = 0;

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

}

void addedge(int u,int v,int w)

{

	edge[tot].to = v;

	edge[tot].w = w;

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

	head[u] = tot++;

}

int dp1[MAXN];

int dp2[MAXN];

int n;

int a[MAXM];

void dfs(int u)

{

	if(u == n-1)

	{

		dp1[u] = dp2[u] = 0;

		return;

	}

	dp1[u] = dp2[u] = INF;

	int sz = 0;

	int smin = -1;

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

	{

		int v = edge[i].to;

		dp1[u] = min(dp1[u],dp1[v] + edge[i].w);

		if(smin == -1)smin = dp2[v] + edge[i].w;

		else

			smin = min(smin,dp2[v] + edge[i].w);

		a[sz++] = dp1[v] + edge[i].w;

	}

	a[sz] = INF;

	for(int i = sz-2;i >= 0;i--)

		a[i] = min(a[i],a[i+1]);

	int tmp = INF;

	dp2[u] = -1;

	if(smin !=-1)dp2[u] = smin;

	int tt = 0;

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

	{

		int v = edge[i].to;

		tt++;

		if(dp2[u] == -1)

			dp2[u] = min(tmp,a[tt]);

		else dp2[u] = max(dp2[u],min(tmp,a[tt]));

		tmp = min(tmp,dp1[v] + edge[i].w);

	}

	if(dp2[u] == -1)dp2[u] = INF;

}

vector<int>vec[MAXN];

int in[MAXN];

int b[MAXN];

int cnt;

void get()

{

	queue<int>q;

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

		if(in[i] == 0)

		{

			q.push(i);

		}

	while(!q.empty())

	{

		int u = q.front();

		q.pop();

		b[cnt++] = u;

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

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

		{

			int v = vec[u][i];

			in[v]--;

			if(in[v] == 0)

				q.push(v);

		}

	}

}

int main()

{

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

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

    int T;

	int m;

	scanf("%d",&T);

	while(T--)

	{

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

		init();

		int u,v,w;

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

		{

			in[i] = 0;

			vec[i].clear();

		}

		while(m--)

		{

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

			addedge(u,v,w);

			vec[v].push_back(u);

			in[u]++;

		}

		cnt = 0;

		get();

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

		{

			dfs(b[i]);

		}

		if(dp2[0] >= INF)printf("-1\n");

		else printf("%d\n",dp2[0]);

	}

    return 0;

}

D： 把K进行质因子分解下，就知道P(n,m) 中含有多少个该质因子了。 然后取最小值 比如 k = p1^k1 * p2^k2 …..pi^ki 如何求出P(n,m) 有多少个pi ,假如有x个，那么所有的 x/ki 求最小值就是答案了 

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

Author        :kuangbin

Created Time  :2014/5/30 20:03:09

File Name     :E:\2014ACM\比赛\ACdream_20140530\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=10000000;

int prime[MAXN+1];

void getPrime()

{

    memset(prime,0,sizeof(prime));

    for(int i=2;i<=MAXN;i++)

    {

        if(!prime[i])prime[++prime[0]]=i;

        for(int j=1;j<=prime[0]&&prime[j]<=MAXN/i;j++)

        {

            prime[prime[j]*i]=1;

            if(i%prime[j]==0) break;

        }

    }

}

long long factor[100][2];

int fatCnt;

int getFactors(long long x)

{

    fatCnt=0;

    long long tmp=x;

    for(int i=1;prime[i]<=tmp/prime[i];i++)

    {

        factor[fatCnt][1]=0;

        if(tmp%prime[i]==0)

        {

            factor[fatCnt][0]=prime[i];

            while(tmp%prime[i]==0)

            {

                factor[fatCnt][1]++;

                tmp/=prime[i];

            }

            fatCnt++;

        }

    }

    if(tmp!=1)

    {

        factor[fatCnt][0]=tmp;

        factor[fatCnt++][1]=1;

    }

    return fatCnt;

}

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

long long f[50];

int main()

{

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

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

	getPrime();

    long long n,m,k;

	int T;

	scanf("%d",&T);

	while(T--)

	{

		cin>>n>>m>>k;

		getFactors(k);

		long long ans = 1000000000000000000LL;

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

		{

			//cout<<factor[i][0]<<" "<<factor[i][1]<<endl;

			long long tmp = factor[i][0];

			memset(f,0,sizeof(f));

			long long sum = 0;

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

			{

				if(tmp > n)break;

				sum  += (n/tmp - (n-m)/tmp);

				tmp *= factor[i][0];

			}

			ans = min(ans,sum/factor[i][1]);

		}

		cout<<ans<<endl;

	}

    return 0;

}

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

Author        :kuangbin

Created Time  :2014/5/30 18:45:57

File Name     :E:\2014ACM\比赛\ACdream_20140530\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;

int main()

{

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

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

    int n;

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

	{

		int ans = 0;

		int a;

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

		{

			scanf("%d",&a);

			ans ^= a;

		}

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

	}

    return 0;

}

F： >= 6161 直接构造， < 6161 处理出含有61的数，然后进行背包。 

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

Author        :kuangbin

Created Time  :2014/5/30 20:52:11

File Name     :E:\2014ACM\比赛\ACdream_20140530\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;

bool check(int n)

{

	int a[20];

	int cnt = 0;

	do

	{

		a[cnt++] = n % 10;

		n /= 10;

	}

	while(n);

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

		if(a[i] == 1 && a[i+1] == 6)

			return true;

	return false;

}

int f[10000];

int pre[10000];

int a[10000];

const int INF = 0x3f3f3f3f;

void ouput(int n)

{

	//printf("%d  **\n",n);

	if(pre[n] != 0)ouput(pre[n]);

	printf(" %d",n - pre[n]);

}

int main()

{

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

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

    int T;

	int n;

	scanf("%d",&T);

	int num = 0;

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

		if(check(i))

			a[num++] = i;

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

		f[i] = INF;

	f[0] = 0;

	pre[0] = -1;

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

	{

		for(int j = 0;j < num && a[j] <= i;j++)

		{

			if(f[i] > f[i-a[j]]+1)

			{

				f[i] = f[i-a[j]] + 1;

				pre[i] = i-a[j];

			}

		}

	}

	while(T--)

	{

		scanf("%d",&n);

		if(check(n))

		{

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

			continue;

		}

		if(n >= 6161)

		{

			int ans1 = 0,ans2 = 0;

			ans1 = 61;

			ans2 = 6100;

			n -= 6161;

			ans2 += n%100;

			ans1 += (n/100)*100;

			printf("2 %d %d\n",ans1,ans2);

			continue;

		}

		if(f[n] == INF)

		{

			printf("0\n");

			continue;

		}

		printf("%d",f[n]);

		ouput(n);

		printf("\n");

	}

    return 0;

}
G： 计算几何。 直接枚举两个端点作为直线的两个点，判断直线和线段交。 写搓了，WA好几发，TAT

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

Author        :kuangbin

Created Time  :2014/5/30 19:17:18

File Name     :E:\2014ACM\比赛\ACdream_20140530\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;

const double inf = 1e20;

const double pi = acos(-1.0);

const int maxp = 1010;

//Compares a double to zero

int sgn(int x)

{

	if(x == 0)return 0;

	if(x < 0)return -1;

	else return 1;

}

struct Point

{

	int x,y;

	Point(){}

	Point(int _x,int _y)

	{

		x = _x;

		y = _y;

	}

	void input()

	{

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

	}

	bool operator == (Point b)const

	{

		return sgn(x-b.x) == 0 && sgn(y-b.y) == 0;

	}

	bool operator < (Point b)const

	{

		return sgn(x-b.x)== 0?sgn(y-b.y)<0:x<b.x;

	}

	Point operator -(const Point &b)const

	{

		return Point(x-b.x,y-b.y);

	}

	//叉积

	int operator ^(const Point &b)const

	{

		return x*b.y - y*b.x;

	}

	//点积

	int operator *(const Point &b)const

	{

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

	}

};

struct Line

{

	Point s,e;

	Line(){}

	Line(Point _s,Point _e)

	{

		s = _s;

		e = _e;

	}

	bool operator ==(Line v)

	{

		return (s == v.s)&&(e == v.e);

	}

	void input()

	{

		s.input();

		e.input();

	}

	//两线段相交判断

	//2 规范相交

	//1 非规范相交

	//0 不相交

	int segcrossseg(Line v)

	{

		int d1 = sgn((e-s)^(v.s-s));

		int d2 = sgn((e-s)^(v.e-s));

		int d3 = sgn((v.e-v.s)^(s-v.s));

		int d4 = sgn((v.e-v.s)^(e-v.s));

		if( (d1^d2)==-2 && (d3^d4)==-2 )return 2;

		return (d1==0 && sgn((v.s-s)*(v.s-e))<=0) ||

			(d2==0 && sgn((v.e-s)*(v.e-e))<=0) ||

			(d3==0 && sgn((s-v.s)*(s-v.e))<=0) ||

			(d4==0 && sgn((e-v.s)*(e-v.e))<=0);

	}

	//直线和线段相交判断

	//-*this line   -v seg

	//2 规范相交

	//1 非规范相交

	//0 不相交

	int linecrossseg(Line v)

	{

		int d1 = sgn((e-s)^(v.s-s));

		int d2 = sgn((e-s)^(v.e-s));

		if((d1^d2)==-2) return 2;

		return (d1==0||d2==0);

	}

};

Line line[1010];

Point p[2010];

int main()

{

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

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

    int T;

	int n;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d",&n);

		int num = 0;

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

		{

			line[i].input();

			p[num++] = line[i].s;

			p[num++] = line[i].e;

		}

		int ans = 0;

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

			for(int y = x+1;y < num;y++)

		{

			int cnt = 0;

			if(p[x] == p[y])continue;

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

					if(Line(p[x],p[y]).linecrossseg(line[j]) != 0)

						cnt++;

			ans = max(ans,cnt);

		}

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

	}

    return 0;

}

H： 直接构造的。 1 n 2 n-1 3 n-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
/* ***************

Author        :kuangbin

Created Time  :2014/5/30 18:50:58

File Name     :E:\2014ACM\比赛\ACdream_20140530\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 main()

{

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

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

    int T;

	int n;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d",&n);

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

		{

			if(i%2 == 0)printf("%d",1+i/2);

			else printf("%d",n-i/2);

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

			else printf("\n");

		}

	}

    return 0;

}
I： 二分 + 拓扑排序判断 二分枚举，把 > mid的边加入，看能不能拓扑排序。  

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

Author        :kuangbin

Created Time  :2014/5/30 18:56:04

File Name     :E:\2014ACM\比赛\ACdream_20140530\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;

const int MAXN = 10010;

vector<int>vec[MAXN];

int in[MAXN];

int n;

bool check()

{

	int cnt = 0;

	queue<int>q;

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

		if(in[i] == 0)

		{

			q.push(i);

			cnt++;

		}

	while(!q.empty())

	{

		int u = q.front();

		q.pop();

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

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

		{

			int v = vec[u][i];

			in[v]--;

			if(in[v] == 0)

			{

				q.push(v);

				cnt++;

			}

		}

	}

	return cnt == n;

}

int a[MAXN],b[MAXN],c[MAXN];

int main()

{

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

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

    int T;

	int m;

	scanf("%d",&T);

	while(T--)

	{

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

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

		{

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

		}

		int l = 0, r = 1000000010;

		int ans = 0;

		while(l <= r)

		{

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

			{

				in[i] = 0;

				vec[i].clear();

			}

			int mid = (l+r)/2;

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

				if(c[i] > mid)

				{

					vec[b[i]].push_back(a[i]);

					in[a[i]]++;

				}

			if(check())

			{

				ans = mid;

				r = mid-1;

			}

			else l = mid+1;

		}

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

	}

    return 0;

}
J： 满二叉树，对称性知道先手必输。

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

Author        :kuangbin

Created Time  :2014/5/30 18:36:54

File Name     :E:\2014ACM\比赛\ACdream_20140530\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;

int main()

{

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

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

    int T;

	long long n;

	scanf("%d",&T);

	while(T--)

	{

		cin>>n;

		printf("Dudu\n");

	}

    return 0;

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

Author        :kuangbin

Created Time  :2014/5/30 18:32:27

File Name     :E:\2014ACM\比赛\ACdream_20140530\K.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 main()

{

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

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

    int T;

	int A,B,R1,R2;

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d%d%d%d",&A,&B,&R1,&R2);

		int R = max(R1,R2);

		if(A < 2*R || B < 2*R)

		{

			printf("NO\n");

			continue;

		}

		if(A >= 2*R1+2*R2 || B >= 2*R1+2*R2)

		{

			printf("YES\n");

			continue;

		}

		int tmp1 = A - R1 - R2;

		int tmp2 = B - R1 - R2;

		if(tmp1*tmp1 + tmp2*tmp2 >= (R1+R2)*(R1+R2))

			printf("YES\n");

		else printf("NO\n");

	}

    return 0;

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