题解：P9649 [SNCPC2019] Coolbits

· · 题解

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 的数，即新的左端点。改变之后我们还要判断一下它会不会超过右端点（即新的区间能不能存在）。

一些细节

参考代码

#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;
}