【位运算知识+前缀思路+后缀思路】CS Course HDU - 6186

我会带着你远行 2022-06-09 11:12 124阅读 0赞

Think:  
1知识点：位运算  
2题意：输入一个序列，询问当暂时取出一个数之后，输出剩下的所有数的从左区间至右区间的与/或/异或的值  
3思路：  
1>记录序列内所有数的在每一位上的累加值，进而通过与运算(同为1才为1)/或运算(存在1即为1)/异或运算(“撤销功能”:异或一个数2遍等于不异或这个数)的性质进行求解  
2>记录前缀+记录后缀  
4思考与反思：  
1>注意如何将一个十进制数转化为其对应的二进制数  
2>异或符号不要写错

[vjudge题目链接][vjudge]

以下为Accepted代码——思路1

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    int a[101400], num[40], tmp[40];
    
    void Sep(int x);
    void Ans(int n, int id, int vor);
    
    int main(){
        int n, m, i, id, vor;
        while(~scanf("%d %d", &n, &m)){
            memset(num, 0, sizeof(num));
            scanf("%d", &a[1]);
            vor = a[1];
            Sep(a[1]);
            for(i = 2; i <= n; i++){
                scanf("%d", &a[i]);
                vor ^= a[i];
                Sep(a[i]);
            }
            while(m--){
                scanf("%d", &id);
                Ans(n, id, vor);
            }
        }
        return 0;
    }
    void Sep(int x){
        for(int i = 0; i < 32; i++){
            num[i] += x%2;
            x /= 2;
            if(!x)
                break;
        }
    }
    void Ans(int n, int id, int vor){
        int x = a[id], y, z;
        memset(tmp, 0, sizeof(tmp));
        for(int i = 0; i < 32; i++){
            tmp[i] += x%2;
            x /= 2;
            if(!x)
                break;
        }
        y = z = 0;
        for(int i = 0; i < 32; i++){
            if(num[i]-tmp[i] == n-1)
                y += (1<<i);
            if(num[i]-tmp[i] > 0)
                z += (1<<i);
        }
        printf("%d %d %d\n", y, z, vor^a[id]);
    }

以下为Accepted代码——思路2

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 101400;
    
    int a[N];
    int u1[N], v1[N], w1[N];
    int u2[N], v2[N], w2[N];
    
    int main(){
        int n, m, i, id;
        while(~scanf("%d %d", &n, &m)){
            for(i = 1; i <= n; i++)
                scanf("%d", &a[i]);
            u1[1] = v1[1] = w1[1] = a[1];
            for(i = 2; i <= n; i++){
                u1[i] = u1[i-1] & a[i];
                v1[i] = v1[i-1] | a[i];
                w1[i] = w1[i-1] ^ a[i];
            }
            u2[n] = v2[n] = w2[n] = a[n];
            for(i = n-1; i >= 1; i--){
                u2[i] = u2[i+1] & a[i];
                v2[i] = v2[i+1] | a[i];
                w2[i] = w2[i+1] ^ a[i];
            }
            while(m--){
                scanf("%d", &id);
                if(id == 1)
                    printf("%d %d %d\n", u2[2], v2[2], w2[2]);
                else if(id == n)
                    printf("%d %d %d\n", u1[n-1], v1[n-1], w1[n-1]);
                else
                    printf("%d %d %d\n", u1[id-1] & u2[id+1], v1[id-1] | v2[id+1], w1[id-1] ^ w2[id+1]);
            }
        }
        return 0;
    }

[vjudge]: https://vjudge.net/problem/HDU-6186