位元守护者的试炼题解

2024-11-11 青年杯,题解 10 2

大意总结：

Vladislav 有 $n$ 个非负整数，他需要将所有整数分成若干组，使得：

每组中的任意两个数在其二进制表示的前 31 位中，任意一位的值都不能相同（即对每一位 $ 1 \leq i \leq 31 $，任意两个数 $ x $ 和 $ y $ 都满足 $ x_2(i) \neq y_2(i) $）。

目标是找到最少的分组数量，使得所有数被分组完成，并且满足上述条件。

问题核心：
每一组中的数不能在任何二进制位上重复，因此问题可以被转化为：找到一种分组方式，使得每组数的二进制位在 31 位范围内形成无冲突状态，并计算出最少的分组数量。

根据题意我们可以知道：

一组中的数字个数可能为1也可能为2
若一组中有两个数字，那么这两个数字的异或值一定为$2^{31}-1$

因此

当一个数字第一次出现时，我们可以将答案数+1,并将它的待匹配值记录到map中，因为一个数字必定代表一组，我们需要将它的另一个队友记录下来，这样当下一次遇到它的队友时，我们不必将它归为新的一组
否则，我们将它的记录数减一，意味着这个数已经在之前有一个队友在等待它了

代码如下：

#include <bits/stdc++.h>
#define PI acos(-1)
#define all(a) (a).begin(), (a).end()
#pragma GCC optimize(2, "Ofast", "inline")
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
const char nl = '\n';
const int N = 2e5 + 10;
int a[N];
void solve()
{
    int n;
    cin >> n;
    map<int, int> mp;
    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        if(!mp[a[i]]){
            ans++;
            mp[((1 << 31) - 1) ^ a[i]]++;
        }
        else mp[a[i]]--;
    }
    cout << ans << nl;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

题解.md

LXX

我们的征途是星辰大海

青年杯

Warning: Undefined array key "HTTP_ACCEPT_LANGUAGE" in /usr/home/LXX123/domains/www.lxxblog.cfd/public_html/usr/themes/Farallon/comments.php on line 4 Deprecated: stripos(): Passing null to parameter #1 ($haystack) of type string is deprecated in /usr/home/LXX123/domains/www.lxxblog.cfd/public_html/usr/themes/Farallon/comments.php on line 4

位元守护者的试炼 - Lxx's Blog
2024-11-11 11:22

[...]4注释在第一个测试用例中，任意两个数字的最后 31 位是相同的，因此我们需要将每个数字放入自己独立的组。在第二个测试用例中，$a_1 = 0000000000000000000000000000000_2$，$a_2 = 1111111111111111111111111111111_2$，它们可以放在同一组，因为对于每个 $i$（$1 \leq i \leq 31$），$a_1(i) \ne a[...]
青年杯出题 - Lxx's Blog
2024-11-11 11:23

[...]题目列表古代王国的正交拉丁方阵秘文破解石碑中的三阶秘阵二进制谜题：中位数的秘密右左错魔法师的非递减之旅位元守护者的试炼车的突击之路题解列表古代王国的正交拉丁方阵秘文题解破解石碑中的三阶秘阵题解二进制谜题：中位数的秘密题解右左错题解魔法师的非递减之旅题解位元守护者的试炼题解[车的突击之路题解][...]

位元守护者的试炼题解

大意总结：

相关文章