Codeblocks，CodeForces - 1013B And 與運算暴力

題目鏈接：

https://vjudge.net/problem/1735275/origin

基本思路：

Codeblocks，本題思路比較簡單，首先，我們知道 a & x = b, b & x = b; 所以，一個數通過與運算改變只能改變一次！

所以，這里就有一種暴力的寫法，三次for循環，時間復雜度是O(3n)。

第一次，從1到n遍歷一遍，計算各個元素出現的次數，如果大于等于2，則輸出0，結束。

第二次，從1到n遍歷，如果存在 vis[ a[i]&k ] >= 2 并且 與k與運算后的值與之前的不同，即a[i] != a[i]&k，于是輸出1，結束。

codeblocks代碼、第三次，從1到n遍歷，對a[i]&k的元素加一，即vis[ a[i]&k ]++，如果存在vis[ a[i]&k ] >= 2 && (a[i]&k) != a[i]，則輸出2，結束。

AC代碼如下：

#include <iostream>
#include <cstdio>using namespace std;
const int MX = 1e5+10;
int a[MX], vis[MX];int main()
{int n, k;scanf("%d%d", &n, &k);for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);for(int i = 1; i <= n; ++i){vis[ a[i] ]++; // 第一次統計一下元素的個數if(vis[ a[i] ] >= 2){printf("0\n");return 0;}}for(int i = 1; i <= n; ++i){// 一次與運算有值并且這個與運算得到的結果和之前的值不同時則說明操作一次即可if(vis[ a[i]&k ] == 1 && a[i] != (a[i]&k)) // 注意要加括號！
        {printf("1\n");return 0;}}for(int i = 1; i <= n; ++i){vis[ a[i]&k ]++; // 操作兩次時直接遍歷一遍if(vis[ a[i]&k ] >= 2 && a[i] != (a[i]&k)) // 這里要注意一下與運算重復的現象！
        {printf("2\n");return 0;}}printf("-1\n");return 0;
}

?

第二種解法用到了flag標記。

codeforces官方題解。第一種情況，未進行與運算就存在，則輸出0。

第二種情況，?進行了一次與運算與之前元素重復，或者輸入元素與之前與運算元素重復，則與對比1求最小值。

第三種情況，?與運算結果與之前與運算結果相同則與2對比得最小值。

下面是AC代碼：

#include <iostream>
#include <cstdio>using namespace std;
const int INF = 0x3f3f3f3f;
const int MX = 1e5+10;
bool flag[MX][3]; // 一個數有兩種狀態！int main()
{int ans = INF;int n, k;scanf("%d%d", &n, &k);for(int i = 1; i <= n; ++i){int x;scanf("%d", &x);int y = x&k;if(flag[x][0]) // 未進行與運算就存在，則輸出0
        {ans = min(ans, 0);}else if(flag[y][0] || flag[x][1]) //進行了一次與運算與之前元素重復，或者輸入元素與之前與運算元素重復，則與對比1求最小值
        {ans = min(ans, 1);}else if(flag[y][1]) // 與運算結果與之前與運算結果相同則與2對比得最小值
        {ans = min(ans, 2);}flag[x][0] = true;flag[y][1] = true;}if(ans == INF) printf("-1\n"); // 都不符合作則輸出-1else printf("%d\n", ans);return 0;
}

用運算關系表示A發生B與C不發生。如有疑問，歡迎評論指出！