2019陕西省赛J Coolbits-摩杜云开发者社区

也许更好的阅读体验

$2019陕西省赛J Coolbits_c++$
给 $2019陕西省赛J Coolbits_acm_02$ 个区间，需要在每个区间选一个数，使得将这些数与起来的结果最大， $2019陕西省赛J Coolbits_acm_02$ 个区间相互独立（即可选择相同的数）

$2019陕西省赛J Coolbits_贪心算法_04$
从大到小考虑每一位是否能填 $2019陕西省赛J Coolbits_acm_05$ ，同时构造出每个区间选的数是什么
设 2019陕西省赛J Coolbits_c++_06 表示第 $2019陕西省赛J Coolbits_c++_07$ 个区间在满足之前贪心的条件下，目前选的数是什么，现在考虑到第 $2019陕西省赛J Coolbits_oi_08$ 位了，假设第 $2019陕西省赛J Coolbits_oi_08$ 位为 $2019陕西省赛J Coolbits_acm_05$ ，则 2019陕西省赛J Coolbits_c++_06 会变成 2019陕西省赛J Coolbits_贪心算法_12 ，之后能表达的数在区间 2019陕西省赛J Coolbits_c++_13 范围内
如果这个区间和 2019陕西省赛J Coolbits_算法_14 有交集，则说明第 $2019陕西省赛J Coolbits_c++_07$ 个区间在满足前面位的情况下第 $2019陕西省赛J Coolbits_oi_08$ 位可以为 $2019陕西省赛J Coolbits_acm_05$ ，若所有区间第 $2019陕西省赛J Coolbits_oi_08$ 位都可为 $2019陕西省赛J Coolbits_acm_05$ ，那么所有的 2019陕西省赛J Coolbits_c++_20 ，否则就要考虑 2019陕西省赛J Coolbits_c++_06 第 $2019陕西省赛J Coolbits_oi_08$ 位是否为 $2019陕西省赛J Coolbits_acm_05$
若本就不可为 $2019陕西省赛J Coolbits_acm_05$ 自不必说，而如果第 $2019陕西省赛J Coolbits_oi_08$ 位可以为 $2019陕西省赛J Coolbits_acm_05$ ，也可不为 $2019陕西省赛J Coolbits_acm_05$ ，我们可以考虑设之前说的区间为 2019陕西省赛J Coolbits_算法_29 ，现在我们其实并不关心第 $2019陕西省赛J Coolbits_oi_08$ 位如何，为 $2019陕西省赛J Coolbits_acm_05$ 也好，不为 $2019陕西省赛J Coolbits_acm_05$ 也好，只要能让我们在考虑之后的某位能为 $2019陕西省赛J Coolbits_acm_05$ 时能尽可能满足条件即可
此时需要注意到，考虑 2019陕西省赛J Coolbits_acm_34 的二进制是什么样的， 2019陕西省赛J Coolbits_贪心算法_35 ，也就是说，的第 2019陕西省赛J Coolbits_oi_37 位到第 2019陕西省赛J Coolbits_贪心算法_38 位都是 $2019陕西省赛J Coolbits_acm_05$ ，如果我们的区间 2019陕西省赛J Coolbits_算法_14 包含了 2019陕西省赛J Coolbits_acm_34 ，那么第 $2019陕西省赛J Coolbits_oi_08$ 位不需要变成 $2019陕西省赛J Coolbits_acm_05$ ，否则就只能为 $2019陕西省赛J Coolbits_acm_05$ 了

$2019陕西省赛J Coolbits_acm_45$

#include <cstdio>
using namespace std;
const int maxn = 1e5 + 10;
int T, n;
int l[maxn], r[maxn], now[maxn];
int main ()
{
    scanf("%d", &T);
while (T--) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)    scanf("%d%d", &l[i], &r[i]), now[i] = 0;
    int ans = 0;
    for (int i = 29; i >= 0; --i) {
        bool flag = true;
        for (int j = 1; j <= n && flag; ++j) {
            int nl = now[j] | (1 << i), nr = now[j] | ((2 << i) - 1);
            if (nl > r[j] || nr < l[j])   flag = false;
        }
        if (flag) {
            for (int j = 1; j <= n; ++j)    now[j] |= 1 << i;
            ans |= 1 << i;
        }
        else {
            for (int j = 1; j <= n; ++j) {
                int nl = now[j] | (1 << i), nr = now[j] | ((2 << i) - 1);
                if (nl <= r[j] && nr >= l[j] && nl - 1 <= l[j]) now[j] |= 1 << i;
            }
        }
    }
    printf("%d\n", ans);
}
    return 0;
}

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