【BZOJ5495】[十二省联考2019]异或粽子(主席树,贪心)
题面
题解
这不是送分题吗。。。
转异或前缀和,构建可持久化\(Trie\)。
然后拿一个堆维护每次的最大值,每次如果取了一个数,就把它再在\(Trie\)树上查一次新建一个元素丢回堆里就行了。
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
#define ll long long
#define MAX 500500
inline ll read()
{
ll x=0;bool t=false;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')t=true,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
return t?-x:x;
}
struct Node{int ch[2],v;}t[MAX*80];
int tot,rt[MAX];
void Modify(int &x,int d,ll val,int w)
{
++tot;t[tot]=t[x];x=tot;t[x].v+=w;if(d==-1)return;
if((val>>d)&1)Modify(t[x].ch[1],d-1,val,w);
else Modify(t[x].ch[0],d-1,val,w);
}
ll Query(int x,int d,ll val)
{
if(d==-1)return 0;int c=(val>>d)&1;
if(t[t[x].ch[c^1]].v)return (1ll<<d)+Query(t[x].ch[c^1],d-1,val);
else return Query(t[x].ch[c],d-1,val);
}
struct Data{ll w;int x;};
bool operator<(Data a,Data b){return a.w<b.w;}
priority_queue<Data> Q;
ll a[MAX],ans;int n,K;
int main()
{
n=read();K=read();
for(int i=1;i<=n;++i)a[i]=a[i-1]^read();
for(int i=1;i<=n;++i)rt[i]=rt[i-1],Modify(rt[i],32,a[i-1],1);
for(int i=1;i<=n;++i)Q.push((Data){Query(rt[i],32,a[i]),i});
while(K--)
{
Data u=Q.top();Q.pop();
ans+=u.w;Modify(rt[u.x],32,u.w^a[u.x],-1);
Q.push((Data){Query(rt[u.x],32,a[u.x]),u.x});
}
printf("%lld\n",ans);
return 0;
}
【BZOJ5495】[十二省联考2019]异或粽子(主席树,贪心)的更多相关文章
-
[十二省联考2019]异或粽子——可持久化trie树+堆
题目链接: [十二省联考2019]异或粽子 求前$k$大异或区间,可以发现$k$比较小,我们考虑找出每个区间. 为了快速得到一个区间的异或和,将原序列做前缀异或和. 对于每个点作为右端点时,我们维护出 ...
-
[十二省联考2019]异或粽子 01trie
[十二省联考2019]异或粽子 01trie 链接 luogu 思路 首先求前k大的(xo[i]^xo[j])(i<j). 考场上只想到01trie,不怎么会写可持久,就写了n个01trie,和 ...
-
【简】题解 P5283 [十二省联考2019]异或粽子
传送门:P5283 [十二省联考2019]异或粽子 题目大意: 给一个长度为n的数列,找到异或和为前k大的区间,并求出这些区间的异或和的代数和. QWQ: 考试时想到了前缀异或 想到了对每个数按二进制 ...
-
Luogu P5283 / LOJ3048 【[十二省联考2019]异或粽子】
联考Day1T1...一个考场上蠢了只想到\(O(n^2)\)复杂度的数据结构题 题目大意: 求前\(k\)大区间异或和的和 题目思路: 真的就是个sb数据结构题,可持久化01Trie能过(开O2). ...
-
【洛谷5283】[十二省联考2019] 异或粽子(可持久化Trie树+堆)
点此看题面 大致题意: 求前\(k\)大的区间异或和之和. 可持久化\(Trie\)树 之前做过一些可持久化\(Trie\)树题,结果说到底还是主席树. 终于,碰到一道真·可持久化\(Trie\)树的 ...
-
Luogu P5283 [十二省联考2019]异或粽子
感觉不是很难的一题,想了0.5h左右(思路歪了,不过想了一个大常数的两只\(\log\)做法233) 然后码+调了1h,除了一个SB的数组开小外基本上也没什么坑点 先讲一个先想到的方法,我们对于这种问 ...
-
[十二省联考2019]异或粽子(堆+可持久化Trie)
前置芝士:可持久化Trie & 堆 类似于超级钢琴,我们用堆维护一个四元组\((st, l, r, pos)\)表示以\(st\)为起点,终点在\([l, r]\)内,里面的最大值的位置为\( ...
-
Luogu5283 十二省联考2019异或粽子(trie/可持久化trie+堆)
做前缀异或和,用堆维护一个五元组(x,l,r,p,v),x为区间右端点的值,l~r为区间左端点的范围,p为x在l~r中最大异或和的位置,v为该最大异或和,每次从堆中取出v最大的元素,以p为界将其切成两 ...
-
洛谷.5283.[十二省联考2019]异或粽子(可持久化Trie 堆)
LOJ 洛谷 考场上都拍上了,8:50才发现我读错了题=-= 两天都读错题...醉惹... \(Solution1\) 先求一遍前缀异或和. 假设左端点是\(i\),那么我们要在\([i,n]\)中找 ...
随机推荐
-
Python模块:hashlib
hashlib:提供了常见的摘要算法,如MD5,SHA1等. import hashlib m = hashlib.md5() m.update('how to use md5 in python h ...
-
nw.js如何处理拖放操作
nw.js如何处理拖放操作 其实拖放(drag-drop)操作是Html5的功能,不是nw.js的内置API,那么我们采用Html5应用一般的处理方法就可以了. 首先我们看一下一个正常的页面,直接拖放 ...
-
JSP-03-实现数据传递
会话跟踪:隐藏表单域.URL重写和Cookie 3.1 传参方法 get /post 区别 3.2 request 获取参数 数据类型 变量名 = (数据类型)request.getPar ...
-
Fiddler抓包【5】_Fiddler过滤
1.User Fiters启用 2.Action Action:Run Filterset now是否运行,Load Filterset加载,Save Filterset保存: 3.Hosts过滤 Z ...
-
区间DP经典 石子合并
题目链接 题意:环形的一群石子,每次可以选择相邻的两堆合并,分数为新得到的一堆石子,求将这片石子合并成一堆的最大和最小分数 输入:第一行一个正整数n,其后n个数代表每堆石子的个数 分析:第一次写的时候 ...
-
Saddle Point ZOJ - 3955(求每个值得贡献)
题意: 给出一个矩阵,删掉一些行和列之后 求剩下矩阵的鞍点的总个数 解析: 对于每个点 我们可以求出来 它所在的行和列 有多少比它大的 设为a 有多少比它小的 设为b 然后对于那些行和列 都有两种操 ...
-
STL容器之deque
[1]deque容器 deque 是对 vector 和 list 优缺点的结合,它是处于两者之间的一种容器. [2]deque方法集 应用示例代码: #include <deque> # ...
-
spring 手册
https://www.tutorialspoint.com/spring/spring_architecture.htm
-
java文件生成
package com.gcy.test.util; import java.io.BufferedWriter; import java.io.File; import java.io.FileNo ...
-
python之函数用法setattr(),了解即可
# -*- coding: utf-8 -*- #python 27 #xiaodeng #python之函数用法setattr(),了解即可 #http://www.cnblogs.com/hong ...