Atcoder Beginner Contest 391 + 392 题解

发表于 更新于 分类于 阅读次数： 本文字数： 9.2k
以后大概只写DEF题解了，补题的话两次发一起吧。

AtCoder Beginner Contest 391 题解

D

题意

给定一些方块的行和高，它们每秒下降一格，类似俄罗斯方块一样，如果一整排填满了方块就会全部消掉。现在给定 \(Q\) 次询问，每次给出一个方块的编号和时间，回答此时 + 0.5s 后该方块是否存在。

题解

模拟题。

注意到行数是非常多的，而列数在 2e5 的范围内，这提示我们从列下手。我们把每一列按照高度从低到高的顺序排序，同时可以发现如果一个方块要被消掉，它一定是在最底层的，所以被消掉的时间就是高度。由于需要最后一行填满才能消掉，因此消掉的行数是确定的，也就是每一列的方块数的最小值，我们枚举会在同一行被消掉的方块，它们被消掉的时间就是这一行所有方块到达最底层的最长时间。

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

void solve() {
    int N, W;
    cin >> N >> W;
    vector<vector<pair<int, int>>> col(W + 1);
    vector<int> vis(N + 1);
    vector<int> h(N + 1);
    vector<int> final(N + 1);
    for (int i = 1; i <= N; i++) {
        int x, y;
        cin >> x >> y;
        col[x].emplace_back(y, i);
        h[i] = y;
    }
    int sz = 1e18;
    for (int i = 1; i <= W; i++) {
        sort(col[i].begin(), col[i].end());
        sz = min(sz, (int)col[i].size());
        for (int j = 0; j < col[i].size(); j++) {
            final[col[i][j].second] = h[col[i][j].second];
        }
    }
    for (int i = 1; i <= sz; i++) {
        int mx = 0;
        for (int j = 1; j <= W; j++) {
            mx = max(mx, final[col[j][i - 1].second]);
        }
        for (int j = 1; j <= W; j++) {
            vis[col[j][i - 1].second] = mx;
        }
    }
    int Q;
    cin >> Q;
    while (Q--) {
        int T, A;
        cin >> T >> A;
        if (!vis[A] || T < vis[A]) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
}

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

E

题意

给定一个长度为 \(3^N\) 的 01 串，然后把这个串从头到尾每连续三个字符一组，每一组取出现次数最多的字符拼接起来组成新串，一直重复下去最后只会剩一个字符。现在我们想让最后剩的字符相反，求最少需要改变多少个原串中的字符。

\(N \le 13\)

题解

观察到这样小的 \(N\) 的取值范围，不妨考虑暴力搜索。因为每三个字符一组，所以不断重复该过程时，也就形成了一个三叉树（倒金字塔形，最上层是原串），改变每个节点时，我们搜索时已经知道需要变成什么字符，考虑一组中以下四种情形：

  1. 当前字符为 3 个 0，我们需要变为 1 的话就要改变两个字符，所以取改变次数最少的两个节点。
  2. 当前字符为 3 个 1，同理。
  3. 当前字符为 2 个 1，1个 0，我们改变需要改变次数最少的 1 节点即可。
  4. 当前字符为 2 个 0，1个 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
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
#include <bits/stdc++.h>
using namespace std;
#define int long long

int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) {
            res = res * a;
        }
        a = a * a;
        b /= 2;
    }
    return res;
}

