Codeforces Round 1030 (Div. 2) A-C题解

A. Equal Subsequences

We call a bitstring$^{\text{∗}}$ perfect if it has the same number of $\mathtt{101}$ and $\mathtt{010}$ subsequences$^{\text{†}}$. Construct a perfect bitstring of length $n$ where the number of $\mathtt{1}$ characters it contains is exactly $k$.

It can be proven that the construction is always possible. If there are multiple solutions, output any of them.

$^{\text{∗}}$A bitstring is a string consisting only of the characters $\mathtt{0}$ and $\mathtt{1}$.

$^{\text{†}}$A sequence $a$ is a subsequence of a string $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly zero or all) characters.

本题想让你构建一个长度为$n$的“完美字符串”，里面恰好有$k$个$1$，其余都是$0$。

“完美字符串”：一个字符串如果它的$101$子序列数量等于$010$子序列数量，我们就说它是完美的。

思路：我们只要保证字符串中既没有$101$也没有$010$，那么它们的数量就自然相等。

一种最简单的做法，就是把所有的$1$都聚在一起，然后把所有的$0$都聚在一起。

代码：

//
// Created by xiaoeyv on 2025/6/17.
//

#include <bits/stdc++.h>
using namespace std;

int t;

int main() {
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<char> a(n, '0');
        for (int i = 0; i < k; i++)
            cout << "1";
        for (int i = k; i < n; i++)
            cout << "0";
        cout << endl;
    }
    return 0;
}

B. Make It Permutation

There is a matrix $A$ of size $n\times n$ where $A_{i,j}=j$ for all $1 \le i,j \le n$.

In one operation, you can select a row and reverse any subarray$^{\text{∗}}$ in it.

Find a sequence of at most $2n$ operations such that every column will contain a permutation$^{\text{†}}$ of length $n$.

It can be proven that the construction is always possible. If there are multiple solutions, output any of them.

$^{\text{∗}}$An array $a$ is a subarray of an array $b$ if $a$ can be obtained from $b$ by deleting zero or more elements from the beginning and zero or more elements from the end.

$^{\text{†}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

这道题这位大佬讲的比较通透，传送门：https://www.luogu.com.cn/article/uh4l4wzp 首先我们可以发现，对于第$i$行，我们只需要进行一次$i 1 i$和一次$i i+1 n$（若$i$<$n$才执行此操作） 即可。 代码：

//
// Created by xiaoeyv on 2025/6/17.
//
#define maxn 5010
#include <bits/stdc++.h>
using namespace std;

int k, n;

int main() {
    cin >> k;
    while (k--) {
        cin >> n;
        cout << 2 * n - 1 << endl;
        for (int i = 1; i <= n; ++i) {
            if (i < n)
                cout << i << " " << i + 1 << " " << n << endl;
            cout << i << " " << 1 << " " << i << endl;
        }
    }
}

C. Make It Beautiful

You are given an array $a$ of $n$ integers. We define the $\text{beauty}$ of a number $x$ to be the number of $1$ bits in its binary representation. We define the beauty of an array to be the sum of beauties of the numbers it contains.

In one operation, you can select an index $i$ $(1 \le i \le n)$ and increase $a_i$ by $1$.

Find the maximum beauty of the array after doing at most $k$ operations.

美丽值：数中二进制表示中 1 的个数

本题会给你$n$个数，让你操作k次，每次操作可以给一个数+1，求操作后最大的美丽数的和。、

我们希望知道每个数第 $j$ 次美丽值 +1 需要多少代价（即加几次才会产生下一个 1）。 这个代价是根据该数当前二进制中最低位的连续 1 来决定的，直到找到第一个 位，然后将它变为 1。

我们可以预处理每个 a[i] 的前若干次“下一个美丽值+1”的代价，用二维数组 cost[i][j] 表示：第 i 个数，进行第 j 次美丽值提升的代价是多少。

美丽值是离散地增长的，我们希望每次都选择当前最便宜的代价去获得一次 +1 的收益。

• 维护一个最小堆，堆中的每个节点包含：

  • 当前代价 cost（即增加当前 a[i] 的第 j 次美丽值的花费）
  • 数组下标 i，和这是第几次操作 j

• 每次从堆中取出最小代价：

  • 若剩余操作次数 k 足够，执行这次操作，k -= cost，ans++
  • 然后尝试将该数的下一次美丽值增加（即 j+1 次）推入堆中

这样每次都以最小成本去换一次美丽值的增量，保证了贪心的全局最优性。

代码：

#include <bits/stdc++.h>
using namespace std;

static const int maxn = 5010;
long long a[maxn];
long long cost[maxn][64];

struct Node {
    long long cost;
    int i, j;

    bool operator>(const Node &o) const {
        return cost > o.cost;
    }
};

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

    int T;
    cin >> T;
    while (T--) {
        int n;
        long long k;
        cin >> n >> k;

        long long ans = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            ans += __builtin_popcountll(a[i]);
        }

        for (int i = 1; i <= n; i++) {
            int bit = 0;
            for (int j = 1; j <= 63; j++) {
                while (bit < 63 && (a[i] & (1LL << bit))) {
                    bit++;
                }
                if (bit >= 63) {
                    cost[i][j] = LLONG_MAX;
                } else {
                    cost[i][j] = (1LL << bit);
                    bit++;
                }
            }
        }

        priority_queue<Node, vector<Node>, greater<Node> > pq;
        for (int i = 1; i <= n; i++) {
            pq.push({cost[i][1], i, 1});
        }

        while (!pq.empty()) {
            auto cur = pq.top();
            pq.pop();
            long long c = cur.cost;
            int i = cur.i, j = cur.j;

            if (c == LLONG_MAX || c > k) break;

            k -= c;
            ans++;

            if (j < 63) {
                pq.push({cost[i][j + 1], i, j + 1});
            }
        }
        cout << ans << endl;
    }
    return 0;
}