HDU-5536 Chip Factory （字典树）-白红宇

HDU-5536 Chip Factory （字典树）

阅读量：4657 次

发布时间：2019-06-09

本文共 1295 字，大约阅读时间需要 4 分钟。

题目大意：给n个数，编号为1~n，取三个编号不同的数，使表达式(a+b)^c的值最大。

题目分析：将这n个数按二进制位建立一棵trie。枚举i、j的和，查询亦或最大值，但在查询之前要把i、j在trie中删除，查询完毕后再插入trie。

ps：用数组实现trie会超时，因为每次test case之前都要初始化数组，非常耗时。

代码如下：

# include
     
      # include
      
       # include
       
        # include
        
         # include
         
          # include
          
           # include
           # include
            
             # include
             
              # include
              
               using namespace std;# define LL long longconst int N=1000;const int INF=1000000000;const double inf=1e20;struct Node{ int cnt; Node *son[2]; Node(){ cnt=0; son[0]=son[1]=NULL; }};Node *root;int a[N+5];int n;void update(int x){ Node *p=root; for(int i=30;i>=0;--i){ int k=(x&(1<
               
                0?1:0; if(p->son[k]==NULL) p->son[k]=new Node(); ++(p->son[k]->cnt); p=p->son[k]; }}void erase(LL x){ Node *p=root; for(int i=30;i>=0;--i){ int k=(x&(1<
                
                 0?1:0; --(p->son[k]->cnt); p=p->son[k]; }}int query(int x){ int res=0; Node *p=root; for(int i=30;i>=0;--i){ int k=(x&(1<
                 
                  0?1:0; if(p->son[k^1]!=NULL&&p->son[k^1]->cnt>0){ res|=(1<
                  
                   son[k^1]; }else{ p=p->son[k]; } } return res;}void delTree(Node *p){ if(p==NULL) return ; delTree(p->son[0]); delTree(p->son[1]); delete p;}int main(){ int T; scanf("%d",&T); while(T--) { scanf("%d",&n); root=new Node(); for(int i=0;i