「十二省联考 2019」异或粽子——tire树+堆
题目
【题目描述】
小粽是一个喜欢吃粽子的好孩子。今天她在家里自己做起了粽子。
小粽面前有 $n$ 种互不相同的粽子馅儿,小粽将它们摆放为了一排,并从左至右编号为 $1$ 到 $n$。第 $i$ 种馅儿具有一个非负整数的属性值 $a_i$。每种馅儿的数量都足够多,即小粽不会因为缺少原料而做不出想要的粽子。小粽准备用这些馅儿来做出 $k$ 个粽子。
小粽的做法是:选两个整数数 $l,r$,满足 $1\le l\le r\le n$,将编号在 $[l,r]$ 范围内的所有馅儿混合做成一个粽子,所得的粽子的美味度为这些粽子的属性值的**异或**和。(异或就是我们常说的 $\mathrm{xor}$ 运算,即 C/C++ 中的 `^` 运算符或 Pascal 中的 `xor` 运算符)
小粽想品尝不同口味的粽子,因此它不希望用同样的馅儿的集合做出一个以上的粽子。
小粽希望她做出的所有粽子的美味度之和最大。请你帮她求出这个值吧!
【输入格式】
从标准输入读入数据。
第一行两个正整数 $n,k$,表示馅儿的数量,以及小粽打算做出的粽子的数量。
接下来一行为 $n$ 个非负整数,第 $i$ 个数为 $a_i$,表示第 $i$ 个粽子的属性值。
【输出格式】
输出到标准输出。
输出一行一个整数,表示小粽可以做出的粽子的美味度之和的最大值。
【样例输入】
3 2
1 2 3
【样例输出】
6
【数据范围与提示】
|测试点|$n$|$k$|
|:-:|:-:|:-:|
|$1\sim 8$|$\le 10^{3}$|$\le 10^{3}$|
|$9\sim 12$|$\le 5 \times 10^{5}$|$\le 10^{3}$|
|$13\sim 16$|$\le 10^{3}$|$\le 2 \times 10^{5}$|
|$17\sim 20$|$\le 5 \times 10^{5}$|$\le 2 \times 10^{5}$|
对于所有的输入数据都满足:$1\le n \le 5 \times 10^{5},1\le k\le \min\left\{\frac{n(n-1)}{2},2 \times 10^{5}\right\},0\le a_i \le 4,294,967,295$。
题解
首先考虑在前缀异或和上暴力,$ n^2 $ 找出所有的值,放进堆里,取前 $ k $ 大的即可,效率 $ O(n^2+\log k) $,可以过 $ 60 \% $
显然把 $ x $ 所有能匹配的都找出来是不可能的,于是考虑在 tire 树上贪心
建 $ n $ 棵可持久化 tire 树,然后在 $ [0,i-1] $ 上贪心即可
考虑如何去重
于是我在测试时想到将 $ x $ 贪心对应的最大值的点 $ p $ 挖掉,然后变成两个区间 $ [l,p-1] $ 和 $ [p+1,r] $,找对应点时建一个链表即可(类似《超级钢琴》)
然而这样的常数太大,于是 map TLE,但还有 unorder map 嘛,跑得飞快
其实可以在 tire 树上二分第 $ k $ 大的值,放入堆时记录下是第 $ k $ 大的即可,为什么我没有想到
代码
显然二分是不可能去写的
#include<bits/stdc++.h>
#define LL long long
#define U unsigned
#include<tr1/unordered_map>
#define _(d) while(d(isdigit(ch=getchar())))
using namespace std;
LL R(){
LL x;bool f=;char ch;_(!)if(ch=='-')f=;x=ch^;
_()x=(x<<)+(x<<)+(ch^);return f?x:-x;}
const int N=5e5+;
int n,m,rot[N],tr[N*][],cnt,s[N*][],nex[N];
LL a[N],sum[N],ans;
struct node{
LL w,v;int l,r;
bool friend operator <(node a,node b){return a.w<b.w;}
};priority_queue<node> q;
tr1::unordered_map<LL,int>mp;
void insert(int &k,int o,LL len,LL v){
if(!~len)return;
k=++cnt;
int f=(v>>len)&;
tr[k][f^]=tr[o][f^],s[k][f^]=s[o][f^],s[k][f]=s[o][f]+;
insert(tr[k][f],tr[o][f],len-,v);
}
LL query(int k,int o,LL len,LL v){
if(!~len)return ;
int f=(v>>len)&;
if(s[k][f^]-s[o][f^])
return (1ll<<len)+query(tr[k][f^],tr[o][f^],len-,v);
else return query(tr[k][f],tr[o][f],len-,v);
}
int find(LL x,int l,int r){
for(int k=mp[x];k;k=nex[k])
if(k<=r&&k>=l)return k;
return ;}
int main(){
n=R(),m=R();
insert(rot[],,,);
for(int i=;i<=n;i++){
a[i]=R(),sum[i]=sum[i-]^a[i];
nex[i]=mp[sum[i]],mp[sum[i]]=i;
insert(rot[i],rot[i-],,sum[i]);
}
for(int i=;i<=n;i++){
LL w=query(rot[i-],,,sum[i]);
q.push((node){w,sum[i],,i-});
}
while(m--){
node now=q.top();q.pop();ans+=now.w;
int id=find(now.w^now.v,now.l,now.r);
if(id->=now.l)q.push((node){query(rot[id-],rot[now.l-],,now.v),now.v,now.l,id-});
if(now.r>=id+)q.push((node){query(rot[now.r],rot[id+-],,now.v),now.v,id+,now.r});
}
cout<<ans<<endl;
return ;
}
最新文章
- Atitit &#160;&#160;图像处理&#160;平滑&#160;也称&#160;模糊,&#160;归一化块滤波、高斯滤波、中值滤波、双边滤波)
- 在可以调用 OLE 之前,必须将当前线程设置为单线程单元(STA)模式
- Html5 Egret游戏开发 成语大挑战(六)游戏界面构建和设计
- NSDate 时间比较...等
- DOJO官方API翻译或解读-dojo/_base/lang --hitch()
- Thinkphp用exp表达式执行mysql语句,查询某字段不为空is not null,自动增值
- 51nod1022 石子归并 V2
- 实现自己的脚本语言ngscript之一:词法分析
- Spring MVC 之 Hello World
- Oracle运维服务的四根救命稻草
- lda 主题模型--TOPIC MODEL--Gibbslda++结果分析
- windbg 之 如何设置模块加载时断下
- 最近发现的.net core中的一些bugs
- re模块和正则表达式
- JavaScript中Null和undefind区别
- 【转】awk 里的substr函数用法举例
- echarts legend 重叠 (转载)
- The 16th Zhejiang provincial collegiate programming contest
- js中select标签中的option选择
- Java 初始 多态