void solve() {
    int N;
    string s;
    cin >> N >> s;
    int l = 1, r = qpow(3, N);
    vector<int> a(r + 1);
    for (int i = 1; i <= r; i++) {
        a[i] = s[i - 1] - '0';
    }
    auto dfs = [&](auto self, int l, int r) -> pair<int, int> {
        if (l == r) {
            return {a[l], 1};
        }
        auto x = self(self, l, l + (r - l + 1) / 3 - 1),
             y = self(self, l + (r - l + 1) / 3, l + (r - l + 1) / 3 * 2 - 1),
             z = self(self, l + (r - l + 1) / 3 * 2, r);
        int cnt[2] = {0, 0};
        cnt[x.first]++, cnt[y.first]++, cnt[z.first]++;
        if (cnt[0] == 3) {
            int b[] = {x.second, y.second, z.second};
            sort(b, b + 3);
            return {0, b[0] + b[1]};
        } else if (cnt[1] == 3) {
            int b[] = {x.second, y.second, z.second};
            sort(b, b + 3);
            return {1, b[0] + b[1]};
        } else if (cnt[0] == 2) {
            int ans = 1e18;
            if (x.first == 0) {
                ans = min(ans, x.second);
            }
            if (y.first == 0) {
                ans = min(ans, y.second);
            }
            if (z.first == 0) {
                ans = min(ans, z.second);
            }
            return {0, ans};
        } else {
            int ans = 1e18;
            if (x.first == 1) {
                ans = min(ans, x.second);
            }
            if (y.first == 1) {
                ans = min(ans, y.second);
            }
            if (z.first == 1) {
                ans = min(ans, z.second);
            }
            return {1, ans};
        }
    };
    cout << dfs(dfs, l, r).second << "\n";
}

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

F

题意

给定三个数组 \(A,B,C\) ，和 \(K\) ，求第 \(K\) 大的 \(A_iB_j + A_iC_k + B_jC_k\)。

\(K\le \min(N^3, 5\times 10^5)\)

题解

首先由于求第 \(K\) 大，结合 \(K\) 的范围我们可以发现在 \(N\) 最大能取 \(2\times 10^5\) 的情况时，\(K\) 的值相对偏小，这提示我们可以排除很大一部分过小的数。

我们把 \(A,B,C\) 按照从大到小的顺序排序，那么对于 \(i\times j\times k > K\) 的情况时，一定不会是我们要的答案，因为此时的组合数显然已经超过了 \(K\) 种，那么我们就在这样的范围下枚举找答案即可。

时间复杂度：只枚举 \(i,j\) 的话是调和级数，复杂度\(O(n\log n)\)，加上枚举 \(k\) 就是二维调和级数了，时间复杂度\(O(n\log^2n)\)

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

void solve() {
    int N, K;
    cin >> N >> K;
    vector<int> A(N + 1), B(N + 1), C(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }
    sort(A.begin() + 1, A.end(), greater());
    for (int i = 1; i <= N; i++) {
        cin >> B[i];
    }
    sort(B.begin() + 1, B.end(), greater());
    for (int i = 1; i <= N; i++) {
        cin >> C[i];
    }
    sort(C.begin() + 1, C.end(), greater());
    vector<int> v;
    v.reserve(5e5);
    for (int i = 1; i <= N && i <= K; i++) {
        for (int j = 1; j <= N && i * j <= K; j++) {
            for (int k = 1; i * j * k <= K && k <= N; k++) {
                int val = A[i] * B[j] + A[i] * C[k] + B[j] * C[k];
                v.push_back(val);
            }
        }
    }
    nth_element(v.begin(), v.begin() + K - 1, v.end(), greater());
    cout << v[K - 1] << "\n";
}

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

Japan Registry Services (JPRS) Programming Contest 2025#1 (AtCoder Beginner Contest 392) 题解

D

题意

有 \(N\) 个骰子，每个骰子有 \(K_i\) 个面，面上写着数字 \(A_{i,j}\)，投掷一次出现每一个面的概率都是 \(\frac{1}{K_ i}\)​ ，现在求任意投掷两个骰子，出现正面相同的概率最大是多少。

\(N\le 100,\sum K_i\le 10^5,A_{i,j}\le10^5\)

题解

由概率知识可知对于骰子 \(i, j\) 出现相同正面的概率为对于每个出现在 \(i, j\) 的相同数的出现次数相乘之和除以它们的面数。如果直接枚举的话，考虑所有面都是 1 的情况，复杂度会被卡为 \(O(N^2K^2)\)，需要结合 \(\sum K_i\le 10^5\) 和值域范围来优化。

