2019陕西省省赛J-位运算+贪心

题目大意：

给你$n$个区间,你需要从每个区间中取出一个数。使得他们按位与后最大。

题目思路：

从高位开始尝试置1.然后check每个区间。
我将问题转化为:找到小于$R$的最大的包含当前$ans$的数$X$.然后check它和$L$的大小关系.

这样就从 区间存在性问题 转化为: 最值问题.这个时候同样贪心做即可.

这样还是带两个log,需要在两处加剪枝，最后时间从T优化为277ms

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vl vector<ll>
#define fi first
#define se second
const int maxn = 1e5 + 5;
const int maxb = 30;
const int mod = 1e9 + 7;
struct Node {
    
    int first , second;
}a[maxn];
int bk[maxn] , u , v , tg[maxn];
inline int calc (int up , int x , int id){
    
    if ((up & x) == x) return up; // 剪枝1:防止全1(或很多1)的up出现
    for (int i = maxb ; i >= 0 ; i--){
    
        u = (up >> i) & 1;
        v = (x >> i) & 1;
        if (u == v) continue;
        if ((x | (1 << i)) > up) {
     // 这种情况代表这个区间往后都不用再check了.
            tg[id] = true;
            return x | ((1 << i) - 1);
        }
        x |= (1 << i);
    }
    assert(x == up);
    return x;
}
template <typename T>
void read(T & x){
     x = 0;T f = 1;char ch = getchar();while(!isdigit(ch)){
    if(ch == '-') f = -1;
ch = getchar();}while (isdigit(ch)){
    x = x * 10 + (ch ^ 48);ch = getchar();}x *= f;}
template <typename T>
void write(T x){
    if(x < 0){
    putchar('-');x = -x;}if (x > 9)write(x / 10);putchar(x % 10 + '0');}
int main()
{
    
    int t; read(t);
    while (t--){
    
        int n ; read(n);
        for (int i = 1 ; i <= n ; i++){
    
            read(a[i].first);
            read(a[i].second);
            bk[i] = false;
        }
        int ans = 0;
        for (int i = maxb ; i >= 0 ; i--){
    
            ll tmp = ans | (1 << i);
            bool ok = true;
            for (int j = 1 ; j <= n && ok; j++){
    
                if (bk[j]) continue;
                if (tmp > a[j].second) ok = false;
                tg[j] = false;
                int mx = calc (a[j].second , tmp , j);
                if (mx < a[j].first) ok = false;
            }
            if (ok) {
    
                ans = tmp;
                for (int j = 1 ; j <= n ; j++) if (tg[j]) bk[j] = true;
            }
        }
        write(ans);
        puts("");
    }
    return 0;
}