数值最神秘的一集——字典树

· · 个人记录

T3

这道题是个很明显的01字典树。又有异或又要求最值的，不是01还是什么

其实一看，一个专注求最大，一个专注得最小。实则就是让最小异或值最大、让最大异或最小值最小。

如果是小蓝先手，为了取得最小的异或值，小乔的到的就一定是最小异或值。对于每个a[i]找与a[i]异或得到的最小值，我们对这些最小值求取max，那么第一问就完成了。

在使用字典树的时候，a[i]是可能找到自己的，那么最小值就一定会变成0了。我们不妨标记一下自己，维护vis[i]=true表示结点i被标记，不可使用。另外维护cnt[i]表示每个结点i被经过的次数，如果cnt[cur]==1，那么就说明结点cur只被a[i]自己经过

另外，对于所有字典树的题目，trie数组的取值是与输入字符总数决定的。异或的值可能会超出题目限定值（大约两倍左右，异或是不进位的加法），取极值时需要注意。

T4

这道题也是个明显的01字典树。

既然a[i]和k都不会超过10^6，那么x一定会在[0,2^{21}]之间，所以枚举x是不会超时的。我们可以将这n个数全部插入01字典树。当k和x都确定时，问题就转化为了找合法的a[i]，在字典树上可以按子树统计