【题解】CF1013B And

题面传送门

解决思路

首先我们可以得出，$ a $ $\&$ $ x $ $=$ $ a $ $\&$ $ x $ $\&$ $ x $。由此得知，同一个 $a$ 反复 $\&$ $x$ 是没有意义的。所以我们得到，答案仅可能是以下几种情况：

$ans = 0$ ，即有相同的数字，不需要操作。
$ans = 1$ ，即对于某个 $a_i$ $\&$ $ x $ $=$ $a_j$，其中 $1 \le i,j\le n $ 且 $j \ne i$ 。
$ans = 2$ ，即对于某两个 $a_i$ $\&$ $ x $ $=$ $a_j$ $\&$ $ x $ ，其中 $1 \le i,j\le n $ 且 $j \ne i$ 。
$ans = -1$ ，即对于任意的 $a_i$ $\&$ $ x $ $\ne$ $a_j$ $\&$ $ x $ ，其中 $1 \le i,j\le n $ 且 $j \ne i$ 。

有了这个思路，再看到$a_i \le 10^5$ ，我们就可以借助桶存下每个 $a_i$ $\&$ $ x $ ，然后判断即可。

AC Code

#include<bits/stdc++.h>

using namespace std;

int n,x,a[100005],t[100005],t2[100005],fl;

//t储存a[i]&x,t2用于判重（ans=0的情况）

int main(){

    scanf("%d%d",&n,&x);

    for(int i=1;i<=n;i++){

    	scanf("%d",&a[i]);

    	if(t2[a[i]]!=0){

    		printf("0");

    		return 0;     //ans=0的情况

		}

		t2[a[i]]++;

    	if((a[i]&x)!=a[i]) t[a[i]&x]++;  //a[i]&x=a[i]的不能计算在内

    	if(t[a[i]&x]>=2) fl=1;  //如果出现过两次，就必有解

	}

	for(int i=1;i<=n;i++){

		if(t[a[i]]>0){

			printf("1");  //ans=1的情况

			return 0;

		}

	}

	if(fl==1) printf("2");   //有解

	else printf("-1");       //无解

  	return 0;

}

巴特西

【题解】CF1013B And

题面传送门

解决思路

AC Code

最新文章

热门文章