CCPC 2017 秦皇岛

Posted on | In

No response

C - Crusaders Quest(00:33)

每次可选择将某一位置的字母or某一段连续的相同的字母del掉，若为后者则可以加1分，del后两段字符串将被链接起来。求最大得分。

Solution:

因为三种字母均存在三个，所以只要暴力枚举del的顺序即可。

Code:

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

#define endl "\n"

int seq[4];

int gao(int a[], int tot, int id) {
    if (id == 3) return 0;
    int tmp[10], n = 0, cnt = 0, res = 0;
    for (int i = 0; i < tot; i++) {
        if (a[i] == seq[id]) {
            cnt++;
            if (cnt % 3 == 0) res++;
        }
        else cnt = 0, tmp[n++] = a[i];
    }
    res += gao(tmp, n, id + 1);
    return res;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int T; cin >> T;
    while (T--) {
        string s; cin >> s;
        int a[10];
        for (int i = 0; i < 9; i++) {
            if (s[i] == 'g') a[i] = 1;
            else if (s[i] == 'a') a[i] = 2;
            else a[i] = 3;
        }
        seq[0] = 1, seq[1] = 2, seq[2] = 3;

        int ans = -1;
        do {
            ans = max(ans, gao(a, 9, 0));
        } while (next_permutation(seq, seq + 3));
        cout << ans << endl;
    }
}

E - String of CCPC(1:36)

可以在原串某处插入字母，第$i$次花费$(i - 1)$，所得的value即为最终串内子串CCPC的个数减去总花费。求最大value。

Solution:

一开始想岔了，以为可以插入一个字母使得新串中CCPC个数+2，于是总插入次数应不超过2。实际上并不存在那种状态，所以最大插入次数应为1。于是枚举插入位置判断即可。

Code:

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

#define endl "\n"

char s[200005];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int T; cin >> T;
    while (T--) {
        int n; cin >> n >> s;
        int ans = 0, add = 0;
        for (int i = 2; i < n; i++) {
            if (!add) {
                if (s[i - 2] == 'C' && s[i - 1] == 'C' && s[i] == 'C' && (i + 2 >= n || (s[i + 1] != 'P' || s[i + 2] != 'C'))) {
                    add = 1;
                }
                if (s[i - 2] == 'C' && s[i - 1] == 'P' && s[i] == 'C' && (i - 3 < 0 || s[i - 3] != 'C')) {
                    add = 1;
                }
                if (s[i - 2] == 'C' && s[i - 1] == 'C' && s[i] == 'P' && (i + 1 >= n || s[i + 1] != 'C')) {
                    add = 1;
                }
            }
            if (i - 3 >= 0 && s[i - 3] == 'C' && s[i - 2] == 'C' && s[i - 1] == 'P' && s[i] == 'C') {
                ans++;
            }
        }
        cout << ans + add << endl;
    }
}

L - One-Dimensional Maze(00:13)

给定一个单向迷宫(?)，当处在两端时可以离开迷宫，否则只能按照所处位置的规则向左或向右走，可以花费1单位使某处规则反向。给定初始位置，问离开迷宫的最小花费。

Solution:

温暖的签到题，显然即求$\min(\sum_{i = 2}^{k} [s_i == R], \sum_{i = k}^{n} [s_i == L])$

Code:

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

#define endl "\n"

char s[100005];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int T; cin >> T;
    while (T--) {
        int n, k; cin >> n >> k;
        cin >> s;
        int cnt = 0;
        for (int i = 1; i < k; i++) {
            if (s[i] == 'R') {
                cnt++;
            }
        }
        int ans = cnt; cnt = 0;
        for (int i = k - 1; i < n - 1; i++) {
            if (s[i] == 'L') {
                cnt++;
            }
        }
        cout << min(ans, cnt) << endl;
    }
}

M - Safest Buildings(2:01, -3)

PUBG， 给定初始圈和下一圈的半径，下一圈位置随机但必定在初始圈内，给定$n$座建筑，问被下一圈覆盖的概率最大的建筑是哪些。

Solution:

$Dist <= \sqrt{(R - 2 * r)^{2}}$ 的建筑概率最大，其他建筑距离越近概率越大。

Code:

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

#define endl "\n"

const int maxn = 1e3 + 5;

inline long long sqr(long long x) {
    return x * x;
}

inline long long dis(long long x, long long y) {
    return sqr(x) + sqr(y);
}

int a[maxn];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int T; cin >> T;
    while (T--) {
        int n, R, r; cin >> n >> R >> r;
        for (int i = 1; i <= n; i++) {
            long long x, y; cin >> x >> y;
            a[i] = dis(x, y);
        }
        long long len = sqr(R - 2 * r);
        long long mn = *min_element(a + 1, a + 1 + n);
        if (mn <= len) {
            vector<int> ans;
            for (int i = 1; i <= n; i++) {
                if (a[i] <= len) {
                    ans.push_back(i);
                }
            }
            cout << ans.size() << endl;
            for (int i = 0; i < (int)ans.size(); i++) {
                cout << ans[i] << " \n"[i == ans.size() - 1];
            }
        }
        else {
            vector<int> ans;
            for (int i = 1; i <= n; i++) {
                if (mn == a[i]) {
                    ans.push_back(i);
                }
            }
            cout << ans.size() << endl;
            for (int i = 0; i < (int)ans.size(); i++) {
                cout << ans[i] << " \n"[i == ans.size() - 1];
            }
        }
    }
}