ZOJ Problem Set - 3870

原理：异或

代码语言：javascript复制

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MaxN = 1e5   10;
int a[MaxN], bit[50]; // bit[i]表示有多少个数的最高位的1在第i位上

void solve(int x) {
    int l = 31;
    while(l >= 0) {
        if(x & (1<<l)) {
            bit[l]  ;
            return ;
        }
        l--;
    }
    return ;
}

int main() {
    int T, n;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        memset(bit, 0, sizeof(bit));
        for(int i = 0; i < n; i  ) {
            scanf("%d", &a[i]);
            solve(a[i]);
        }
        int ans = 0;
        for(int i = 0; i < n; i  ) {
            int l = 31;
            while(l >= 0) {
                if(a[i] & (1<<l)) break;
                l--;
            }
            while(l >= 0) {
                if(!(a[i] & (1<<l))) ans  = bit[l];
                l--;
            }
        }
        printf("%dn", ans);
    }
    return 0;
}

原理

0 人点赞