Codeforces Round 1012 (Div.2) 题解

发表于 分类于 阅读次数： 本文字数： 6.3k
手速场，C 题面烂完了。

A

题意

有一个宝藏在 \(a+0.5\) 米深，两个人轮流挖，第一个人每次挖 \(x\) 米，第二个人每次挖 \(y\) 米，求谁先挖到。

题解

有点像反 Nim 游戏，最先达到 \(a\) 米的会输掉，不妨先把 \(a + 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
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int x, y, a;
    cin >> x >> y >> a;
    a++;
    a -= a / (x + y) * (x + y);
    if (a == 0) {
        cout << "YES\n";
        return;
    }
    if (x >= a) {
        cout << "NO\n";
    } else {
        cout << "YES\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

B

题意

一个 \(n\times m\) 网格，可以从某一 行/列 的开头/结尾推一个球，如果第一个位置没有球，它就停下，否则会推动这一行/列的球继续位移。

给定一个最终状态，判断可不可行。

题解

对于每个球，必须在上下左右至少有一个方向从开头到它都有球，否则不可能被推动，对每一个球判断一下即可。

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

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] = " " + a[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == '1') {
                auto check = [&](int x, int y) {
                    bool ok = true;
                    for (int i = x; i >= 1; i--) {
                        if (a[i][y] != '1') {
                            ok = false;
                            break;
                        }
                    }
                    if (ok) {
                        return true;
                    }
                    ok = true;
                    for (int j = 1; j <= y; j++) {
                        if (a[x][j] != '1') {
                            ok = false;
                            break;
                        }
                    }
                    return ok;
                };
                if (check(i, j) == false) {
                    cout << "NO\n";
                    return;
                }
            }
        }
    }
    cout << "YES\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C

题意

一个走廊，在 \((3x+1, 3y+1)\)，\(( 3𝑥+1,3𝑦+2)\)，($ 3𝑥+2,3𝑦+1 )\(，\)( 3𝑥+2,3𝑦+2)$ 放着桌子，相邻的四张桌子拼成一个大桌。现在给定一些人的意愿，它们会选择一张没有人的大桌或一张有空位的桌子，要求最短距离，距离相同时 \(x\) 小的优先。给出每个人去的 \(x\) 和 \(y\)。

题解

英文题面很难懂，“available” 和 “free” 分别代表没坐满的和空的。可以考虑模拟，使用优先队列维护桌子， map 维护桌子是否被选即可。初始时塞入足够数量的桌子。

大致的桌子数量估算是：最坏情况是 \(n\) 个人全部都是要空桌的，这样桌子图会呈现一个等腰直角三角形的分布，设直角边长为 \(x\)，那么能放下 \(\frac{x-1}{3}\) 张桌子，要求 \(\frac{(\frac{x-1}{3}) ^ 2}{2} \ge n\)，即 \((x-1)^2\ge18n\)，取 \(x^2\le 20n\)即可。

