位运算

例题

P4310 绝世好题: 给定一个长度为 \(n\) 的数列 \(a_i\)，求 \(a_i\) 的子序列 \(b_i\) 的最长长度 \(k\)，满足 \(b_i \& b_{i-1} \ne 0\)，其中 \(2\leq i\leq k\)，& 表示位运算取与。

这道题明显是一个有关序列分割的动态规划题目。设 \(f_i\) 表示前 \(i\) 项的最大长度且 \(i\) 必选，那么 \(f_i=\max_{j。这样朴素的动态规划转移的时间复杂度是 \(O(n^2)\)，无法通过全部的测试点。

利用位运算，我们可以不要枚举上一个位置 \(j\)，而是枚举二进制下哪一位与 \(a_i\) 取与后为 \(1\)。

具体地，我们设 \(g[i,p]\) 表示前 \(i\) 项最终第 \(p\) 位为 \(1\) 的最大长度。则，我们可以枚举所有 \(a_i\) 的二进制为 \(1\) 的位置，即 \(f_i=\max\{g[i-1,p]\ |\ a_i\text{的第p位为1}\}\)。然后，对于 \(g[i,p]\)，若 \(a_i\) 的第 \(p\) 位为 \(0\)，那么 \(g[i,p]\leftarrow g[i-1,p]\)，否则 \(g[i,p]\leftarrow \max(g[i-1,p],f_i)\)。

容易发现，\(g_i\) 数组的取值仅与 \(g_{i-1}\) 有关，因此可以通过滚动数组的方式优化空间。总的时间复杂度为 \(O(n\log \omega)\)，空间复杂度为 \(O(n+\log \omega)\)，其中 \(\omega\) 表示值域。

int n, a, f, g[2][31];
/*
f[i] 表示以 i 结尾的最长子序列长度
g[i, p]表示前 i项第p位为1的最大长度
f[i] = max{g[i-1, p] | a[i]第p位为1} + 1
g[i, p] = 
	max(g[i-1, p], f[i]), a[i]第p位为1
	g[i-1, p], a[i]->p = 0
优化：g[i, p]第一维滚动
*/
int main () {
	int ans = 0;
	read(n);
	rep(i, 1, n) {
		read(a);
		f = 1;
		rep(p, 0, 30)
			if((a >> p) & 1) 
				f = max(f, g[(i - 1) & 1][p] + 1);
		rep(p, 0, 30)
			if((a >> p) & 1)
				g[i & 1][p] = max(g[(i - 1) & 1][p], f);
			else g[i & 1][p] = g[(i - 1) & 1][p];
		ans = max(ans, f);
	}
	writeln(ans);
	return 0;
}

按位取与: 给定一个长度为 \(n\) 的序列 \(a_i\)，请你求出 \(\max\{a_i\&a_j\}\)，其中 \(1\le i，\(a_i\le 10^{18}\)。

本题暴力的复杂度为 \(O(n^2)\)，显然无法通过。此时，我们需要利用按位贪心的思想。按位贪心是指从高位到低位遍历，优先使得高位为 \(1\)，只有高位无法为 \(1\) 时才使这一位为 \(0\)，并继续按此法则考虑下一位。其正确性证明如下：

假设目前考虑最高位为第 \(k\) 位，当第 \(k\) 位为 \(1\) 而后 \(k-1\) 位均为 \(0\) 时，收益为 \(2^k\)；当第 \(k\) 位为 \(0\) 而后 \(k-1\) 位均为 \(1\) 时，收益为 \(2^{k-1}+2^{k-2}+\cdots+2^0\)。利用等比数列求和公式可得，后者等于 \(2^k-1<2^k\)，因此高位为 \(1\) 更优。

对于本题，由于每一位之间的计算互相独立，可以从高到低按位贪心。假设目前访问到第 \(p\) 位，如果第 \(p\) 位为 \(1\) 的数的个数 \(\ge 2\)，那么最终答案里该位为 \(1\)。此时，所有第 \(p\) 位为 \(0\) 的数都不再参与后续的计算。因此，我们可以用两个动态数组 vector 存储当前轮合法的数和下一轮合法的数，并用滚动数组的方式传递；若数组大小 \(\ge 2\) 则将 \(ans\) 的第 \(p\) 位置为 \(1\)（ans |= (1ll<）。

ll n, a[maxn], ans, now;
vector  id[2];
int main () {
	read(n);
	rep(i, 1, n) read(a[i]), id[0].push_back(i);
	Rep(p, 30, 0) {
		ll nxt = (now ^ 1);
		id[nxt].clear();
		for(unsigned int i = 0; i < id[now].size(); i++) {
			int u = id[now][i];
			if((1ll << p) & a[u]) 
				id[nxt].push_back(u);
		}
		if(id[nxt].size() < 2) continue;
		ans |= (1ll << p);
		now = nxt;
	}
	writeln(ans);
	return 0;
}