1013 B. And

鏈接

[http://codeforces.com/contest/1013/problem/B]

題意

給你一個n和x,再給n個數，有一種操作用x&a[i]取代，a[i],問使其中至少兩個數相同，要多少次操作，如果不能輸出-1.

思路

x&a[i],無論&多少次，a[i]都只有一次改變,所以可以知道，有這幾種情況ans=0,1,2,-1;
0表示不需要操作已經有兩個以上的數相同了，1代表要么x&a[i]==a[j],要么a[i]==x&a[j],i!=j.
2代表x&a[i]==x&a[j],i!=j;

代碼

#include<bits/stdc++.h>
using namespace std;
int n,x;
bool f[100005][2];
int main(){int a;cin>>n>>x;int ans=100000;for(int i=0;i<n;i++){cin>>a;int b=x&a;if(f[a][0]){ans=0;}else if(f[a][1]||f[b][0]){ans=min(ans,1); }else if(f[b][1])ans=min(ans,2);f[a][0]=1;f[b][1]=1;}if(ans==100000){cout<<-1<<endl;return 0;}cout<<ans<<endl;return 0;
}