总时间复杂度为 \(O(n\log n)\)（常数取决于取的桌子量）

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

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>>
        free, avai;
    map<array<int, 3>, int> mp;
    for (int i = 1; i * i <= n * 20; i += 3) {
        for (int j = 1; j * j <= n * 20; j += 3) {
            free.push({i + j, i, j});
            avai.push({i + j, i, j});
            avai.push({i + j + 1, i + 1, j});
            avai.push({i + j + 1, i, j + 1});
            avai.push({i + j + 4, i + 1, j + 1});
        }
    }
    for (int i = 1; i <= n; i++) {
        if (a[i] == 0) {
            while (mp[free.top()] == 1) {
                free.pop();
            }
            auto [_, x, y] = free.top();
            cout << x << " " << y << "\n";
            mp[free.top()] = 1;
            free.pop();
        } else {
            while (mp[avai.top()] == 1) {
                avai.pop();
            }
            auto [_, x, y] = avai.top();
            cout << x << " " << y << "\n";
            mp[avai.top()] = 1;
            avai.pop();
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D

题意

构造一个排列 \(p\)，要求：对于 \(1\le i\le n\)，定义 \(c_i = \lceil\frac{p_1+p_2+...+p_i}{i}\rceil\)，使得 \(c_i\) 中至少有 \(\lfloor\frac{n}{3}\rfloor - 1\) 个素数。

题解

一个事实是，素数的密度约为 \(\frac{n}{\log n}\)，在 \(n\) 较大时很难随机构造达到 \(\frac{n}{3}\)。（直接生成 \(1\) 到 \(n\) 你会 WA 8）

由于 \(c_i\) 是一个平均值，因此，我们可以通过加一个比 \(c_i\) 大的数和加一个比 \(c_i\) 小的数来维持这个平均值。因此，可以考虑从一个较大的素数入手，一直构造这个素数。

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

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

// minp[x] 可以找到 x 大于 1 的最小质因子
vector<int> minp, primes;
void sieve(int n) {
    minp.assign(n + 1, 0);
    primes.clear();
    for (int i = 2; i <= n; i++) {
        if (minp[i] == 0) {
            minp[i] = i;
            primes.push_back(i);
        }
        for (auto p : primes) {
            if (i * p > n) {
                break;
            }
            minp[i * p] = p;
            if (p == minp[i]) {
                break;
            }
        }
    }
}

void solve() {
    int n;
    cin >> n;
    sieve(n);
    int p = max(1, n / 3);
    while (minp[p] != p) {
        p++;
    }
    int l = p, r = p;
    vector<int> a = {0, p};
    while (l > 1 && r < n) {
        l--, r++;
        a.push_back(l);
        a.push_back(r);
    }
    for (int i = 1; i < l; i++) {
        a.push_back(i);
    }
    for (int i = r + 1; i <= n; i++) {
        a.push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        cout << a[i] << " \n"[i == n];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

E1

题意

给定两个数组 \(a,b\) 求进行多少次以下操作能把 \(a\) 变成全 0：对于每个 \(i\), \(a_i\) 和 \(b_i\) 同时减去二者的最小值，然后数组 \(a\) 循环左移。题目保证一定有解（\(\sum a_i \le \sum b_i\)）

题解

手玩一下可以发现：对于每个 \(a_i\)，如果不能被 \(b_i\) 抵消，他就会依次尝试与 \(b_{i-1},b_{i-2},..,b_1,b_n,...\) 抵消，这样的操作最多 \(n\) 次。这样的环上操作，破环成链一般是一个更好的方式。这样操作后，我们找到每一个 \(a_i\) 与 让它抵消的 \(b_j\) ，二者的距离就是对于 \(a_i\) 的答案。但是枚举 \(a_i\) 往前扫描的时间复杂度太高了，我们可以换个角度思考：对于位置 \(i\)，\(b_i\) 首先会处理当前的 \(a_i\)，如果还有剩余，就依次去和前面的数抵消，直到自身变为 0 或者没有数可以抵消。

因此，我们可以维护一个栈来放置没有抵消的 \(a\)，每次到达一个新位置时就把 \(a_i\) 入栈，然后用 \(b_i\) 抵消栈中的元素，如果能抵消，二者的距离就是答案，我们对所有的答案取最大值即可。

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

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(2 * n + 1), b(2 * n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i + n] = a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        b[i + n] = b[i];
    }
    int ans = 0;
    vector<int> stk;
    for (int i = 1; i <= 2 * n; i++) {
        if (a[i]) {
            stk.push_back(i);
        }
        while (!stk.empty() && b[i]) {
            int x = stk.back();
            int mn = min(a[x], b[i]);
            a[x] -= mn, b[i] -= mn;
            ans = max(ans, i - x + 1);
            if (a[x] == 0) {
                stk.pop_back();
            }
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}