CF1625D - Binary Spiders[trie树优化dp]

官方题解

• 题意：给数列a[]，选择尽量多的数满足任意两个异或起来<=k
  1625D - Binary Spiders
• 思路：首先，将数列排序得到，然后升序取得的值的任意两个最小值为相邻两个异或的最小值。
  证明：zxcv告诉我可以考虑在trie树上，dfs序等价于字典序，然后一个树与其lca最深（异或值最小）的叶子节点必是dfs序（字典序）最接近的,即相邻的，得证。
  这个结论非常有用！我们就可dp了。\(dp[i]=dp[j]+1\)满足\(a_i\ xor\ a_j>=k\)
  有了\(O(n^2)\)的，然后用上\(01trie树\)优化找与\(a_i\)异或值\(<=k\)。只需要\(O(30n)\)
  具体的（其实很好想：）
  k表示当前位K的值
  \(k=0\)：只能找异或起来等于0的走
  \(k=1\)：走异或为1的，然后用为0的子树更新\(dp[i]\)(这里我们要在trie树上维护子树的dp最大值)
  总之我们走的路径都表示该结果与k的前dep位相等。
• code:

#include
using namespace std;
const int N=3e5+5;
int go[N*31][2],mx[N*31],pre[N],dp[N],n,k,ncnt;
struct node {int val,id;}a[N];
bool cmp(node u,node v) {return u.val>d)&1;
	if(!go[u][w]) go[u][w]=++ncnt;
	Insert(go[u][w],d-1,x);
	if(go[u][w^1])mx[u]=(dp[mx[go[u][0]]]>dp[mx[go[u][1]]])?mx[go[u][0]]:mx[go[u][1]];
	else mx[u]=mx[go[u][w]];
}
int Fd(int x) {
	int u=0,res=0;
	for(int i=29;i>=0;i--) {
		bool w=x&(1<dp[res])res=mx[t1];
			if(go[u][w])u=go[u][w];else return res;
		}
	}
	if(dp[res]ans)ans=dp[i],pos=i;
//		printf("!%d %d\n",pre[i],dp[i]);
	}
	if(ans==1) printf("-1");
	else {
		printf("%d\n",ans);
		for(int t=pos;t;t=pre[t]) printf("%d ",a[t].id);
	}
	return 0;
}