[数据结构与算法]Codeforces 467B Fedor and New Game

Fedor and New Game（位运算+模拟）

【题目链接】Problem - 467B - Codeforces

题意：给你m+1个数让你判断所给的数的二进制形式与第m+1个数不想同的位数是否小于等于k，累计答案

思路1：

统计a[i]与x二进制下不同的位数有几个（cnt）若cnt <= k说明满足条件。

返回x的第j位是几：x >> j & 1

【代码实现】

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;
int a[N];

int main()
{

    int n, m, k;
    cin >> n >> m >> k;
    
    for (int i = 0; i < m; i ++ ) cin >> a[i];
    
    int x, res = 0;
    cin >> x;
    for (int i = 0; i < m; i ++ )// 对应数字的二进制表示最多有 k 位不同
    {
        int cnt = 0;
        for (int j = 0; j < n; j ++ )
        {
            // x >> k & 1 判断x的第k位是几
            if((a[i] >> j & 1) != (x >> j & 1)) cnt ++;
        }
        if(cnt <= k) res ++;
    }
    
    cout << res;
    
    return 0;
}

思路二：既然是01二进制，又让我们统计不同的数的个数，我们可以将 x ^ a[i]：这样相同的变为了0，不同的为1，为此我们只需要统计1的个数即可。

【代码实现】

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;
int a[N];

int main()
{

    int n, m, k;
    cin >> n >> m >> k;
    
    for (int i = 0; i < m; i ++ ) cin >> a[i];
    
    int x, res = 0;
    cin >> x;
    for (int i = 0; i < m; i ++ )// 对应数字的二进制表示最多有 k 位不同
    {
        int cnt = 0;
        int tmp = x ^ a[i];
        for(int j = 0; j < n; j ++)
        {
            if((tmp >> j & 1) == 1) cnt ++;
        }
        if(cnt <= k) res ++;
    }
    
    cout << res;
    
    return 0;
}