Codeforces Round #328 div2
Codeforces Round #328 div2
若羽
发布于 2019-07-14 13:47:18
发布于 2019-07-14 13:47:18
Problem_A(592A):
题意：
在一个8*8的棋盘上有黑白两种棋子，'W'代表白色，'B'代表黑色。
玩家A执白子，先走。 白子只能向上走，黑子只能向下走。如果有障碍物则不能走， 比如白色的上方有一个黑子，那么白子不能走。
谁先走到边界谁就赢了。 求解谁会赢
思路：
白子只能往上走， 黑子只能往下走。
所以只要找出最上面的白子和最下面的白子， 求距离边界最小值就可以了。
代码：
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <stack>
10 #include <queue>
11 #include <string>
12 #include <vector>
13 #include <fstream>
14 #include <iterator>
15 #include <iostream>
16 #include <algorithm>
17 using namespace std;
18 #define LL long long
19 #define INF 0x3f3f3f3f
20 #define MOD 1000000007
21 #define eps 1e-6
22 #define MAXN 10
23 #define MAXM 100
24 #define dd {cout<<"debug"<<endl;}
25 #define pa {system("pause");}
26 #define p(x) {printf("%d\n", x);}
27 #define pd(x) {printf("%.7lf\n", x);}
28 #define k(x) {printf("Case %d: ", ++x);}
29 #define s(x) {scanf("%d", &x);}
30 #define sd(x) {scanf("%lf", &x);}
31 #define mes(x, d) {memset(x, d, sizeof(x));}
32 #define do(i, x) for(i = 0; i < x; i ++)
33 #define dod(i, x, l) for(i = x; i >= l; i --)
34 #define doe(i, x) for(i = 1; i <= x; i ++)
35 int n = 8;
36 int row[MAXN][MAXN];
37 int read_ch()
38 {
39 char ch;
40 while(ch = getchar())
41 {
42 if(ch == 'B') return 2;
43 if(ch == 'W') return 1;
44 if(ch == '.') return 0;
45 }
46 }
47
48 int main()
49 {
50 mes(row, 0);
51 for(int i = 1; i <= n; i ++)
52 for(int j = 1; j <= n; j ++)
53 row[i][j] = read_ch();
54
55 int min_a = INF, min_b = INF;
56
57 for(int j = 1; j <= n; j ++)
58 {
59 for(int i = 1; i <= n; i ++)
60 {
61 if(row[i][j] == 2) break;
62 if(row[i][j] == 1)
63 {
64 min_a = min(min_a, i - 1);
65 break;
66 }
67 }
68 for(int i = n; i >= 1; i --)
69 {
70 if(row[i][j] == 1) break;
71 if(row[i][j] == 2)
72 {
73 min_b = min(min_b, n - i);
74 break;
75 }
76 }
77 }
78 printf("%c\n", min_a <= min_b ? 'A' : 'B');
79 return 0;
80 }Problem_B(592B):
题意：
给n个点， 依旧如下的规则划线：
1：先按顺时针将所有的点标号 1~n
2：从第一个点开始， 对其他n-1个点做一条射线
3：如果射线延长的过程中遇到其他线段， 则停止延长。
求这个n-1多边形内的区域被分成了多少块。
思路:
手动模拟一下n = 4和n = 6的情况，就能发现一个规律：
第一个点将区域划分成了 n - 2块区域。
第二个点又增加了 n - 3个区域。
第三个点增加了 n - 4 个区域。
.....
第n - 1个点增加了n - (n - 1) 块区域。
第n个点增加了n - 2块区域。
然后就能得到一个式子:
Sn = n - 2 + n - 3 + n - 4 + ... + n - (n - 1) + n - 2
= n * n - (2 + 3 + 4 + ... + (n - 1)) - 2
= n * n - (1 + 2 + 3 + ... + (n - 1)) - 1
= n * n - (1 + (n - 1)) * (n - 1) / 2 - 1
So 答案就出来了。
代码：
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <stack>
10 #include <queue>
11 #include <string>
12 #include <vector>
13 #include <fstream>
14 #include <iterator>
15 #include <iostream>
16 #include <algorithm>
17 using namespace std;
18 #define LL long long
19 #define INF 0x3f3f3f3f
20 #define MOD 1000000007
21 #define eps 1e-6
22 #define MAXN 1000000
23 #define MAXM 100
24 #define dd {cout<<"debug"<<endl;}
25 #define pa {system("pause");}
26 #define p(x) {printf("%d\n", x);}
27 #define pd(x) {printf("%.7lf\n", x);}
28 #define k(x) {printf("Case %d: ", ++x);}
29 #define s(x) {scanf("%d", &x);}
30 #define sd(x) {scanf("%lf", &x);}
31 #define mes(x, d) {memset(x, d, sizeof(x));}
32 #define do(i, x) for(i = 0; i < x; i ++)
33 #define dod(i, x, l) for(i = x; i >= l; i --)
34 #define doe(i, x) for(i = 1; i <= x; i ++)
35 LL n;
36 LL get_ans(LL x)
37 {
38 return (n - 2) + 2 * (n - 3) + (n - 3) * (n - 4);
39 }
40
41 int main()
42 {
43 scanf("%I64d", &n);
44 printf("%I64d\n", get_ans(n));
45 return 0;
46 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2016-05-26 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读