B. And

题目链接

Codeforces Round #500 (Div. 2) [based on EJOI]--B. And

题解

简单题。题意大概是给定一组数与一个数x,每次操作可以使某一个数变为ai&x,求最少操作数使这一组数中存在两个一样的数,如果没有则输出-1。
首先判断原本的数列中是否有相同的数,之后每个数都处理一遍看是否有ai&x与原数列中的数相同,最后判断是否有两个数经过处理只有相同即可。

代码

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

int n, q1, x, q2;
int a[100005];
int num[100005];
int cnt[100005];
bool pd(false);
int ans(233);

int main(){
    cin >> n >> x;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        num[a[i]]++;
        if (num[a[i]] == 2) {
            cout << 0 << endl;
            return 0;
        }
    }
    for (int i = 1; i <= n; i++) {
        q1=a[i];
        q2 = q1 & x;
        if (q2 != q1) { 
            cnt[q2]++;
            num[q2]++;
        }
        if (num[q2] == 2) {
            pd = true;
            ans = min(ans, cnt[q2]);
        }
    }
    if (pd)cout << ans << endl;
    else cout << -1 << endl;
}

标签: greedy

添加新评论