历经过世界盛大 / 却留恋这年华
题解
给定一个非负整数 $n$，你需要把 $0, 1, 2, \dots, n$ 划分成若干组，满足每一组的按位与为 $0$。划分的组不需要相邻。你需要最大化划分组数并给出方案。
$T$ 组测试数据，$1 \le T \le 600,0 \le n \le 10^5,\sum n \le 2 \times 10^5,1.0\rm{s},512\rm{MiB}$。
事实上，答案始终为 $\lceil\frac{n+1}{2}\rceil$。下面，我们通过递归式的构造来证明这一点。
我们令 $A(x)$ 表示当 $n=x$ 时的答案。令 $k=\min{i|2^i-1\ge x}$。我们可以让所有满足 $2^{k-1} \le y \le x$ 的正整数 $y$ 与 $2^k-1-y$ 匹配为一个组。这样，我们还剩下 $[0,2^k-x-1]$ 这些数未被分组，而这一步可以递归为 $A(2^k-x-1)$。这样，问题即被递归地解决了。时间复杂度为 $O\left(\sum n\right)$。