首页 > 其他分享 >刷题 位运算异或 异或前缀和

刷题 位运算异或 异或前缀和

时间:2024-01-18 14:00:28浏览次数:24  
标签:前缀 int ed 异或 include pre1 刷题

2024.1.18 杭州电子科技大学2023华为杯编程竞赛

 

解题思路

首先可以知道,我们任意选一点为根 root 往下递归异或就可以得到 f [ i ](root 到 i 的路径异或值 ),那么  l 到 r 的路劲异或值可以由 f [ l ] ^ f [ r ]得出

那么如何计算答案呢,就是用 f [ l ]~f [ r ] 分别异或f [ x ] 相加即可,但是1e5级别的询问显然时间复杂度不可以接受,然后我们就行有什么可以快速算出 l ~ r 的贡献呢,这里可以想到用前缀和;

(当然不是异或前缀和,异或不满足分配律,比如 (2^3+2^3+4^3)!=8^3

所以是另一种 :计算1~n , f [ i ] 2进制的每一位1和0的前缀和,

那么答案就是,对f [ x ] 的每一位的贡献计算,比如f [ x ] 第2位是0,那么根据异或1异或0才有贡献, 贡献就是 pow( 2 , i (第几位) *( sum1[ r ][ i ]-sum1[ l-1 ][ i ] );

复杂度位1e5*30,显然可以接受

(这道题我一开始把所有变量换成longlongTLE了,只换ans其他部分用1ll处理就过了,longlong效率比int低,注意,如果看表面复杂度过了但TLE了可能就是这个问题)
 

代码

 

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
using namespace std;
#define ll long long
const int N=100005;
vector<pair<int,int>> e[N];
int f[N],pre1[N][32],pre0[N][32];
int n;
void solve(int x,int fa)
{
	for(auto ed:e[x])
	{
		if(ed.first==fa)continue;
		f[ed.first]=f[x]^ed.second;//f存储每个点到根的路径异或和
		solve(ed.first,x);
	}
}
inline void init()
{
	for(int i=1;i<=n;i++)
	{
		e[i].clear();
		f[i]=0;
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		cin>>n;
		init();
		for(int i=1;i<n;i++)
		{
			int u,v,w;
			cin>>u>>v>>w;
			e[u].push_back({v,w});
			e[v].push_back({u,w});
		}
		solve(1,-1);
		for(int i=1;i<=n;i++)
		{
			for(int j=0;j<30;j++)
			{
				int x=((f[i]>>j)&1);//提取每一位数字
				pre1[i][j]=pre1[i-1][j]+(x>0);//pre1用来存储前i个点中有多少路径异或和的第j位能在x的第j位为0时做出贡献的
				pre0[i][j]=pre0[i-1][j]+(x==0);//pre0用来存储前i个点中有多少路径异或和的第j位能在x的第j位为1时做出贡献的
			}
		}
		int q;
		cin>>q;
		while(q--)
		{
			int l,r,x;
			cin>>l>>r>>x;
			ll ans=0;//要开long long
			for(int i=0;i<30;i++)
			{
				int t=((f[x]>>i)&1);
				if(t) ans+=1ll*(1ll<<i)*(pre0[r][i]-pre0[l-1][i]);//算式里也要注意long long
				else ans+=1ll*(1ll<<i)*(pre1[r][i]-pre1[l-1][i]);
			}
			cout<<ans<<'\n';
		}
	}
	return 0;
}

标签:前缀,int,ed,异或,include,pre1,刷题
From: https://www.cnblogs.com/modemingzi-csy/p/17972356

相关文章

  • 算法—前缀和
    1.一维前缀和S[i]=a[1]+a[2]+...a[i]//求s[n]a[l]+...+a[r]=S[r]-S[l-1]//求l-r的序列和2.二维前缀和S[i,j]=s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];第i行j列格子左上部分所有元素的和以(x1,y1)为左上角,(x2,y2)为右下角的子矩阵的和为:S[......
  • 前缀和求解(c++)
    数组ana1a2...an前缀和Si=a1+a2+...+ai①如何求②作用//一维数组前缀和的计算#include<iostream>usingnamespacestd;constintN=100010;inta[N],s[N];intn,m;intmain(){scanf("%d%d",&n,&m);for(inti=1;i<=n;......
  • 前缀和&差分
    前缀和&差分(蒟蒻篇)前缀和前缀和是指某序列的前n项和,而差分可以看成前缀和的逆运算。一般用于大量的求一段连续区间的和时间复杂度:预处理O(n),查询O(1)一维前缀和模板作用是:找a序列的一段连续区间的和for(inti=1;i<=n;i++)sum[i]=sum[i-1]+a[i];......
  • [刷题技巧] LeetCode238. 除自身以外数组的乘积
    题目描述思路:前缀/后缀乘积数组构造除自身以外数组的左边前缀乘积构造除自身以外数组的右边后缀乘积然后对应位置相乘方法一:classSolution{publicint[]productExceptSelf(int[]nums){intn=nums.length;//前缀乘积数组:leftProduct[i]表......
  • abc098d<双指针,异或>
    题目D-XorSum2给出n个元素的数组a,求满足条件的子区间个数:数组a子区间元素和与异或和相等。思路和与异或和相同,即没有任何进位,也就是区间中对于范围内每个二进制位,最多出现一次;使用双指针,统计每个二进制位最多出现一次的区间个数即可;总结异或:不进位加法;代码点击......
  • [刷题技巧] 前缀和相关知识点汇总
    一、前缀和的作用前缀和技巧适用于快速、频繁地计算一个索引区间内的元素之和。二、前缀和的思路将原始数组进行预处理,将来需要查询数据的时候,只需要查询预处理的前缀和数组的某些值即可。前缀和的求解是【动态规划】。三、前缀和的定义四、前缀和数组的构造//int[]nums......
  • [刷题班] LeetCode1480. 一维数组的动态和
    题目描述思路:前缀和前缀和数组(prefixSum)的构造方法一:classSolution{publicint[]runningSum(int[]nums){int[]preSum=newint[nums.length];preSum[0]=nums[0];for(inti=1;i<nums.length;i++){preSum[i]......
  • [刷题班] LeetCode125. 验证回文串
    题目描述思路:左右指针只考虑数字和字母字母的话需要全部转化为小写然后使用左右指针判断是否是回文串方法一:classSolution{publicbooleanisPalindrome(Strings){List<Character>list=newArrayList<>();for(charc:s.toCharArray()){......
  • [刷题班] LeetCode11. 盛最多水的容器
    题目描述思路:左右指针方法一:暴力,超出时间限制模拟所有情况,记录最大的体积值。体积=Math.min(height[i],height[j])*(j-i)classSolution{publicintmaxArea(int[]height){intres=Integer.MIN_VALUE;for(inti=0;i<height.leng......
  • [刷题班] LeetCode27. 移除元素
    题目描述思路:快慢指针slow指针:其前面都是数值不等于val的元素。fast指针:用于遍历。方法一:classSolution{publicintremoveElement(int[]nums,intval){intslow=0,fast=0;for(;fast<nums.length;fast++){if(nums[fas......