江西网站制作的公司哪家好,家在深圳光明业主论坛,wordpress搭建小程序商城,wordpress西部题目链接
P9236 [蓝桥杯 2023 省 A] 异或和之和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 思路
1. 暴力求解
直接枚举出所有子数组#xff0c;求每个子数组的异或和#xff0c;再对所有的异或和求和
枚举所有子数组的时间复杂度为O#xff08;N^2#xff09;求每个子数组的异或和再对所有的异或和求和
枚举所有子数组的时间复杂度为ON^2求每个子数组的异或和又要遍历一次数组所以总的时间复杂度为ON^3
2. 优化
异或中有这么一个性质a ^ b ^ b a即两个相同元素异或后为0此性质推广到子数组同理
因此我们可以用前缀和的思想来快速得出一个区间的异或和。
此时可以将时间复杂度优化为ON^2
基于前缀和我们进行进一步的优化拆位法和贡献法
1拆位法
拆位法将一个数转换成二进制形式并拆分成单独的二进制位来计算
二进制中除了0就是1由于异或的性质我们可以得出一个结论对于二进制位中的第i位而言如果这一位中1的个数为奇数那么异或后的结果中这一位就是1否则为0
例如 拆位法加上前缀和我们就能计算出某个区间中1的个数进而得出在该区间中这个二进制位异或后是0还是1
2贡献法
贡献法从区间的角度转换成计算每个二进制位对答案的贡献
某个区间中这一位异或后的结果为1时这一位就产生了贡献异或后的结果为0时这一位就不会产生贡献。
例如 我们以一个二进制位作为一个计算周期统计该位中1的前缀和 例如该位中1的前缀和为偶数说明对于虚线内的这个区间异或后该位为0无贡献 注意这里的区间最终异或后只可能为1或0因此当我们谈论区间的贡献时实际上也就是谈论该位是否有贡献 但是如果一个前缀和为偶数的区间减去一个前缀和为奇数的区间所得到的新的区间的前缀和也为奇数即新区间中该位异或后的结果为1有贡献
例如 蓝色虚线的区间前缀和为偶数2减去红色虚线前缀和为奇数1的区间所得到蓝色实线区间的1的前缀和为奇数2 - 1 1则该实线区间异或后也有贡献
通过观察我们可以得出以下结论
对于第i个二进制位如果以第n个数为结尾的区间所对的前缀和为偶数时该区间能够提供 前面奇数前缀和的个数 个贡献区间
例如对于上面蓝色虚线的区间其前面有一个奇数前缀和那么该区间自身就能提供一个贡献区间 而该位中1的前缀和为奇数与上面同理我们只需要计算出前面所有前缀和为偶数的区间个数减去这些前缀和为偶数的区间得到的新区间前缀和都为奇数奇-偶奇则都有贡献
而因为该区间本身的前缀和为奇数所以能够提供的贡献区间为1 前面偶数前缀和的个数
通过提示我们可以知道所有的数中有效位数不会超过20 代码
#include bits/stdc.h
using namespace std;
#define ll long longll n;int main()
{cin n;ll *arr new ll[n];for (int i 0; i n; i)cin arr[i];ll pow 1, sum 0; for (int i 0; i 20; i) //最多计算20个二进制位 {ll counti 0, oddnum 0, evenum 0, range 0; //counti统计1的前缀和oddnum统计奇数前缀和的个数//evenum统计偶数前缀和的个数range统计有贡献区间个数 for (int j 0; j n; j) //遍历n个整数 {if (arr[j] 1) //按位与1后结果为1说明最低位为1否则为0 counti; //更新前缀和 if (counti % 2 1) //前缀和为奇数{range 1 evenum; //更新有贡献区间个数 oddnum; //奇数前缀和的个数1 }else //前缀和为偶数 {range oddnum; //更新有贡献区间个数 evenum; //偶数前缀和的个数1 }arr[j] 1; //移位 }sum range * pow; //计算位数对结果的贡献值 pow * 2; //更新pow }cout sum;return 0;
} 讲的不够清楚也请大家多多见谅有错误或问题可以在评论区指出。
