首页 > 其他分享 >LG5283 [十二省联考 2019] 异或粽子 题解

LG5283 [十二省联考 2019] 异或粽子 题解

时间:2022-11-14 20:02:25浏览次数:77  
标签:ch int 题解 ll LG5283 1ll 异或 include 联考

口胡一个异或经典问题

LG5283 [十二省联考 2019] 异或粽子

给定一个长为 \(n\) 的序列,序列一段子区间 \([l,r]\) 的值为 \([l,r]\) 范围内所有数异或起来的值。现在求出前 \(k\) 大的子区间的值的和。

\(n\leq 5\times 10^5,k\leq 2\times 10^5\)。

根据异或的性质,一段子区间 \([l,r]\) 的值为前缀异或和数组 \(s_r\oplus s_{l-1}\) 的值。

所以等价于找到前 \(k\) 大的 \(s_i \oplus s_j\) 的值(\(0\leq i<j\leq n\))。为了方便,改成求前 \(2k\) 大的 \(s_i\oplus s_j\) 值(\(i,j\) 无限制,同时 \(i=j\) 的情况异或和为 \(0\),如果每次按最大的取是不会取到的),然后这个值除以二。

于是我们将所有 \(s_i\) 插入一个 \(\texttt{01trie}\) 中。对于每一个组数 \((s_j,t)\),我们是能通过 \(\texttt{01trie}\) 找到与 \(s_j\) 异或后第 \(t\) 大的数的(比较基础吧)。

因此我们先将所有 \((s_j,n+1)\) 的值加入一个大根堆中,同时附加信息编号 \(j\),同时开一个数组 \(lef\) 表示 \(s_j\) 还能参与统计了多少次答案,初始为 \(lef_j=n\)。每次从堆中找到最大的数,统计答案,并再将 \((s_j,lef_j-1)\) 加入大根堆,同时 \(lef_j:=lef_j-1\)。

具体实现见代码。

时间复杂度 \(O(k\log n\times \log_2 a)\)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>ttfa;
inline ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar();}
	while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=500005;
int ch[N*34][2],tot=1,siz[N*34];
inline void inser(ll x){
	int u=1;++siz[u];
	for(ll i=33;i>=0;--i){
		ll c=((x>>i)&1ll);
		if(!ch[u][c])ch[u][c]=++tot;
		u=ch[u][c];++siz[u];
	}
}
priority_queue<ttfa>q;
int lef[N],n,k;
ll a[N],ans;
inline ll query(ll x,int k){
	int u=1;ll tmp=0;
	for(ll i=33;i>=0;--i){
		ll c=((x>>i)&1ll);
		if(k<=siz[ch[u][c]])u=ch[u][c];
		else k-=siz[ch[u][c]],u=ch[u][c^1],tmp|=(1ll<<i);
	}
	return tmp;
}
int main(){
	n=read(),k=read()*2;
	inser(0);//前缀和,所以一开始的 0 也要进
	for(int i=1;i<=n;++i){
		a[i]=read()^a[i-1];
		inser(a[i]);
	}
	for(int i=0;i<=n;++i){
		q.push({query(a[i],n+1),i});
		lef[i]=n;
	}
	while(k--){
		ttfa tmp=q.top();q.pop();
		ans+=tmp.first;
		//printf("%lld %lld\n",tmp.first,tmp.second);
		int i=tmp.second;
		q.push({query(a[i],lef[i]--),i});
	}
	printf("%lld\n",ans/2ll);
	return 0;
}

加强版

求出 \(n\) 个数,两两异或的前 \(k\) 大的数之和。

\(k\leq \frac{n(n-1)}{2}\)。

首先考虑求出两两异或的第 \(k\) 大值。和往常一样在 \(\texttt{01trie}\) 上从低往高讨论第 \(k\) 大值能不能 \(1\) 即可。时间复杂度为 \(O(n \log a)\)。

在这个过程中我们求得了大于第 \(k\) 大值的最小的数和 \(res\) 表示第 \(k\) 大值的个数。

现在考虑如何求和前 \(k\) 大值的和。

