UVa 12571

題目

http://domen111.github.io/UVa-Easy-Viewer/?12571

給定 $N$ 個數字 $x_1, x_2, \dots, x_N$，以及 $Q$ 筆詢問

每筆詢問會有一個數字 $a$，求 $a \texttt{ & } x_i$ 的最大值為多少

$$1 \leq N \leq 100000 \
1 \leq Q \leq 30000 \
0 \leq x_i \leq 10^9 \
0 \leq a < 230
$$

想法1

雖然說暴力地把每個數字都做 & 一次取最大值會太慢(沒錯，我在這題 TLE 了好幾次)

但是注意到 $a$ 的範圍都在 $230$ 以內，也就是說超過 $2^7$ 這個 bit 的部分都可以直接忽略掉

所以我們就只需要注意所有 $255 = 11111111_2$ 以內的部分即可

找出一開始 $N$ 個數字中所有在 $0$~$255$ 以內的部分記錄起來

接下來如果要詢問，我們只需要針對這 $256$ 個數字檢查是否有出現過，然後找出 & 後的最大值即可

如此一來我們就不需要掃過長度 $N$ 的序列，而只需要掃過長度 $256$ 的序列

Code

//By Koios1143
#include<iostream>
using namespace std;
int T, N, Q;
bool used[256];
int main(){
	cin>>T;
	while(T--){
		for(int i=0 ; i<256 ; i++){
			used[i] = false;
		}
		cin>>N>>Q;
		for(int i=0, n ; i<N ; i++){
			cin>>n;
			// 只記錄 255 以內的部分
			used[(n&255)] = true;
		}
		for(int i=0, q, ans=0 ; i<Q ; i++, ans=0){
			cin>>q;
			for(int j=0 ; j<256 ; j++){
				if(used[j]){
					// 出現過就找最大值
					ans = max(ans, (q & j));
				}
			}
			cout<<ans<<"\n";
		}
	}
	return 0;
}

時間複雜度分析

每筆測資輸入時間複雜度為 $O(N + Q)$

每筆測資找出 used 的時間複雜度為 $O(N)$

令 $M = 256$，每筆詢問時間複雜度為 $O(R)$

總時間複雜度為 $O(t(N + Q + QR))$

想法2

如果我們直接把整個序列掃過去時間太慢，可能的因素是重複檢查相同的數字

也就是說，有些數字有出現的 bit 可能被其他數字完全覆蓋，那麼我們就只需要找那些盡量多 bit 的做一次 & 運算，其效果等同跟這群數字都做一次 &

舉範例的例子來說，輸入的 $N$ 個數字為 $1, 2, 3$，轉換成二進位後
$$
1 = 01_2 \
2 = 10_2 \
3 = 11_2
$$

很顯然的，與其跟三個數字都做一次 &，倒不如只跟 $3$ 做一次 &，因為 $3$ 包含了 $1, 2$ 的所有 bit

那麼我們只要想辦法留下這種會覆蓋掉別人的數字即可

那麼要怎麼篩選呢?

我們可以枚舉每個尚未被篩除的數字跟其他數字做 | 運算，如果 $a | b = a$，那就表示 $b$ 的所有 bit 都被包含在 $a$ 裡面

這裡有個優化的想法

那些會被篩掉的數字必定都是被比她還大的數字篩掉的，畢竟大的數字在更高位會出現 $1$

那麼，一開始就把數字排序好，必定可以保證由大到小篩選不會漏篩，而且每次都可以從最後一個篩除的數字往下繼續篩

如此一來就不需要每次都跟全部數字篩看看了

最後只需要把篩出來的數字跟詢問做 & 找最大值即可

Code

//By Koios1143
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int t, n, m, arr[100010];
vector<int> res;
int main(){
	cin>>t;
	while(t--){
		res.clear();
		cin>>n>>m;
		for(int i=0 ; i<n ; i++){
			cin>>arr[i];
		}
		// 排序後來篩，可以明確知道下次要從哪個數字繼續篩，稍微加速所需時間
		// i 表示不篩除的數字編號; j 表示當前要篩選的數字編號
		sort(arr, arr+n);
		for(int i=n-1, j ; i>0 ; i=j){
			res.push_back(arr[i]);
			for(j=i-1 ; (arr[i] | arr[j]) == arr[i] ; j--){}
		}
		for(int i=0, q, ans ; i<m ; i++){
			cin>>q;
			ans=0;
			for(auto j: res){
				ans = max(ans, (q & j));
			}
			cout<<ans<<"\n";
		}
	}

	return 0;
}

---

複雜度我不太知道要怎麼估，但是至少在 UVa 上是比第一個想法快了 0.02 秒

---