我们不通过枚举骰子，而是枚举值域。通过存储每个值对应的骰子编号以及出现数量，我们可以做到对于每个值最多出现 \(N\) 个骰子，时间复杂度似乎是 \(O(AN^2)\) 的，但是由于 \(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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n;
    cin >> n;
    vector<map<int, int>> a(n + 1);
    vector<int> sz(n + 1);
    map<int, map<int, int>> mp;
    vector<vector<int>> ans(n + 1, vector<int>(n + 1));
    for (int i = 1; i <= n; i++) {
        cin >> sz[i];
        for (int j = 1; j <= sz[i]; j++) {
            int x;
            cin >> x;
            mp[x][i]++;
        }
    }
    for (int i = 1; i <= 1e5; i++) {
        for (auto [x, y] : mp[i]) {
            for (auto [u, v] : mp[i]) {
                if (u >= x) {
                    break;
                }
                ans[x][u] += y * v;
            }
        }
    }
    double res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            res = max(res, 1.0 * ans[j][i] / (sz[i] * sz[j]));
        }
    }
    cout << setprecision(15) << res << "\n";
}

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

E

题意

\(N\) 台服务器， \(M\) 条线（双向连接），现在想让所有服务器连通，求最少需要改变多少条线的其中一端并给出改变方式。

题解

连通 + 图论很自然地往并查集取想了。在建图的过程中我们可以记录下那些多余的边（连向自身的和连向已经连通的部分的），那么改变的数目就是连通块的数目减去 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
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
#include <bits/stdc++.h>
using namespace std;
#define int long long

struct DSU {
    int n;
    vector<int> p, sz;
    DSU(int n_) {
        n = n_;
        init(n);
    }
    void init(int n) {
        p.resize(n + 1);
        sz.resize(n + 1, 1);
        iota(p.begin() + 1, p.end(), 1);
    }
    int find(int x) {
        while (x != p[x]) {
            x = p[x] = p[p[x]];
        }
        return x;
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (sz[x] > sz[y]) {
            swap(x, y);
        }
        sz[y] += sz[x];
        p[x] = y;
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return sz[find(x)]; }
};

void solve() {
    int n, m;
    cin >> n >> m;
    DSU dsu(n);
    vector<int> out(m + 1), st(m + 1);
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        if (dsu.same(x, y)) {
            out[i] = true;
            st[i] = x;
        } else {
            dsu.merge(x, y);
        }
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (i == dsu.p[i]) {
            cnt++;
        }
    }
    cout << cnt - 1 << "\n";
    for (int i = 1, k = 1; i <= m; i++) {
        if (!out[i]) {
            continue;
        }
        while (k <= n && dsu.find(k) == dsu.find(st[i])) {
            k++;
        }
        if (k > n) {
            break;
        }
        dsu.merge(st[i], dsu.find(k));
        cout << i << " " << st[i] << " " << k << "\n";
    }
}

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

F

题意

给出一个数组 \(P\)，现在把数字 1～\(N\) 按照顺序依次插入一个空序列，插入时每个数字 \(i\) 要放到第 \(P_i\) 的位置上。

题解

如果从后往前看的话，对于每个数 \(i\) 就是要找到第 \(P_i\) 个空着的位置放入即可，所以我们需要的操作就是找到第 \(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
#include <bits/stdc++.h>
using namespace std;
#define int long long

struct BIT {
    int n;
    vector<int> w;
    BIT(int n) {
        this->n = n;
        w.resize(n + 1);
    }
    void add(int x, int k) {
        for (; x <= n; x += x & -x) {
            w[x] += k;
        }
    }
    void add(int x, int y, int k) { add(x, k), add(y + 1, -k); }
    int ask(int x) {
        int ans = 0;
        for (; x; x -= x & -x) {
            ans += w[x];
        }
        return ans;
    }
    int ask(int x, int y) { return ask(y) - ask(x - 1); }
    int kth(int k) {
        // 查找第 k 小的值
        int ans = 0;
        for (int i = log2(n); i >= 0; i--) {
            int val = ans + (1 << i);
            if (val < n && w[val] < k) {
                k -= w[val];
                ans = val;
            }
        }
        return ans + 1;
    }
};

void solve() {
    int n;
    cin >> n;
    vector<int> p(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }
    BIT bit(n);
    for (int i = 1; i <= n; i++) {
        bit.add(i, 1);
    }
    vector<int> ans(n + 1);
    for (int i = n; i >= 1; i--) {
        int k = bit.kth(p[i]);
        ans[k] = i;
        bit.add(k, -1);
    }
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " \n"[i == n];
    }
}

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