可持久化01字典树 hdu5536

小鱼儿 2023-06-07 12:06 33阅读 0赞

**题目大意：**

在一个数组中找出 (s\[i\]+s\[j\])^s\[k\] 最大的值，其中 i、j、k 各不相同。

数据范围太小了 做法见代码：

#include<bits/stdc++.h>
    using namespace std;
    using ll =long long ;
    constexpr int M=1005;
    ll res,tot,t[M*33][2],val[M*33],num[M*33],a[M],T,n;
    
    void insert(ll x,ll rt=0){
        for(ll id,i=32;i>=0;i--){
            id=(x>>i)&1;
            if(!t[rt][id]) t[rt][id]=++tot;
            rt=t[rt][id];
            num[rt]++;
        }
        val[rt]=x;
    }
    void update(ll x,ll ad,ll rt=0){
        for(ll id,i=32;i>=0;i--){
            id=(x>>i)&1;
            rt=t[rt][id];
            num[rt]+=ad;
        }
    }
    ll ask(ll x,ll rt=0){
        for(ll id,i=32;i>=0;i--){
            id=(x>>i)&1;
            if( t[rt][id^1] && num[t[rt][id^1]] )rt=t[rt][id^1];
            else rt=t[rt][id];
        }
        return x^val[rt];
    }
    
    int main(){
        scanf("%lld",&T);
        while(T--){
            for(register int i=0;i<32000;i++)
                t[i][0]=t[i][1]=num[i]=val[i]=0;
            res=tot=0;
            scanf("%lld",&n);
            for(ll i=1;i<=n;i++) scanf("%lld",&a[i]),insert(a[i]);
    
            for(ll i=1;i<=n;i++){
                for(ll j=1;j<=n;j++){
                    if(i==j)continue;
                    update(a[i],-1);update(a[j],-1);
                    res=max(res,ask(a[i]+a[j]));
                    update(a[i],1);update(a[j],1);
                }
            }
            printf("%lld\n",res);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，33人围观）

还没有评论，来说两句吧...

相关阅读

相关【学习】可持久化线段树（主席树）

可持久化数据结构是为了保存这个数据结构的所有历史版本 -------------------- 正文这是一棵非常好看的线段树 ![1658269-20190712

我就是我/ 2023年08月17日 16:49/ 0 赞/ 146 阅读

相关可持久化01字典树 hdu5536

题目大意：在一个数组中找出 (s\[i\]+s\[j\])^s\[k\] 最大的值，其中 i、j、k 各不相同。数据范围太小了做法见代码： inclu

小鱼儿/ 2023年06月07日 12:06/ 0 赞/ 34 阅读

相关 HDU 1251(字典树)

题意：如题。 include <iostream> include <string> include <cstring> incl

以你之姓@/ 2022年09月20日 12:35/ 0 赞/ 200 阅读

相关 hdu 1247 字典树

给定一系列的单词，少于50000个，输出这些单词中由两个出现过的单词组成的单词。开始用gets输入，无限wrong！猜测可能数据中有空行。换了scanf就AC了。

拼搏现实的明天。/ 2022年08月05日 11:19/ 0 赞/ 37 阅读

相关 HDU - 5536 Chip Factory（字典树）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5536 题意：给一个长度为n的序列a，从这里选出三个序列ai,aj,ak使得（

超、凢脫俗/ 2022年06月08日 10:10/ 0 赞/ 173 阅读

相关字典树-HDU 5536-Chip Factory

字典树-HDU 5536-Chip Factory -------------------- 题目链接：[Chip Factory][] 题目基

朴灿烈づ我的快乐病毒、/ 2022年05月15日 05:21/ 0 赞/ 209 阅读

相关 HDU5536 01字典树求模板

include<bits/stdc++.h> using namespace std; const int N=1e5+10; struct T

傷城~/ 2022年05月09日 05:18/ 0 赞/ 206 阅读

相关可持久化线段树（主席树）学习笔记

主席树一种神奇数据结构，更令人半懂不懂的说法是叫做可持久化权值线段树名字由来据说发明者叫做HJT，于是就有人联想到了某国家领导人于是就有人称其为主席树了

迷南。/ 2021年12月21日 04:11/ 0 赞/ 339 阅读

相关 HDU4757 Tree (可持久化Trie)

题意：给出一棵树，每个点上有权值，有m组询问，每次询问从x到y的路径上的权值与z异或的最大值为多少。分析：最原始的是数集是固定的，只需要对数集按照高到低位去建Trie

￡神魔★判官ぃ/ 2021年12月16日 08:55/ 0 赞/ 205 阅读

相关 [学习笔记] 可持久化线段树&主席树

众所周知,线段树是一个非常好用也好写的数据结构, 因此,我们今天的前置技能:线段树. 然而,可持久化到底是什么东西? 别急,我们一步一步来... step 1 首

喜欢ヅ旅行/ 2021年11月19日 15:36/ 0 赞/ 327 阅读