题意:

在[0,2n)区间内任取一个数X,依次异或m个本区间内的数,并在某次异或之前或之后做一次f操作,即将当前的X循环左移(在n位的范围内)。求选择哪个数可以使在不同时候异或的答案的最小值最大。

分析:

首先,题目可以转化为:X异或这m个数中的前k个和循环右移1位后的(m-k)个数后的最小值最大。根据k的取值不同,我们可以得到(m+1)个不同的这样的异或方案。根据异或的交换律和结合律,这(m+1)个方案就相当于那m个数异或后的数与X异或。即$X\oplus A\oplus B\oplus C=X\oplus(A\oplus B\oplus C)$,所以我们将题目转化为:求{X与(m+1)个数中的某一个异或后结果的最小值}max

很自然地想到:策略1:如果X的某一位无论异或(m+1)个数中的哪一个,那一位都不变,我们就尽量让这一位异或之后为1。
我们继续分析:策略2:如果X的某一位异或不同的数,结果都不同,那么这时我们就需要使后续位异或结果尽量大(即尽量多遇到策略一)。
因此,这种只跟后续状态有关的问题,我们应该用DP解决,而0和1的状态分布又神似二叉树,所以我们可以尝试在trie树上DP

把那(m+1)个数放进trie树,较高位更靠近根节点,那么对于每一个X,我们都可以从trie数中找到一条路径使路径代表的值与X的异或值最小。比如X的最高位为1,而trie树的根节点有0和1两个子节点,那么我们的路径肯定会走向1这个子节点,从而获得更小的异或值。

那么如何求最小值的最大值呢?二分似乎是行不通的。结合开始分析时我们想到的两个策略,我们发现:

如果trie树的某个节点只有左子节点或右子节点,对应着策略1;两个节点都有的对应着策略2。在DP时我们就可以结合这两个策略,更新trie树每个节点对应应该选什么数字可以使往下的异或值最大。