Codeforces Round 1009 Div.3 题解

发表于 更新于 分类于 阅读次数： 本文字数： 5.2k
怎么感觉Div3越来越难了啊也可能是我越来越菜了？

C

题意

输入一个 \(x\) ，找到一个 \(y < x\) 满足 \(x,y,x\oplus y\) 能构成一个三角形，无解输出 -1 。

题解

根据三角形不等式也就是 \(y + (x\oplus y) > x, x + y > x\oplus y\)，经过手玩之后发现二进制下类似于 “100000” 和 “111111” 的数，无论 \(y\) 怎么取，都有\(y + (x \oplus y) = x\)，这两种情况无解，否则一定有解：我们找到二进制中最高位的 1 之后用这个幂减去 1 即可：因为这样 \(y + (x \oplus y)\)，一定会产生进位，从而 \(>x\)。

严格证明如下：首先有 \(x + y = x \oplus y + 2(x \& y)\)（这是因为x & y 取出 x 和 y 中都为 1 的位，即进位部分，而x ^ y 取出 x 和 y 中不同的位，即不进位相加的结果），因此不等式 \(x + y > x\oplus y\) 代入后转化为：\(x \& y > 0\)，不等式 \(y + (x\oplus y) > x\) 代入 $ x y = x + y - 2(x& y)\(​ 后可得：\)y > x & y$，这说明 \(x\) 二进制除了最高位的 1 必须还有 1，并且 \(x\) 二进制除了最高位的 0 必须还有 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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int x;
    cin >> x;

    bool is2 = (x & (x - 1)) == 0;
    bool isx = ((x + 1) & x) == 0;

    if (is2 || isx) {
        cout << -1 << endl;
    } else {
        int a = log2(x);
        cout << (1ll << a) - 1 << "\n";
    }
}

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

D

题意

给定 \(n\) 个横坐标及半径，判定在这 \(n\) 个圆中和圆上包含了多少个点。

\(\sum_{i=1}^nr = m\)，且 \(m\le 2\times 10^5\)

题解

一个圆的情况，可参考https://www.incrediblej.cool/2025/01/23/Atcoder-Beginner-Contest-389-%E9%A2%98%E8%A7%A3/#d，使用滑动窗口即可。

现在圆的数目很多，但题目给的限制是半径之和，这提示我们复杂度应该是跟 \(m\) 有关的。

