AC代碼

https://codeforces.com/contest/1720/submission/177381464

題意：

Subsequence b=[b0,b1,…,bm?1] of length m is called beautiful, if the following condition holds:

For any p (0≤p<m?1) holds: abp⊕bp+1<abp+1⊕bp.

題解：

令dp_i為以第i個數(shù)a_i結(jié)尾的最長的子序列長度

a_j ^ i < a_i ^ j, j<i, 此時我們在二進(jìn)制的情況下觀察這個不等式,

發(fā)現(xiàn)從最高位開始,將會出現(xiàn)第一個位置是a_j ^ i != a_i ^ j的,

假設(shè)為第k位，由于是小于號,所以在這個位上,a_j ^ i是0,a_i ^ j是1.

所以，j=a_i ^1, 且0=a_i ^ j ^ 1 = a_j ^ i，即是a_i ^ i ^ 1 = a_j ^ j

在第k位之前,a_j ^ i = a_i ^ j,此時移個項,a_j ^ j = a_i ^ i.

使用Trie字典樹，tr[p][0/1]用于存儲a_i ^ i的bit串

f[p][0/1]表示在這個p節(jié)點上j的取值為0 或1 時的最長子序列長度。

使用Trie字典樹，查找a_j ^ j = a_i ^ i第一次不成立的第k位，而且滿足條件：

j=a_i ^1, 且 a_i ^ i ^ 1 = a_j ^ j

此時即可以更新f[p][0/1]，f[p][0/1]的最大值即是答案。