位运算

· · 个人记录

P9649 [SNCPC2019] Coolbits

首先，我们要知道什么是位与运算。位与就是一个十进制数的二进制表示法的数字，和其他的数字判断。如果一个位置上都是 1 就为 1 否则都为 0。

那么，我们就可以从后往前枚举所有的二进制位，也就是让这个位置上的答案为 1。然后我们就开始尝试缩小范围。

然后我们就找寻看看是不是有一个 l_j 满足我们枚举的第 i 位为 1 的情况。然后对于所有的点将他们缩小范围。答案加上 2^{i - 1}。最后输出即可。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n;
int l[100005],r[200005];
int cd(int x,int i){
    if(((x >> i) & 1) == 0){
        x = x >> i;
        x |= 1;
        x = x << i;
    }
    return x;
}
void work(){
    int ans = 0;
    for(int i = 31 ; i >= 0 ; i --){
        bool f = 1;
        for(int j = 1 ; j <= n ; j ++){
            if(cd(l[j] , i) > r[j]){
                f = 0;
                break;
            }
        }
        if(f == 0){
            continue;
        }
        for(int j = 1 ; j <= n ; j ++){
            l[j] = cd(l[j] , i);
        }
        ans += (1ll << i);
    }
    cout << ans << endl;
    return;
}
signed main(){
    cin >> T;
    while(T --){
        cin >> n;
        for(int i = 1 ; i <= n ; i ++){
            cin >> l[i] >> r[i];
        }
        work();
    }
    return 0;
}

P9612 [CERC2019] Light Emitting Hindenburg

刚读完题目，脑袋还是朦朦的，有点不懂是什么意思，那么我就先给你简化题意吧。在 n 个数中选 k 个数，让他们按位或后答案更大。

而位或与位与差不多，但是位或为 1 的情况更多，参与位或的两个数中的某一位，只要有一位是 1 那么位或出来的答案中这一位就是 1。

一样的，我们仍旧是从后往前枚举每一位，当我们发现有 >= k 个我们没有算的数中的第 i 位为 1 的时候。我们其实就可以选他了。将这个数标记后一直循环，直到不能在标记了为止。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,cnt;
int a[200005];
bool vis[1000005];
signed main(){
    cin >> n >> k;
    for(int i = 1 ; i <= n ; i ++){
        cin >> a[i];
        vis[i] = 1;
    }
    for(int i = 30 ; i >= 0 ; i --){
        int ans = 0;
        for(int j = 1 ; j <= n ; j ++){
            if((a[j] >> i) & 1){
                ans ++;
            }
        }
        if(ans >= k){
            int sum = 0;
            for(int j = 1 ; j <= n ; j ++){
                if((a[j] >> i) & 1){
                    a[++sum] = a[j];
                }
            }   
            n = sum;
            cnt += (1ll << i);
        }
    }
    cout << cnt;
    return 0;
}