例題

P4310 絕世好題: 給定一個(gè)長(zhǎng)度為 \(n\) 的數(shù)列 \(a_i\)，求 \(a_i\) 的子序列 \(b_i\) 的最長(zhǎng)長(zhǎng)度 \(k\)，滿足 \(b_i \& b_{i-1} \ne 0\)，其中 \(2\leq i\leq k\)，& 表示位運(yùn)算取與。

這道題明顯是一個(gè)有關(guān)序列分割的動(dòng)態(tài)規(guī)劃題目。設(shè) \(f_i\) 表示前 \(i\) 項(xiàng)的最大長(zhǎng)度且 \(i\) 必選，那么 \(f_i=\max_{j。這樣樸素的動(dòng)態(tài)規(guī)劃轉(zhuǎn)移的時(shí)間復(fù)雜度是 \(O(n^2)\)，無法通過全部的測(cè)試點(diǎn)。

利用位運(yùn)算，我們可以不要枚舉上一個(gè)位置 \(j\)，而是枚舉二進(jìn)制下哪一位與 \(a_i\) 取與后為 \(1\)。

具體地，我們?cè)O(shè) \(g[i,p]\) 表示前 \(i\) 項(xiàng)最終第 \(p\) 位為 \(1\) 的最大長(zhǎng)度。則，我們可以枚舉所有 \(a_i\) 的二進(jìn)制為 \(1\) 的位置，即 \(f_i=\max\{g[i-1,p]\ |\ a_i\text{的第p位為1}\}\)。然后，對(duì)于 \(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)\)。

容易發(fā)現(xiàn)，\(g_i\) 數(shù)組的取值僅與 \(g_{i-1}\) 有關(guān)，因此可以通過滾動(dòng)數(shù)組的方式優(yōu)化空間。總的時(shí)間復(fù)雜度為 \(O(n\log \omega)\)，空間復(fù)雜度為 \(O(n+\log \omega)\)，其中 \(\omega\) 表示值域。

int n, a, f, g[2][31];
/*
f[i] 表示以 i 結(jié)尾的最長(zhǎng)子序列長(zhǎng)度
g[i, p]表示前 i項(xiàng)第p位為1的最大長(zhǎng)度
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
優(yōu)化：g[i, p]第一維滾動(dòng)
*/
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;
}

按位取與: 給定一個(gè)長(zhǎng)度為 \(n\) 的序列 \(a_i\)，請(qǐng)你求出 \(\max\{a_i\&a_j\}\)，其中 \(1\le i，\(a_i\le 10^{18}\)。

本題暴力的復(fù)雜度為 \(O(n^2)\)，顯然無法通過。此時(shí)，我們需要利用按位貪心的思想。按位貪心是指從高位到低位遍歷，優(yōu)先使得高位為 \(1\)，只有高位無法為 \(1\) 時(shí)才使這一位為 \(0\)，并繼續(xù)按此法則考慮下一位。其正確性證明如下：

假設(shè)目前考慮最高位為第 \(k\) 位，當(dāng)?shù)?\(k\) 位為 \(1\) 而后 \(k-1\) 位均為 \(0\) 時(shí)，收益為 \(2^k\)；當(dāng)?shù)?\(k\) 位為 \(0\) 而后 \(k-1\) 位均為 \(1\) 時(shí)，收益為 \(2^{k-1}+2^{k-2}+\cdots+2^0\)。利用等比數(shù)列求和公式可得，后者等于 \(2^k-1<2^k\)，因此高位為 \(1\) 更優(yōu)。

對(duì)于本題，由于每一位之間的計(jì)算互相獨(dú)立，可以從高到低按位貪心。假設(shè)目前訪問到第 \(p\) 位，如果第 \(p\) 位為 \(1\) 的數(shù)的個(gè)數(shù) \(\ge 2\)，那么最終答案里該位為 \(1\)。此時(shí)，所有第 \(p\) 位為 \(0\) 的數(shù)都不再參與后續(xù)的計(jì)算。因此，我們可以用兩個(gè)動(dòng)態(tài)數(shù)組 vector 存儲(chǔ)當(dāng)前輪合法的數(shù)和下一輪合法的數(shù)，并用滾動(dòng)數(shù)組的方式傳遞；若數(shù)組大小 \(\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;
}