当前位置: 代码迷 >> 综合 >> 字典树合并 ifrog1028 Bob and Alice are playing numbers
  详细解决方案

字典树合并 ifrog1028 Bob and Alice are playing numbers

热度:45   发布时间:2023-12-14 03:07:10.0

传送门:点击打开链接

题意:有3种运算符,选择两个数使用这种运算符,使得最后的答案最大。

思路:xor的我们已经很熟练了,我们来讨论&和|

&的话,如果1的个数>=2,那么我们就走1,否则,就把字典树的01合并,因为此时01的答案是一样的。

|的话,我们需要先做一个预处理。把对于每一个节点,其1所对应的字典树复制到0所对应的字典树上去。

这一步可以用DFS搞定,复杂度是T(n)=T(n/2)+n,所以总复杂度是MAX*logMAX,max等于1e6,所以可以接受

之后,我再去枚举其中一个。对于第i位,如果是1,那么我字典树就走0,如果是0,那么我字典树就走1.

因为字典树0的里面也包括了为1的值了,现在

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <bitset>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#inclu