Codeforces Round 483 (Div. 2)

发表于 | 更新于: | 分类于

概况：场外ABCD accept

题目链接

479

A - Game

大意：两个人先后从一堆数中取数，每次一个，到只剩一个停止，第一个人想最后剩下的数最小，第二个人想最后剩下的数最大。

题解：排序取中间值即可，因为先手取大数所以-1再除二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int a[1005];
int main(int argc, char const *argv[])
{
    int n;
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; ++i) {
            scanf("%d", &a[i]);
        }
        sort(a, a + n);
        printf("%d\n", a[(n - 1) / 2]);
    }
    return 0;
}

B - Minesweeper

大意：判断一个扫雷的地图是否正确

题解：因为’.’代表无地雷且旁边八格都没有，所以相当于数字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
#include <bits/stdc++.h>
using namespace std;

char mp[106][106];
int main(int argc, char const *argv[])
{
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        for (int i = 0; i < n; ++i) {
            scanf("%s", mp[i]);
        }
        int temp, gg, flag = 1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (mp[i][j] <= '9' && mp[i][j] >= '1') {
                    temp = mp[i][j] - '0';
                    gg = 0;
                    if (i > 0) {
                        if (mp[i - 1][j] == '*') ++gg;
                        if (j > 0) {
                            if (mp[i - 1][j - 1] == '*') ++gg;
                        }
                        if (j < m - 1) {
                            if (mp[i - 1][j + 1] == '*') ++gg;
                        }
                    }
                    if (i < n - 1) {
                        if (mp[i + 1][j] == '*') ++gg;
                        if (j > 0) {
                            if (mp[i + 1][j - 1] == '*') ++gg;
                        }
                        if (j < m - 1) {
                            if (mp[i + 1][j + 1] == '*') ++gg;
                        }
                    }
                    if (j > 0) {
                        if (mp[i][j - 1] == '*') ++gg;
                    }
                    if (j < m - 1) {
                        if (mp[i][j + 1] == '*') ++gg;
                    }
                    if (gg != temp) {
                        flag = 0;
                        break;
                    }
                } else if (mp[i][j] == '.') {
                    if (i > 0) {
                        if (mp[i - 1][j] == '*') flag = 0;
                        if (j > 0) {
                            if (mp[i - 1][j - 1] == '*') flag = 0;
                        }
                        if (j < m - 1) {
                            if (mp[i - 1][j + 1] == '*') flag = 0;
                        }
                    }
                    if (i < n - 1) {
                        if (mp[i + 1][j] == '*') flag = 0;
                        if (j > 0) {
                            if (mp[i + 1][j - 1] == '*') flag = 0;
                        }
                        if (j < m - 1) {
                            if (mp[i + 1][j + 1] == '*') flag = 0;
                        }
                    }
                    if (j > 0) {
                        if (mp[i][j - 1] == '*') flag = 0;
                    }
                    if (j < m - 1) {
                        if (mp[i][j + 1] == '*') flag = 0;
                    }
                    if (flag == 0) break;
                }
            }
            if (flag == 0) break;
        }
        printf("%s\n", flag ? "YES" : "NO");
    }
    return 0;
}

C - Finite or not?

大意：数论题有点东西，就是一个十进制的小数在某种进制内是不是有限小数，其中十进制小数是以p/q（都为十进制）给出的

题解：大概就推一下发现p/q为最简式时p取任意整数都对结果没有影响，然后其实比如b进制中p/q如果是有限小数，一定有p*(b^k)/q为整数，即q是b素因子的任意组合（也可以是多个素因子重复），所以素数打表和反复取gcd都可以解决

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
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main(int argc, char const *argv[])
{
    int t;
    scanf("%d", &t);
    ll p, q, b;
    while (t--) {
        scanf("%lld%lld%lld", &p, &q, &b);
        q /= __gcd(p, q);
        ll temp = __gcd(q, b);
      	//好像做了什么多余的事
        if (q == 1) printf("Finite\n");
        else if (temp == 1) printf("Infinite\n");
        else {
            while (q > 1 && temp > 1) {
                temp = __gcd(q, temp);
                q /= temp;
            }
            printf("%s\n", q == 1 ? "Finite" : "Infinite");
        }
    }
    return 0;
}

D - Divide by three, multiply by two

大意：抄的

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
#include <bits/stdc++.h>

using namespace std;

int dp[5005][5005];

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        memset(dp, 0, sizeof dp);
        for (int i = 1; i <= n; i++) scanf("%d", &dp[i][i]);
        for (int i = 1; i < n; i++) {
            for (int j = 1; j + i <= n; j++) {
                dp[j][j + i] = dp[j][j + i - 1] ^ dp[j + 1][j + i];
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j + i <= n; j++) {
                dp[j][j + i] = max(max(dp[j + 1][j + i], dp[j][j + i]), dp[j][j + i - 1]);
            }
        }
        int t, l, r;
        scanf("%d", &t);
        while (t--) {
            scanf("%d%d", &l, &r);
            printf("%d\n", dp[l][r]);
        }
    }
    return 0;
}

E - Elevator

大意：不会啊有机会补一补。

1
2


嘻嘻嘻我想要1900