T3

题意描述

给你一个非负整数 $n$，你需要把 $0, 1, 2, \dots, n$ 划分成若干组，满足每一组的按位与为 $0$。

你需要最大化划分组数并给出方案。

多组测试，$T\le 600,0\le n\le 10^5,\sum n\le 2\times 10^5$。

特殊性质：$n=2^k-1$。

解答

不一定比 T2 难。

考虑特殊性质，我们猜测此时的分组方式一定是尽量将对称的两个分一组。

具体的，我们将 $i$ 与 $n-i$ 分在一组，此时 $n-i=n\oplus i$，显然是可以满足要求的。

考虑一般情况，我们猜测和特殊性质一样，但是我们先找到一个最小的 $r=2^k-1$ 且 $r\ge n$。

然后我们把所有 $i,r-i(i,r-i\le n)$ 先两个分一组，接下来会剩下 $0\sim r-n-1$ 的问题。

这是一个子问题，我们可以归纳说明这个子问题是可解的。

然后考虑证明这个解最小。

其实也很简单，因为我们的方法会在 $n$ 为偶数时把 $0$ 单独分出来，此时其他的组的大小至少都要 $\ge 2$，那么此时分组最小。

$n$ 为奇数是同理的。

时间复杂度 $O(n)$。