467-B, *1100

Problem - 467B - Codeforces

문제

• 이진수 집합 $\left \{ x_{1},\ x_{2}, ...\ ,\ x_{m} \right \},\ (1 \leq m \leq 1000,\ 1 \leq n \leq 20,\ 1 \leq x_{i} \leq 2^{n}-1)$ 중
  $x_{m+1}$와 각각의 자릿수를 비교했을 때 다른 비트가 $k$이하인 원소의 개수는?
• $O(mn)$ 정도 알고리즘은 통과할 수 있다

 

$O(mn)$

두 이진수 $a$, $b$에서 자리수는 같은 데 다른 비트의 수는
$\text{a^b}$에서 1인 bit 수를 세면 된다 $O(log\ \text{a^b})$

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
 
int n, m, k;
ll Fedor;
vector<ll> player;
 
int cnt_bit_one(ll binary)
{
    int cnt = 0;
    while(binary){
        cnt ++;
        binary = binary & (binary-1);
    }
    return cnt;
}
 
int friends()
{
    int cnt = 0;
    for(auto e: player){
        if(cnt_bit_one(Fedor^e)<=k) cnt++;
    }
    return cnt;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> m >> k;
    ll tmp;
    for(int i = 0; i < m; i++) {
        cin >> tmp;
        player.emplace_back(tmp);
    }
    cin >> Fedor;
 
    cout << friends() << endl;
 
    return 0;
}cs