題目描述

有 $N$ 種食材，編號從 $0$ 至 $N?1$，其中第 $i$ 種食材的美味度為 $a_i$。

不同食材之間的組合可能產生奇妙的化學反應。具體來說，如果兩種食材的美味度分別為 $x$ 和 $y$ ，那么它們的契合度為 $x\ \text{and}\ y $。

其中，$\text{and}$ 運算為按位與運算，需要先將兩個運算數轉換為二進制，然后在高位補足 ，再逐位進行與運算。例如，$12$ 與 $6$ 的二進制表示分別為 $1100$ 和 $0110$ ，將它們逐位進行與運算，得到 $0100$ ，轉換為十進制得到 4，因此 $12\text{?and?}6=4$。在 C++ 或 Python 中，可以直接使用 & 運算符表示與運算。

現在，請你找到契合度最高的兩種食材，并輸出它們的契合度。

輸入格式

第一行一個整數 $N$，表示食材的種數。

接下來一行 $N$ 個用空格隔開的整數，依次為 $a_1,?,a_N$，表示各種食材的美味度。

輸出格式

輸出一行一個整數，表示最高的契合度。

輸入輸出樣例 #1

輸入 #1

3
1 2 3

輸出 #1

2

輸入輸出樣例 #2

輸入 #2

5
5 6 2 10 13

輸出 #2

8

說明/提示

樣例解釋 1

可以編號為 $1,2$ 的食材之間的契合度為 $2\text{and}3=2$，是所有食材兩兩之間最高的契合度。

樣例解釋 2

可以編號為 $3,4$ 的食材之間的契合度為 $10\text{and}13=8$，是所有食材兩兩之間最高的契合度。

數據范圍

對于 $40\%$ 的測試點，保證 $N\le 1,000$；

對于所有測試點，保證 $N\le 10^6$，$0\le a_i\le 2,147,483,647$。

提交鏈接

烹飪問題

思路分析

對于 $40\%$ 的測試點：

? 暴力算法（$100\%$ 的數據會超時）

枚舉所有 $(i,j)$ 組合，復雜度 $O(N^2)$，在 $n=10^6$ 時會超時

#include <bits/stdc++.h>
using namespace std;int n, a[1000009];int main()
{cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];int mx_and = 0;for (int i = 1; i <= n; i++)for (int j = i + 1; j <= n; j++)mx_and = max(mx_and, a[i] & a[j]);cout << mx_and;return 0;
}

對于 $100\%$ 的測試點：

思路1：

AND 運算結果的大與小由高位決定：高位為 $1$ 越多，結果越大。我們從高位往低位貪心，希望兩個數在高位盡可能都為 $1$。

我們可以：

1. 遍歷 $31～0$ 位（因為數據范圍不超過 $2^{31}?1$）

2. 每次篩出當前位為 $1$ 的數集合

3. 如果這集合里數量 $\ge 2$，就只保留它們繼續往低位考慮

4. 最終從這些數中找一組最大 AND 值

主邏輯

int mx_and = 0;
for(int pos = 31; pos >= 0; pos--) {int num = check_and(1, n, pos);if(num >= 2) {mx_and |= (1 << pos);n = num;}
}

從最高位 $31$ 遞減到最低位 $0$，逐位處理：for(int pos = 31; pos >= 0; pos--)

每次調用 check_and 將數組按照該位是否為 $1$ 重新劃分：int num = check_and(1, n, pos);

如果劃分后，第 $pos$ 位為 $1$ 的數不少于 $2$ 個，則將該位保留在答案中，同時更新數組范圍只保留這部分數，繼續判斷下一位，如果不足兩個數，則該位不能保留。

if(num >= 2) 
{mx_and |= (1 << pos);n = num;
}

關鍵函數解析：check_and

int check_and(int l, int r, int bit) 
{int i = l, j = r;while (i <= j) {// 左指針跳過第 bit 位為 1 的數while (i <= j && ((a[i] >> bit) & 1)) i++;// 右指針跳過第 bit 位為 0 的數while (i <= j && !((a[j] >> bit) & 1)) j--;if (i < j) swap(a[i++], a[j--]);}return j;
}

該函數將數組 $[l..r]$ 中的元素根據第 $bit$ 位分為兩部分：

• 左半部分是第 $bit$ 位為 $1$ 的數。

• 右半部分是第 $bit$ 位為 $0$ 的數。

返回值 $j$ 表示第 $bit$ 位為 $1$ 的數所在區間的最后一個位置。

完整代碼

#include<bits/stdc++.h>
using namespace std;int n , a[1000009];int check_and(int i , int j , int bit)
{while(i <= j){while(i <= j && a[i] >> bit & 1) i++;while(i <= j && !(a[j] >> bit & 1))j--;if(i <= j)	swap(a[i++] , a[j--]);}return j;
}
int main()
{cin >> n;for(int i = 1; i <= n; i++)cin >> a[i];int mx_and = 0;for(int pos = 31; pos >= 0; pos--){int num = check_and(1 , n , pos);if(num >= 2){mx_and |= 1 << pos;n = num;}}cout << mx_and;return 0;
}

思路2：

從數組中取出最大的 $32$ 個數，然后在它們之間暴力兩兩組合，求最大 a[i] & a[j]

1. AND 的值由高位影響最大

   因為 AND 運算中，只有兩個數該位都是 $1$，結果才是 $1$，所以想讓結果最大，就要讓兩個數在高位盡量都是 $1$。高位相同的數才更容易 AND 出更大的數。

2. 越大的數，高位 $1$ 越可能多

   數值大的數，二進制中左側（高位）出現 $1$ 的概率更高，所以最大 AND 通常出現在“比較大的兩個數”之間。

3. 最多 $32$ 個不同高位組合

   因為 $int$ 是 $32$ 位，最多有 $32$ 個不同的“最高位為 $1$”的模式，所以只取最大 $32$ 個數，就等于把每一種高位代表的結構都涵蓋了。

參考代碼

#include<bits/stdc++.h>
using namespace std;int n , a[1000009];int main()
{cin >> n;for(int i = 1; i <= n; i++)cin >> a[i];sort(a + 1 , a + n + 1 , greater<int>());n = min(n , 32);int mx_and = 0;for(int i = 1; i <= n; i++)for(int j = i + 1; j <= n; j++)mx_and = max(mx_and , a[i] & a[j]);cout << mx_and;return 0;
}