枚举每一个 \(a_i\),同样从高位到低位求解。若两两异或的第 \(k\) 大值的这一位是 \(0\),则 \(a_i\) 与【与 \(u\) 这一层下方向相反的子树】中叶子结点的对应值的异或值大于第 \(k\) 大值。这样的子树最多又 \(O(n\log_2 a)\) 个。现在我们的问题是如何求 \(a_i\) 与某一子树中的值的异或值之和。

我们将 \(a_i\) 数组排序,并不会影响之前的处理,然后处理出其每一位上 \(1\) 的个数的前缀和,需要求值时找到子树中最小值和最大值,对应数组中的左右端点,差分求值即可。由于问要按位计算,单次求值的之间复杂度为 \(O(\log_2 a)\)。

总时间复杂度 \(O(n\log_2 a)\)。

讲得自己都不是很清楚(有很大部分是直接抄的题解),还是看看代码吧。

CF241B Friends

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>ttfa;
inline ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar();}
	while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*f;
}
#define int long long
const int N=150005;
const ll MOD=1000000007,INV2=(MOD+1)/2;
ll n,k,a[N],sum[N][32],val;
int ch[N*32][2],lef[N*32],rit[N*32],siz[N*32],tot,pos[N];
inline ll calc(ll v,int l,int r){
	if(l==0)return 0;
	ll tmp=0;
	for(int i=30;i>=0;--i){
		int c=(v>>i)&1;
		if(!c)tmp=(tmp+(1ll<<i)*(sum[r][i]-sum[l-1][i])%MOD)%MOD;
		else tmp=(tmp+(1ll<<i)*(r-l+1-sum[r][i]+sum[l-1][i])%MOD)%MOD;
	}
	return tmp;
}
signed main(){
	n=read(),k=read();k*=2;
	for(int i=1;i<=n;++i)a[i]=read();
	sort(a+1,a+1+n);
	for(int i=1;i<=n;++i)
		for(int j=0;j<=30;++j)
			sum[i][j]=sum[i-1][j]+((a[i]>>j)&1ll);
	tot=1;
	for(int i=1;i<=n;++i){
		int u=1;++siz[u];
		for(int j=30;j>=0;--j){
			int c=(a[i]>>j)&1ll;
			if(!ch[u][c])ch[u][c]=++tot,lef[tot]=i;
			u=ch[u][c];rit[u]=i;++siz[u];
		}
	}
	for(int i=1;i<=n;++i)pos[i]=1;
	for(int i=30;i>=0;--i){
		ll tot=0;
		for(int j=1;j<=n;++j){
			int c=((a[j]>>i)&1ll)^1ll;
			tot+=siz[ch[pos[j]][c]];
		}
		bool f=0ll;
		if(k<=tot)f=1ll,val|=(1ll<<i);
		else k-=tot;
		for(int j=1;j<=n;++j){
			int c=((a[j]>>i)&1ll)^f;
			pos[j]=ch[pos[j]][c];
		}
	}
	ll ans=0ll;
	for(int i=1;i<=n;++i){
		int u=1;
		for(int j=30;j>=0;--j){
			int c=((a[i]^val)>>j)&1ll,v=ch[u][c^1];
			if(!((val>>j)&1)&&ch[u][c^1])
				ans=(ans+calc(a[i],lef[v],rit[v]))%MOD;
			u=ch[u][c];
		}
	}
	printf("%lld\n",(ans+k*val%MOD)*INV2%MOD);
	return 0;
}

滚存字典树 CF1055F Tree and XOR

给一颗 \(n\) 个点的数,有边权,你要求出 \(n^2\) 个点对中第 \(k\) 小的路径异或和。

\(n\leq 10^6,k\leq n^2,w\leq 2^{62}\)。

注意这题不需要计算小于等于第 \(k\) 小的所有路径的异或和,而是只需要求出这第 \(k\) 小时什么。

做法其实和 friends 是一样的,但是空间开不下了。

容易发现我们按位从高到底贪心选择答案的每一位时,只需要考虑当前这一位子树的字典树上的信息,因此我们直接考虑统计一位字典树的时候把上一位的字典树全部清空,只需要记录每个数在字典树上上一位到达的结点即可。

具体实现见代码,有注释。

