【进制转换＋异或运算】XOR Sorting HihoCoder - 1509

迷南。 2022-05-31 01:45 137阅读 0赞

Think:  
1知识点：【进制转换＋异或运算】  
2题意：输入一个序列a\[1..n\]，判断满足一下两个条件的S有多少个  
(1):0 <= S < pow(2, 60)  
(2):对于i(1 <= i < n)，(a\[i\] xor S) <= (a\[i+1\] xor S)  
3解题思路：  
(1):先将a\[i\]和a\[i+1\]转换为二进制，然后通过异或运算相同为零不同为一的性质和(a\[i\] xor S) <= (a\[i+1\] xor S)的条件确定可以确定的位，然后对于无法确定的位则均有两种取值(0、1)，进而得到满足条件的S的个数

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    typedef long long LL;
    
    int rec[64], s1[64], s2[64];
    
    bool solve(LL x, LL y);
    LL power(LL x, int k);
    
    int main(){
        int n, i, cnt, flag;
        LL a, t;
        scanf("%d", &n);
        flag = 1;
        memset(rec, -1, sizeof(rec));
        scanf("%lld", &t);
        for(i = 1; i < n; i++){
            scanf("%lld", &a);
            if(!solve(a, t)) flag = false;
            t = a;
        }
        if(!flag){
            printf("0\n");
        }
        else {
            cnt = 0;
            for(i = 0; i < 60; i++){
                if(rec[i] == -1) cnt++;
            }
            printf("%lld\n", power(2, cnt));
        }
        return 0;
    }
    LL power(LL x, int k){
        LL ans = 1;
        while(k){
            if(k & 1) ans *= x;
            x *= x;
            k >>= 1;
        }
        return ans;
    }
    bool solve(LL x, LL y){
        int i;
        for(i = 0; i < 60; i++){
            if(x & ((LL)1 << i)) s1[i] = 1;
            else s1[i] = 0;
            if(y & ((LL)1 << i)) s2[i] = 1;
            else s2[i] = 0;
        }
        for(i = 59; i >= 0; i--){
            if(s1[i] == 1 && s2[i] == 0){
                if(rec[i] == -1 || rec[i] == 1) rec[i] = 1;
                else return false;
                break;
            }
            else if(s1[i] == 0 && s2[i] == 1){
                if(rec[i] == -1 || rec[i] == 0) rec[i] = 0;
                else return false;
                break;
            }
        }
        return true;
    }

[vjudge]: https://vjudge.net/problem/HihoCoder-1509