题解 CF1625D 【Binary Spiders】（贪心，trie，dp）

提供一个感觉比较优美的做法（不需要分类讨论）。

我们发现将这些数看成二进制数字符串后，\(\operatorname{xor}\) 和 lcp 是很相似的；那么类比 sa 关于后缀之间的 lcp 的那个结论，我们可以发现，将这些数按字典序排序后得到 \(a\) 序列，那么 \(a\) 的一个子序列 \(b\) 中的元素两两异或的最小值为 \(\min_i\{b_i\operatorname{xor} b_{i+1} \}\)。

证明：必要性显然，证一下充分性：假设存在 \(i+1 （相反情况同理）使得 \(b_i\operatorname{xor}b_j，那么一定存在一个二进制位 \(k\)，使得任意 \(k^{\prime}>k\) 满足 \(b_{j,k^{\prime}}=b_{i+1,k^{\prime}}\) 且 \(b_{i,k}=b_{j,k}\ne b_{i+1,k}\) ，又因为 \(b_{i} 可得 \(b_{i,k}=b_{j,k}=0,b_{i+1,k}=1\)；这样以来又可得 \(b_{i+1}>b_{j}\)，与假设 \(i+1 矛盾，得证。

那么我们就有了一个简单的做法，将给出的序列按二进制表示下字典序（其实就等于按数值大小）排序得到 \(a\) 序列，设 \(f_i\) 表示强制选 \(i\) 时从区间 \([1,i]\) 最多能选几个数，转移方程为 \(f_i=\max_{j。

直接做是 \(O(n^2)\) 的，放在字典树上，设 \(g_x= \max_{y\in subtree(x),y\texttt{ is a leaf}}\{f_y\}\)，插入时暴力维护，转移时从上向下遍历，设当前在第 \(j\) 位 \(x\) 节点，若 \(k_j=0\)，说明此时 \(subtree(son_{x,b_i\operatorname{xor}1})\) 中所有数都是可以选的，令 \(f_i=\max\{f_i,g_{son_{x,b_i\operatorname{xor}1}}+1\}\)，然后进入 \(son_{x,b_i}\) 继续处理；否则只能进入 \(son_{x,b_i\operatorname{xor}1}\)。

时间复杂度为 \(O(n\log v)\)，\(v\) 为值域。

代码：

#include
using namespace std;
#define rg register
#define ll long long
#define ull unsigned ll
#define inf 0x3f3f3f3f
#define lowbit(x) (x&(-x))
#define eps 1e-8
const double alpha=0.73;
inline void file(){
	freopen("baka.in","r",stdin);
	freopen("baka.ans","w",stdout);
}
char buf[1<<21],*p1=buf,*p2=buf;
inline int getc(){
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
	rg int ret=0,f=0;char ch=getc();
    while(!isdigit(ch)){if(ch==EOF)exit(0);if(ch=='-')f=1;ch=getc();}
    while(isdigit(ch)){ret=ret*10+ch-48;ch=getc();}
    return f?-ret:ret;
}
struct num{ 
	int id,v; 
	num(int id=0,int v=0):id(id),v(v) {} 
	bool operator<(const num& tmp)const{ return v^tmp.v?v>i)&1),to=((v>>i)&1);
		if(!chk) f[id]=max(f[id],g[son[u][to^1]]);
		u=son[u][to^chk];
	}
	if(u) f[id]=max(f[id],g[u]);
	++f[id].v;
}
inline void insert(int x){
	const int v=a[x].v,id=a[x].id; int u=1;
	const num fid=num(id,f[id].v);
	for(rg int i=30;~i;--i){
		const bool to=((v>>i)&1);
		if(!son[u][to]) son[u][to]=++cntt;
		g[u]=max(g[u],fid);
		u=son[u][to];
	}
	g[u]=max(g[u],fid);
}
signed main(){
    //file();
   	n=read(),k=read();
   	for(rg int i=1,x;i<=n;++i) x=read(),a[i]=num(i,x);
	sort(a+1,a+1+n);
	for(rg int i=1;i<=n;++i) update(i),insert(i);
	int x=g[1].id;
	if(f[x].v==1) return 0*puts("-1");
	printf("%d\n",f[x].v);
	while(x) printf("%d ",x),x=f[x].id;
	return 0;
}
/*
10 10
18 2 6 17 7 19 17 6 2 12 14
4 15 5 20 2 6 20 12 16 5
*/