const int N=1000006;
int n,pos[N],loc[N],ch[N][2],siz[N],tot;
ll k,a[N],ans;
int main(){
	n=read(),k=read();
	for(int i=2;i<=n;++i){
		int f=read();ll w=read();
		a[i]=a[f]^w;
	}
	for(int i=1;i<=n;++i)pos[i]=loc[i]=1;
	//pos[i] 表示 trie 树上对于第 i 个点建树到的位置
	//loc[i] 表示寻找答案的时候对于第 i 个数合法的位置
	for(int i=61;i>=0;--i){
		ll cnt=0;//清空 trie 的上一层
		for(int j=1;j<=tot;++j)ch[j][0]=ch[j][1]=siz[j]=0;
		tot=0;
		for(int j=1;j<=n;++j){//然后建出这一层的 trie 数
			int c=((a[j]>>i)&1ll);
			if(!ch[pos[j]][c])ch[pos[j]][c]=++tot;
			++siz[pos[j]=ch[pos[j]][c]];
		}
		for(int j=1;j<=n;++j)
			cnt+=siz[ch[loc[j]][(a[j]>>i)&1]];//统计与这一位数异或为 0 的个数
		bool f=0;
		if(cnt<k)k-=cnt,f=1,ans|=(1ll<<i);//答案这一位为 0 不够,需要为 1
		for(int j=1;j<=n;++j)
			loc[j]=ch[loc[j]][((a[j]>>i)&1ll)^f];
	}
	printf("%lld\n",ans);
	return 0;
}

标签:ch,int,题解,ll,LG5283,1ll,异或,include,联考
From: https://www.cnblogs.com/BigSmall-En/p/16890181.html

相关文章

  • 题解 HDU4035 【Maze】
    postedon2022-08-1712:33:51|under题解|sourceproblemhttps://vjudge.net/problem/HDU-4035SHY在一棵树上随机游走,从根节点出发,每次有\(k_u\)的几率回到根节......
  • ARC 103 /\/\/\/ 题解
    前缀和一下,就好了#include<bits/stdc++.h>usingnamespacestd;typedefunsignedlonglongull;constintN=1e5+99;inta[N],odd[N],even[N];structcmp{ boolo......
  • CSP-S 2022 题解
    T1假期计划\(\ttloj3899\)/\(\ttuoj773\)首先数据规模是\(n\le2500\),提示我们用\(\mathcalO\left(n^2\right)\)的算法。既然是选择\(4\)个互不相同的点,不妨......
  • 题解:【ABC245F】Endless Walk
    题目链接本题解适合像我这样的不具备思维能力的选手。首先根据题意,一个点如果符合要求,那它必然在一个点数大于\(2\)的强联通分量里,因为如果只有一个点它就哪里都去不了......
  • Codeforces 722 F Cyclic Cipher 题解 (同余方程,two-pointers)
    题目链接前两天做过一个题意类似但做法不类似的题在这里首先做这道题需要一个结论:(一元)同余方程组有解的充要条件是方程组中的所有方程两两联立有解。证明两个同......
  • CF1650G 『Counting Shortcuts』 题解
    从洛谷博客那里搬过来的(图论专题本来打算先挑最简单的做,结果做了两个多小时(题意就是让你找从起点\(s\)到终点\(t\)的最短路以及次短路个数,本题次短路长度指的是最短......
  • Codeforces 833 题解
    A\(n\)是奇数时恰好可以用完,\(n\)是偶数时多出来的一块没用,所以直接输出\((n+1)/2\)即可。B每个字符出现次数都小于等于字符总数,令\(\Sigma\)是字符集大小,那显然......
  • CF1292E Rin and The Unknown Flower 题解
    IO交互题fflush(stdout)害人不浅!!1注意到如果我们发起询问C和O就可以花费2的代价知道整个串,不过代价过高,所以我们考虑减小点代价。考虑发起询问CO,CH,CC,这样我......
  • TheNameCalculator题解
    TheNameCalculator题解题目链接:TheNameCalculator题解首先看程序开启的保护,有Canary和NX栈不可执行。IDA打开程序,shift+F12查看字符串,发现有"Hereisyourflag:"。点......
  • 833——B题题解
    题目链接题目大意:给一串字符串(只包含0~9),定义一个最优子串的定义:如果该子串同字符种类数大于最最多字符出现数,那么这个子串可以被称为最优子串。解题思路:大眼一看这个数......