# Find Max AND / XOR of a Pair in Array (2022.1.14)
###### tags: `競程筆記` `CompetitiveProgramming`
## AND
### 想法
先分bit由大到小看，如果這個bit有兩個人以上，那就加到答案裡面。沒有這個bit的人就踢掉（以後不再看他）。
:::spoiler Code
```cpp=
int arr[100005], out[100005]; //出局
signed main(){
int n;cin>>n;
for (int i=1;i<=n;i++) cin>>arr[i];
int ans = 0;
for (int k=30;k>=0;k--){
int cnt = 0;
for (int i=1;i<=n;i++) if (!out[i]){
if (arr[i] & (1<<k)) cnt++;
}
if (cnt>=2){
ans += (1<<k);
for (int i=1;i<=n;i++) if (!(arr[i] & (1<<k))) out[i] = true;
}
}
cout<<ans<<endl;
}
```
:::
## XOR
喵了一眼網路上的做法，大多都是trie或神奇的超短東西
### 我的神奇做法
先舉例：1 4 5 6 12 13 輸出：13
首先一樣從大的bit開始看。根據xor的性質，要在答案中產生這個bit，需要有一個「有這個bit的數」和「沒這個bit的數」取xor。所以我們把數分成兩組。要記得先把重複的數字拿掉喔
| 8✓ | 8x |
| ----- | ------- |
| 12 13 | 1 4 5 6 |
最佳答案一定是左邊某個數xor右邊某個數。
---
接著，我們看下一個bit。一樣再把左邊分成兩組，右邊分成兩組。
<table>
<thead>
<tr>
<th colspan=2>8✓</th>
<th colspan=2>8x</th>
</tr>
</thead>
<tbody>
<tr>
<th rowspan=1>4✓ (A組)</th>
<th rowspan=1>4x (B組)</th>
<th rowspan=1>4✓ (C組)</th>
<th rowspan=1>4x (D組)</th>
</tr>
<tr>
</tr>
<tr>
<td rowspan=1>12 13</td>
<td rowspan=1> </td>
<td rowspan=1>4 5 6</td>
<td rowspan=1>1</td>
</tr>
</table>
最佳答案(目前是8+4=12以上)一定是 「A配D」 或是 「B配C」兩者中較大的那個。所以我們就可以一直遞迴下去，找到最佳答案！以以上這個情形為例，答案一定是A和D，因為B和C其中一個為空。（成功剪枝）
---
<table>
<thead>
<tr>
<th colspan=2>4✓</th>
<th colspan=2>4x</th>
</tr>
</thead>
<tbody>
<tr>
<th rowspan=1>2✓ (A組)</th>
<th rowspan=1>2x (B組)</th>
<th rowspan=1>2✓ (C組)</th>
<th rowspan=1>2x (D組)</th>
</tr>
<tr>
</tr>
<tr>
<td rowspan=1> </td>
<td rowspan=1>12 13</td>
<td rowspan=1> </td>
<td rowspan=1>1</td>
</tr>
</table>
挖...「A和D」和「B和C」都湊不出來...怎麼辦？
用2這個bit沒辦法區分成兩組，我們只好捨棄這個bit了。但是下一個bit可能還有機會！把2的分組打回原形，再用1試試看！
---
<table>
<thead>
<tr>
<th colspan=2>4✓</th>
<th colspan=2>4x</th>
</tr>
</thead>
<tbody>
<tr>
<th rowspan=1>1✓ (A組)</th>
<th rowspan=1>1x (B組)</th>
<th rowspan=1>1✓ (C組)</th>
<th rowspan=1>1x (D組)</th>
</tr>
<tr>
</tr>
<tr>
<td rowspan=1>13</td>
<td rowspan=1>12</td>
<td rowspan=1>1 </td>
<td rowspan=1> </td>
</tr>
</table>
有了！這時候我們就能快樂的 return $~12 ~xor~ 1$ 了！
---
#### 一開始怎麼辦？
一開始我們還不知道最大的數是由哪個bit開始的...
<table>
<thead>
<tr>
<th colspan=2>16✓</th>
<th colspan=2>16x</th>
</tr>
</thead>
<tbody>
<tr>
<th rowspan=1>8✓ (A組)</th>
<th rowspan=1>8x (B組)</th>
<th rowspan=1>8✓ (C組)</th>
<th rowspan=1>8x (D組)</th>
</tr>
<tr>
</tr>
<tr>
<td rowspan=1> </td>
<td rowspan=1> </td>
<td rowspan=1>12 13 </td>
<td rowspan=1>1 4 5 6 </td>
</tr>
</table>
顯然醬就是捨棄A組和B組，用 C D 遞迴下去。
<table>
<thead>
<tr>
<th colspan=2>16✓</th>
<th colspan=2>16x</th>
</tr>
</thead>
<tbody>
<tr>
<th rowspan=1>8✓ (A組)</th>
<th rowspan=1>8x (B組)</th>
<th rowspan=1>8✓ (C組)</th>
<th rowspan=1>8x (D組)</th>
</tr>
<tr>
</tr>
<tr>
<td rowspan=1>24 25 26 </td>
<td rowspan=1>16 18 </td>
<td rowspan=1> </td>
<td rowspan=1> </td>
</tr>
</table>
同理，如果只有A B兩組非空，就用 A B 遞迴下去。
---
#### 會不會看到1這個bit時，還有一組大小超過1？
不會，因為每一組都代表在那個bit有不一樣的0或1。如果有以上這個情況發生，那一定是數個相同的數字。
---
#### 這樣複雜度是多少？
我們的遞迴有 $log(a_i)$ 層，在每一層，每個數字都會被恰看過一次。所以時間和空間複雜度都是 $O(nlog(a_i))$。（只是這個實作方法常數有點大就是了）
---
:::spoiler LeetCode AC
```cpp=
class Solution {
public:
int arr[200005] ;
int f(int k,vector<int> L,vector<int> R){
if (L.empty() && R.empty()) return 0;
if (L.size()==1 && R.size()==1) return L[0] ^ R[0];
if (k<=0) return 0;
vector<int> a,b,c,d;
for (int u:L) if (u & (1<<(k-1))) a.push_back(u); else b.push_back(u);
for (int u:R) if (u & (1<<(k-1))) c.push_back(u); else d.push_back(u);
if (a.empty() && b.empty()) return f(k-1,c,d);
else if (c.empty() && d.empty()) return f(k-1,a,b);
else if (a.size() && b.size() && c.size() && d.size()){
return max(f(k-1,a,d),f(k-1,c,b));
}else if ( (a.empty() || d.empty()) && (c.empty() || b.empty()) ){
return f(k-1,L,R); // ?
}else if ((a.empty() || d.empty())){
return f(k-1,c,b);
}else {
return f(k-1,a,d);
}
}
int findMaximumXOR(vector<int>& nums) {
sort(nums.begin(),nums.end());
nums.erase(unique(nums.begin(),nums.end()),nums.end());
int maxn;
int n = nums.size();
for (int i=1;i<=n;i++) {
arr[i] = nums[i-1];
maxn = max(maxn,arr[i]);
}
vector<int> v,e;
for (int i=1;i<=n;i++) v.push_back(arr[i]);
int res = f(31,e,v);
return res;
}
};
```
:::
:::spoiler Full Code
```cpp=
// Cookie197
// the people who invented competitive programmin must be ******* crazy
// why am i still here suffering while i can do something else more valuable?
// WHY???
#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<iomanip>
#include<math.h>
#include<unordered_map>
#include<numeric>
#include<random>
using namespace std;
#define Why_does_competitive_programming_even_exist ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
#define pii pair<ll,ll>
#define pdd pair<double ,double>
#define mp make_pair
#define mod 998244353
#define endl "\n"
#define inf 1e9
int arr[200005] ;
int f(int k,vector<int> L,vector<int> R){
//cout<<"#"<<k<<" ";
//for (int u:L) cout<<u<<" ";
//cout<<" ";
//for (int u:R) cout<<u<<" ";
//cout<<endl;
if (L.empty() && R.empty()) return 0;
if (L.size()==1 && R.size()==1) return L[0] ^ R[0];
if (k<=0) return 0;
vector<int> a,b,c,d;
for (int u:L) if (u & (1<<(k-1))) a.push_back(u); else b.push_back(u);
for (int u:R) if (u & (1<<(k-1))) c.push_back(u); else d.push_back(u);
if (a.empty() && b.empty()) return f(k-1,c,d);
else if (c.empty() && d.empty()) return f(k-1,a,b);
else if (a.size() && b.size() && c.size() && d.size()){
return max(f(k-1,a,d),f(k-1,c,b));
}else if ( (a.empty() || d.empty()) && (c.empty() || b.empty()) ){
return f(k-1,L,R);
}else if ((a.empty() || d.empty())){
return f(k-1,c,b);
}else {
return f(k-1,a,d);
}
}
int maxn;
signed main(){
int n;cin>>n;
for (int i=1;i<=n;i++){
cin>>arr[i]; maxn = max(maxn,arr[i]);
}
// you should remove dulplicates first
vector<int> v,e;
for (int i=1;i<=n;i++) v.push_back(arr[i]);
int b = 0; while((1<<b)<=maxn) b++;
int res = f(b,e,v);
cout<<"ans=";
cout<<res<<endl;
}
```
:::
## 延伸題 [CF 1625D Binary Spiders](https://codeforces.com/contest/1625/problem/D)
### 重要觀察
想要很多個數字的xor大於k，要先看「比k大的bit」
以k=5 (101) 為例，我們依照8以上的bit們的不同，來對陣列的數字進行分組。
:::spoiler Code
```cpp=
// Cookie197
// the people who invented competitive programmin must be ******* crazy
// why am i still here suffering while i can do something else more valuable?
// WHY???
#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<iomanip>
#include<math.h>
#include<unordered_map>
#include<numeric>
#include<random>
using namespace std;
#define Why_does_competitive_programming_even_exist ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
#define pii pair<ll,ll>
#define pdd pair<double ,double>
#define mp make_pair
#define mod 998244353
#define endl "\n"
#define inf 1e9
int arr[300005] ;
vector<vector<int> > group;
map<int,int> pos;
pair<int,pii> z = mp(0,mp(0,0));
pair<int,pii> f(int k,vector<int> L,vector<int> R){
if (L.empty() && R.empty()) return z;
if (L.size()==1 && R.size()==1) return mp(L[0] ^ R[0],mp(pos[L[0]],pos[R[0]]));
if (k<=0) return z;
vector<int> a,b,c,d;
for (int u:L) if (u & (1<<(k-1))) a.push_back(u); else b.push_back(u);
for (int u:R) if (u & (1<<(k-1))) c.push_back(u); else d.push_back(u);
if (a.empty() && b.empty()) return f(k-1,c,d);
else if (c.empty() && d.empty()) return f(k-1,a,b);
else if (a.size() && b.size() && c.size() && d.size()){
return max(f(k-1,a,d),f(k-1,c,b));
}else if ( (a.empty() || d.empty()) && (c.empty() || b.empty()) ){
return f(k-1,L,R);
}else if ((a.empty() || d.empty())){
return f(k-1,c,b);
}else {
return f(k-1,a,d);
}
}
pair<int,pii> max_xor(vector<int> v){
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
vector<int> e;
return f(31,e,v);
}
int maxn;
vector<int> Ans;
map<int,int> m;
signed main(){
Why_does_competitive_programming_even_exist;
int n,k;cin>>n>>k;
int tmp = k, lim = 0;
while(tmp){
tmp >>= 1;
lim++;
}
int cnt = 0;
for (int i=1;i<=n;i++){
cin>>arr[i];
pos[arr[i]] = i;
if (m.count(arr[i]>>lim)){
group[ m[(arr[i]>>lim)] ] .push_back(arr[i]);
}
else {
vector<int> e;
group.push_back(e);
m[(arr[i]>>lim)] = cnt;
group[cnt].push_back(arr[i]);
cnt++;
}
}
if (k==0){
cout<<n<<endl;
for (int i=1;i<=n;i++) cout<<i<<" ";
cout<<endl; return 0;
}
int ans = 0;
for (int u=0;u<group.size();u++){
if (group[u].size()==1) {
ans++;
Ans.push_back(pos[group[u][0]]);
}
else {
pair<int,pii> p = max_xor(group[u]);
if (p.first >= k) {
ans+=2;
Ans.push_back(p.second.first);
Ans.push_back(p.second.second);
}else{
ans++; Ans.push_back(pos[group[u][0]]);
}
}
}
if (ans<2) {
cout<<-1<<endl;
return 0;
}
cout<<ans<<endl;
for (int u:Ans) cout<<u<<" ";
cout<<endl;
}
```
:::
Sign in with Wallet
Connect another wallet