拓展到多个圆，比较容易注意到的是可能会有重复覆盖的情况，我们考虑对于每个圆枚举它们能覆盖的横坐标，得出最大纵坐标，然后对于相同的横坐标，得到最大的纵坐标，这就是相互覆盖的情况下该横坐标涵盖最多点的情况。时间复杂度为 \(O(m\log 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
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, m;
    cin >> n >> m;
    vector<array<int, 2>> a;
    vector<int> x(n + 1), r(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> x[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> r[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = -r[i]; j <= r[i]; j++) {
            int s = sqrt(r[i] * r[i] - j * j);
            a.push_back({x[i] + j, s});
        }
    }
    sort(a.begin(), a.end());
    int ans = 0;
    for (int l = 0, r = 0; l < a.size(); l = r) {
        while (r < a.size() && a[l][0] == a[r][0]) {
            r++;
        }
        int y = 0;
        for (int i = l; i < r; i++) {
            y = max(y, a[i][1]);
        }
        ans += 2 * y + 1;
    }
    cout << ans << "\n";
}

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

E

题意

交互题。

现在有 \(n\) 个点，每次可以询问 3 个点的编号，返回出这三个点构成的三角形中点的编号，你需要找到三个点，它们构成的三角形中没有其他的点。

题解

考虑我们很不幸的初次询问问到了最外围那个包含了其他所有点的最大的三角形，然后返回给我们一个编号。现在，这四个点把三角形分成了三个部分，每个部分就是更小的情况，平均点数减少到了 \(\frac{1}{3}\)。但是，如果系统返回给我们的编号是很靠近我们询问的顶点的三角形，同时我们更不幸地问到了更大的三角形该怎么办呢？我们从之前询问的三个点随机选两个点继续问即可。

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

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

void solve() {
    int n;
    cin >> n;
    int x[] = {1, 2, 3};
    while (true) {
        cout << "?";
        for (int i = 0; i < 3; i++) {
            cout << " " << x[i];
        }
        cout << endl;
        int p;
        cin >> p;
        if (p == 0) {
            cout << "!";
            for (int i = 0; i < 3; i++) {
                cout << " " << x[i];
            }
            cout << endl;
            break;
        }
        int i = rnd() % 3;
        x[i] = p;
    }
}

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

F

题意

在一个平面直角坐标系中给定一个方形区域（平行于 \(x\) 轴和 \(y\) 轴），将这个区域分解成若干小正方形，但这些小正方形的长度只能是 2 的幂，起始位置也只能是当前长度的倍数，求需要的最少方块数。

题解

直接分解好像并不好做，如果递归写法过于复杂了，考虑把方块全部设置为长度为 1 的正方形组成然后合并它们。

我们从小往大尽可能地合成，每四个一样的可以合成一个更大的，因此答案就减少了 3。然后主要考虑如何合成，首先我们需要求出开始位置和结束位置，也就是找到比开始的坐标大的第一个长度的倍数，和比结束坐标小的第一个长度的倍数，从而在包围的这些位置里都可以合成。

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

void solve() {
    int l1, r1, l2, r2;
    cin >> l1 >> r1 >> l2 >> r2;
    int ans = (r1 - l1) * (r2 - l2);
    for (int i = 1; i < 30; i++) {
        int x = 1ll << i;
        int L1 = (l1 + x - 1) / x * x;
        int L2 = (l2 + x - 1) / x * x;
        int R1 = r1 / x * x;
        int R2 = r2 / x * x;
        if (L1 >= R1 || L2 >= R2) {
            continue;
        }
        ans -= 3 * (R1 - L1) / x * (R2 - L2) / x;
    }
    cout << ans << "\n";
}

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

G

题意

给定一个多边形，每个点都有一个权值 \(a_i\)，现在你可以取三个点 \(i,j,k\) 构成一个三角形，然后获得 \(a_i\times a_j\times a_k\) 的分数。可以进行若干次操作，但是形成的三角形不能相交，也不能有共同的顶点，求能获得的最大分数。

题解

考虑题目的限制，不能相交也就是对于两个三角形 \(abc\) 和 \(def\)，不能出现类似 \(a < d < b < e\) 的情况（即每个三角形的顶点之间的区间 \([a+1, b -1]\)如果要出现别的三角形，它的三个顶点只能全部在这个区间里），所以环形的多边形是没有实际意义的，可以看作链处理。

考虑区间dp，设 \(f_{i, j}\) 表示区间 \([i,j]\)的最大答案，那么对于 \(i < k < j\)，有

$f_{i,j} = (f_{i+1,k-1} + f_{k+1,j-1}+a_ia_ja_k) $，除此之外还有

\(f_{i, j} = \max(f_{i,k} + f_{k+1,j})\)。我们第一维枚举终点，第二维枚举起点，第二维枚举起点到终点之间的编号即可。

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<vector<int>> dp(n + 1, vector<int>(n + 1));
    for (int r = 3; r <= n; r++) {
        for (int l = r - 2; l >= 1; l--) {
            for (int i = l; i < r; i++) {
                if (i != l) {
                    dp[l][r] =
                        max(dp[l][r], a[i] * a[l] * a[r] + dp[l + 1][i - 1] +
                                          dp[i + 1][r - 1]);
                }
                dp[l][r] = max(dp[l][r], dp[l][i] + dp[i + 1][r]);
            }
        }
    }
    cout << dp[1][n] << "\n";
}

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