自动搬运

查看原文

来自洛谷，原作者为

	Flaw_Owl 当你穿过了暴风雨，你就不再是原来的那个人了。

搬运于2025-08-24 22:50:25，当前版本为作者最后更新于2024-06-05 08:39:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P9649 [SNCPC2019] Coolbits 题解

题目链接：P9649 [SNCPC2019] Coolbits

题目摘要

二进制运算 + 贪心思想：第 $i$ 位置 $1$ 的贡献要比之后每一位都置 $1$ 要大。

题目分析

乍一看感觉是和 P9612 [CERC2019] Light Emitting Hindenburg 有点类似的题。都是使得若干个数最后的按位与之和最大，不同的是本题是给定一些区间，在区间里选数；而 P9612 则是直接给定了一些数。因此本题要稍微难一些。

如果你已经做过 P9612，你就会知道这道题的大致思想是贪心。如果我们枚举最后结果的每一位，我们会发现 10000 要比 01111 要大，即 $1$ 的数量贵精不贵多，如果高位上能置 $1$，那么这个数是必要选的。

然而现在的问题是，现在不是从 $n$ 个数选择的问题，而是从 $n$ 个区间中取一个数。——但这也没有关系，我们按照同样的思路进行分析，仍然是类似于枚举答案的思想。如果第 $i$ 位能置 $1$，就说明选择出的这 $n$ 个数的这一位都是 $1$。如果不可能，说明这一位不可能是 $1$ 了，跳过这一位；如果可以，那么区间就会被缩小，变成从最小的该位为 $1$ 的数到右端点。

具体来说，即为：

int cal(int x, int i)
{
    if (!((x >> i) & 1))
        x = ((x >> i) | 1) << i;
    return x;
}

这个函数计算了对于每一个区间的左端点，如果它的第 $i$ 位为 $1$，那么区间不用改变，否则变为除了那一位为 $1$ 之外，其它位都为 $0$ 的数，即新的左端点。改变之后我们还要判断一下它会不会超过右端点（即新的区间能不能存在）。

一些细节

• 数据范围是 $0 \leq x \leq 10^9$，大概是 int 类型，即 $2^{31} - 1$。我们枚举答案的位数的时候就要从 $30$ 枚举到 $0$。
• 位运算的优先级比较容易出错，注意多加括号。

参考代码

#include <iostream>
#include <cctype>
#define ll long long

using namespace std;

int read()
{
    int x = 0, f = 1;
    char ch = 0;
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const int maxN = 1e5 + 5;

int T;
int n;
ll ans;
int L[maxN], R[maxN];

int cal(int x, int i)
{
    if (!((x >> i) & 1))
        x = ((x >> i) | 1) << i;
    return x;
}

int main()
{
    T = read();
    while (T--)
    {
        ans = 0;
        n = read();
        for (int i = 1; i <= n; i++)
            L[i] = read(), R[i] = read();
        for (int i = 30; i >= 0; i--)
        {
            ll d = 1ll << i;
            bool flag = false;
            for (int j = 1; j <= n; j++)
                if (cal(L[j], i) > R[j])
                {
                    flag = true;
                    break;
                }
            if (flag)
                continue;
            for (int j = 1; j <= n; j++)
                L[j] = cal(L[j], i);
            ans |= d;
        }
        printf("%lld\n", ans);
    }
    return 0;
}