Codeforces Round 940 (Div. 2)

发表于 更新于 分类于 阅读次数： 本文字数： 1.4k 阅读时长 ≈ 5 分钟
The most important thing in life is to have a great aim and the determination to attend it.

A. Stickogon

思路：

  • 题目要求每条边只能有一个木棍，然后我们可以联想到最小的正多边形是正三角形，所以只需要将每种木棍的个数存起来，然后求可以组成多少个正三角形即可

时间复杂度：\(O(n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(110);
    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;
        a[x]++;
    }

    int ans = 0;
    for (int i = 1; i <= 100; i++) {
        ans += a[i] / 3;
        a[i] %= 3;
    }
    std::cout << ans << "\n";
}

B. A BIT of a Construction

思路：

  • 有一个关于位运算的前置知识，将一个int范围里的每一位都置为1可以这样操作(1 << 31) - 1，那么我们将一个小于x的最大数的每一位置为1就是(1 << __lg(x)) - 1，所以我们只需要把小于等于k的最大那个二进制下1最多的那个数求出来即可，然后输出k - x和n - 2个0。

时间复杂度：\(O(n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve() {
    int n, k;
    std::cin >> n >> k;

    if (n == 1) {
        std::cout << k << "\n";
    } else {
        int b = std::__lg(k);
        std::cout << (1 << b) - 1 << " " << k - (1 << b) + 1 << " ";
        for (int i = 3; i <= n; i++) {
            std::cout << 0 << " ";
        }
        std::cout << "\n";
    }
}

C. How Does the Rook Move?

题目大意：每次玩家可以选择一个位置 \((r_i, c_i)\) 然后机器人会在镜像位置 \((c_i, r_i)\) 也放一个棋子，如果玩家在对角线上放一个棋子 \((i, i)\) ，那么机器人不会操作，然后题目要求给你一个残局，问有多少种满足 \(N\) 皇后问题的解 \(\rightarrow\) 每行每列都只存在一个棋子

思路：

  • 我们可以发现，每当我们在非对角线的位置 \((r_i, c_i)\) 下一个任意颜色的棋子时，机器人在镜像位置 \((c_i, r_i)\) 也会下一个棋子，那么我们将丢失2行和2列，如果在对角线位置下一个棋子，我们只会丢失1行1列。
  • 我们用分治的思想考虑，每次下一个棋子，这一个或者两个棋子，会把棋盘分割为1个或者4个小的棋盘，棋盘的大小不重要，重要的在于，大的棋盘会变成更小的棋盘，而且被分割出的棋盘一定是一个边长为k的正方形，所以问题就变成了求一个边长为k的棋盘上的n皇后问题。
    • 对于一个边长为1的正方形棋盘，它的方案数为1，一个边长为2的棋盘，它的方案数为3，我们可以发现，一个边长为x的棋盘，它的方案数由一个边长为x - 1的棋盘继承而来。
    • 对于我们下一步棋，我们如果下在对角线，那么会损失1行和1列，会产生一个k - 1阶的新棋盘，然后在这个新的棋盘中，其方案数为 \(1 \times dp[k - 1]\)
    • 如果我不下在对角线处，就会损失2行2列，那么我们有 \(2 \times (k - 1)\) 种下棋方案，剩下k - 2阶的棋盘，那么在一个k - 2阶的棋盘里，它的方案数为 \(2 \times (k - 1) \times dp[k - 2]\)
  • 所以，对于一个N阶的棋盘，它的方案数为 \(dp[k] = dp[k - 1] + 2 \times (k - 1) \times dp[k - 2]\)

时间复杂度：\(O(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
constexpr int N = 3E5 + 10, P = 1E9 + 7;
i64 dp[N];

void solve() {
    int n, k;
    std::cin >> n >> k;

    for (int i = 0; i < k; i++) {
        int r, c;
        std::cin >> r >> c;

        if (r == c) {
            n -= 1;
        } else {
            n -= 2;
        }
    }
    std::cout << dp[n] << "\n";
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    dp[0] = dp[1] = 1;
    for (int i = 2; i <= N; i++) {
        dp[i] = dp[i - 1] + (dp[i - 2] * 2) % P * (i - 1) % P;
        dp[i] %= P;
    }

    int t;
    std::cin >> t;

    while (t--) {
        solve();
    }    

    return 0;
}

D. A BIT of an Inequality

思路：

  • 可以把题目的式子变形一下 \(f(x, y) \space \oplus \space f(y, z) > f(x, z)\)
  • 根据题目给的 \(n\) 的范围(\(10^5\))，这题就一定不是枚举，不然就是 \(O(n^3)\)，铁定超时。要做到 \(O(1)\) 的时间查询，那么我们可以采用异或前缀和
  • 我们根据异或前缀和的思路，把式子变形一下 \(f(x, y) \space \oplus \space f(y, z) > f(x, z) \Rightarrow (S_z - S_{x - 1}) \space \oplus \space a_y > (S_z - S_{x - 1})\)，那么我们可以明确的知道，这个式子左边多异或的那个 \(a_y\) 它可以使得整个式子变大，然后我们考虑，在一个数什么情况下，它异或另一个数，可以使得结果变大，一定是这个 \(a_y\) 的最高位是 \(1\)，然后我们可以按这个思路，设数组 \(bit[i][j]\) 表示第 \(i\) 位前缀和 \(1\) 的个数，利用乘法原理，进行计算有多少个三元组满足条件。

时间复杂度：\(O(30 \times 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
void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }

    std::vector<i64> s(n + 1);
    std::vector<std::vector<i64>> bit(30, std::vector<i64>(n + 1));
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] ^ a[i];
        for (int j = 0; j < 30; j++) { // check the kth bit
            bit[j][i] = bit[j][i - 1] + (s[i] >> j & 1);
        }
    }

    i64 ans = 0;
    for (int i = 1; i <= n; i++) {
        int k = 29;
        while (k >= 0 && (a[i] >> k & 1) == 0) k--; // find the highest bit of 1
        if (k == -1) continue ; // if x is 0 
        ans += (bit[k][n] - bit[k][i - 1]) * bit[k][i - 1]; // the number of 1
        ans += (n - i + 1 - (bit[k][n] - bit[k][i - 1])) * (i - bit[k][i - 1]); // the number of 0
    }
    std::cout << ans << "\n";
}