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<bits/stdc++.h>

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<v.val;}

void Insert(int u,int d,int x) {

	if(d<0) {mx[u]=x;return;}

	bool w=(a[x].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<<i),p=k&(1<<i);

		if(p) {if(go[u][w^1])u=go[u][w^1];else return res;}

		else {

			int t1=go[u][w^1];if(t1&&dp[mx[t1]]>dp[res])res=mx[t1];

			if(go[u][w])u=go[u][w];else return res;

		}

	}

	if(dp[res]<dp[mx[u]]) res=mx[u];

	return res;

}

int main() {

	int ans=0,pos;

	scanf("%d%d",&n,&k);

	for(int i=1;i<=n;i++) scanf("%d",&a[i].val),a[i].id=i;

	sort(a+1,a+1+n,cmp);

	for(int i=1;i<=n;i++) {

		pre[i]=Fd(a[i].val);dp[i]=dp[pre[i]]+1;

		Insert(0,29,i);

		if(dp[i]>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;

}

巴特西

CF1625D - Binary Spiders[trie树优化dp]

最新文章

热门文章