网站制作软件下载,珠海网站建设 科速,嵌入式设计与开发,陕西省两学一做网站题目链接#xff1a;
蓝桥杯2023年第十四届省赛真题-异或和之和 - C语言网 (dotcpp.com) 1.异或和之和 - 蓝桥云课 (lanqiao.cn)
参考题解#xff1a; 蓝桥杯真题讲解#xff1a;异或和之和 #xff08;拆位、贡献法#xff09;-CSDN博客
洛谷P9236 [蓝桥杯 2023 省 A]…题目链接
蓝桥杯2023年第十四届省赛真题-异或和之和 - C语言网 (dotcpp.com) 1.异或和之和 - 蓝桥云课 (lanqiao.cn)
参考题解 蓝桥杯真题讲解异或和之和 拆位、贡献法-CSDN博客
洛谷P9236 [蓝桥杯 2023 省 A] 异或和之和 题解_c加加区间异或问题洛谷ir-CSDN博客
说明
1.需要知道一个重要的结论图片来自参考题解 注为什么A^BC可以得到B^CA 在原式上两边同时异或上一个B根据异或的性质B^B0,与0异或等于本身。
2.那么由前缀和可以得出
sum(j,i)为i和j这个区间上面的异或和右下角第二排的式子等号两边同时异或上一个s[j-1]得到第一排的式子 3.从推出的这个式子来看sum[ij]s[i]^s[j-1]i右端点j左端点
说明任意一个区间上面的异或和都可以转化成两个异或前缀和的异或和。再考虑到对于一个二进制位来说异或和结果为1的时候才会对结果有影响(贡献)而奇数个1异或为1偶数个为0对应到这里的两个数前缀和异或那么就是一个前缀和为0一个为1那么把n个数都进行拆位就可以 对每一个二进制位 做操作数是0或1只有拆成二进制的0和1才能直接用前面的结论的异或位运算。
于是统计在第k位从0开始数上n个数中对应前缀和为0、1的数量记为n0n1那么最后在这一位上的对结果的贡献就是n0*n1* 。 这里注意需要把S[0]考虑进来左端点位置为1的时候计算区间需要s[0] 而S[0]为0 所以0的初始数量为1 为什么会是n0 * n1 * 因为n0是前缀和为0的数量n1是前缀和为1的数量我们在n0个位置里面选一个再在n1个位置里选一个他们计算出来的区间异或和sumij是为1的且这个sumij不重复因为你计数的0和1的位置是不重复的那么计算出来的sumij的至少由一个端点跟别的sum不一样那么n0*n1是sumij为1的个数乘上这一位上的基数即可。
4.另一种思路
在参考题解第二个文章里提出了另一种思路既然
对于一个二进制位来说异或和结果为1的时候才会对结果有影响(贡献)而奇数个1异或为1偶数个为0
那么我统计我当前位置是出现1的奇数次还是偶数次根据
sum[ij]s[i]^s[j-1] 为奇数次s[i]为1要求s[j-1]为偶数次
为偶数次s[i]为0要求s[j-1]为奇数次即要求总的次数为奇数。 于是很容易去找记前面为偶数次的 位置数 为 even奇数次为odd
s[i]为奇数次是不是就有 even1个 为奇数次1 的区间因为这even个偶数次的 位置都可以作为s[j-1]的这个j-1位置还有s[0]00也是偶数次这个没被计数到(1,i)也是一个奇数个的区间所以还要加1
s[i]为偶数次是不是就有 odd个 为奇数次1 的区间因为是要求s[j-1]为奇数次所以不加1.
或者可以这样考虑
s[i]为奇数次even个前面为偶数次的 位置这些位置第一次出现对应的数肯定是1且这个1只出现一次对应这个偶数否则1的数量就变了0可以出现无数次那么就是对应一个偶数o他出现的第一个位置ma[m]假设a为第k位上这n个数的01序列的数组名为1s[m-1]肯定只出现了o-1次这个位置不能组成合法区间去掉。
而对于一个奇数p第一次出现的位置ra[r]为1s[r-1]为偶数次p-1需要加上这个位置。
于是合法的区间even-出现的偶数的数量若出现24则数量为2出现的奇数的数量
当s[i]为奇数次奇数的数量比偶数数量多1推出上面同样的式子。
s[i]为偶数次二者相等推出上面同样的式子。
5.注意
数据范围数组每个数小于等于2的20次方那么要考虑的二进制位数就是21位不是20位
代码
仅异或前缀和
要枚举左右端点时间复杂度 会超时。60%数据。
#include bits/stdc.h
#define int long long
using namespace std;
const int N1e510;
int ans0;
int a[N];
int s[N];//异或前缀和 //vectorint num[N];
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cinn;for(int i1;in;i){cina[i];//ansa[i];s[i]s[i-1]^a[i];}for(int i1;in;i){for(int ji;jn;j){int sums[j]^s[i-1];// sum(i,j)^s[i-1]s[j]两百年同时异或s[i-1]消掉左边的 s[i-1]anssum;}}coutans;return 0;
}
说明3对应代码
#include bits/stdc.h
#define int long long
using namespace std;
const int N1e510;
int ans0;
int a[N];
int s[N];
//异或前缀和
int odd,even,cnt0,radix1;
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cinn;for(int i1;in;i){cina[i]; }radix1;for(int i0;i20;i){//这里同样注意需要把S[0]考虑进来左端点位置为1的时候计算区间需要s[0] 而S[0]为0 //所以0的初始数量为1 int n01,n10;for(int j1;jn;j){//求第i位上的二进制前缀和 s[j]s[j-1]^(a[j]1);if(s[j]1){n1;} else{n0;}a[j]a[j]1;}ansn0*n1*radix;radixradix1;}coutans;return 0;
}说明4对应代码
#include bits/stdc.h
#define int long long
using namespace std;
const int N1e510;
int ans0;
int a[N];
int s[N];
//异或前缀和
int odd,even,cnt0,radix1;
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cinn;for(int i1;in;i){cina[i];}// 对二进制的21个位置中的第j个位置算n个数的贡献 //注意是 0-20位有21个位置 for(int j0;j20;j){cnt0;odd0,even0;//对第i个数而言它的二进制形式的第j位从0开始数能找到的能贡献1的区间数//这个区间是i和前i个数组成的。有多少个能贡献1的区间在第i位上结果就加上多少个1 最后结果要乘上第j位对应的基数2的j次方 for(int i1;in;i){//对n个数计算第j位上的异或和之和 //注意取出最后一位的方法 int tta[i]1;//取出二进制位 if(tt1){//计算二进制第j位上到第i个数是出现了几个1用前缀和累加可以在O1复杂度计算出 s[i]s[i-1]1;}else{s[i]s[i-1];}if(s[i]%20){//到第i数出现了偶数个1那么他能找到 前i项中为奇数次的数量 个贡献1的区间 even;ans(odd)*radix;//注意乘上第j位对应的基数 }else{//到第i数出现了奇数个1那么他能找到 前i项中为偶数次的数量1 个贡献1的区间 odd;ans(even1)*radix;}a[i]a[i]1;//第i个数左移一位方便下一次取j1位 }radixradix1;//j1位基数变成原来的2倍 }// for(int i1;in;i){
// for(int ji;jn;j){
// int sums[j]^s[i-1];// sum(i,j)^s[i-1]s[j]两百年同时异或s[i-1]消掉左边的 s[i-1]
// anssum;
// }
// }coutans;return 0;
}
文章转载自： http://www.morning.rcmcw.cn.gov.cn.rcmcw.cn http://www.morning.xxgfl.cn.gov.cn.xxgfl.cn http://www.morning.jrbyz.cn.gov.cn.jrbyz.cn http://www.morning.mgkb.cn.gov.cn.mgkb.cn http://www.morning.nrmyj.cn.gov.cn.nrmyj.cn http://www.morning.wnnts.cn.gov.cn.wnnts.cn http://www.morning.fksdd.cn.gov.cn.fksdd.cn http://www.morning.dqxnd.cn.gov.cn.dqxnd.cn http://www.morning.ldnrf.cn.gov.cn.ldnrf.cn http://www.morning.trpq.cn.gov.cn.trpq.cn http://www.morning.kzrg.cn.gov.cn.kzrg.cn http://www.morning.xnwjt.cn.gov.cn.xnwjt.cn http://www.morning.txysr.cn.gov.cn.txysr.cn http://www.morning.tqklh.cn.gov.cn.tqklh.cn http://www.morning.ydxg.cn.gov.cn.ydxg.cn http://www.morning.jhtrb.cn.gov.cn.jhtrb.cn http://www.morning.dtnzk.cn.gov.cn.dtnzk.cn http://www.morning.gxhqt.cn.gov.cn.gxhqt.cn http://www.morning.lfqnk.cn.gov.cn.lfqnk.cn http://www.morning.ljygq.cn.gov.cn.ljygq.cn http://www.morning.qgfhr.cn.gov.cn.qgfhr.cn http://www.morning.gwqq.cn.gov.cn.gwqq.cn http://www.morning.kryxk.cn.gov.cn.kryxk.cn http://www.morning.phjny.cn.gov.cn.phjny.cn http://www.morning.xglgm.cn.gov.cn.xglgm.cn http://www.morning.xblrq.cn.gov.cn.xblrq.cn http://www.morning.divocn.com.gov.cn.divocn.com http://www.morning.gtcym.cn.gov.cn.gtcym.cn http://www.morning.fsbns.cn.gov.cn.fsbns.cn http://www.morning.bfrsr.cn.gov.cn.bfrsr.cn http://www.morning.lwcqh.cn.gov.cn.lwcqh.cn http://www.morning.mooncore.cn.gov.cn.mooncore.cn http://www.morning.lczxm.cn.gov.cn.lczxm.cn http://www.morning.mxftp.com.gov.cn.mxftp.com http://www.morning.fxzw.cn.gov.cn.fxzw.cn http://www.morning.fkyrk.cn.gov.cn.fkyrk.cn http://www.morning.ktmbp.cn.gov.cn.ktmbp.cn http://www.morning.kyzja.com.gov.cn.kyzja.com http://www.morning.hhfqk.cn.gov.cn.hhfqk.cn http://www.morning.rppf.cn.gov.cn.rppf.cn http://www.morning.mdfxn.cn.gov.cn.mdfxn.cn http://www.morning.tkztx.cn.gov.cn.tkztx.cn http://www.morning.skqfx.cn.gov.cn.skqfx.cn http://www.morning.sbwr.cn.gov.cn.sbwr.cn http://www.morning.rchsr.cn.gov.cn.rchsr.cn http://www.morning.ltdxq.cn.gov.cn.ltdxq.cn http://www.morning.bwgrd.cn.gov.cn.bwgrd.cn http://www.morning.bhmnp.cn.gov.cn.bhmnp.cn http://www.morning.xxrgt.cn.gov.cn.xxrgt.cn http://www.morning.qzmnr.cn.gov.cn.qzmnr.cn http://www.morning.ccphj.cn.gov.cn.ccphj.cn http://www.morning.xfmwk.cn.gov.cn.xfmwk.cn http://www.morning.tfzjl.cn.gov.cn.tfzjl.cn http://www.morning.lxcwh.cn.gov.cn.lxcwh.cn http://www.morning.zlbjx.cn.gov.cn.zlbjx.cn http://www.morning.mnmrx.cn.gov.cn.mnmrx.cn http://www.morning.zwppm.cn.gov.cn.zwppm.cn http://www.morning.zbnkt.cn.gov.cn.zbnkt.cn http://www.morning.czxrg.cn.gov.cn.czxrg.cn http://www.morning.kwfnt.cn.gov.cn.kwfnt.cn http://www.morning.bkpbm.cn.gov.cn.bkpbm.cn http://www.morning.jyknk.cn.gov.cn.jyknk.cn http://www.morning.jcfg.cn.gov.cn.jcfg.cn http://www.morning.xgmf.cn.gov.cn.xgmf.cn http://www.morning.kkwbw.cn.gov.cn.kkwbw.cn http://www.morning.yldgw.cn.gov.cn.yldgw.cn http://www.morning.ynstj.cn.gov.cn.ynstj.cn http://www.morning.rcklc.cn.gov.cn.rcklc.cn http://www.morning.qxxj.cn.gov.cn.qxxj.cn http://www.morning.pffqh.cn.gov.cn.pffqh.cn http://www.morning.qtkfp.cn.gov.cn.qtkfp.cn http://www.morning.rfmzc.cn.gov.cn.rfmzc.cn http://www.morning.ssglh.cn.gov.cn.ssglh.cn http://www.morning.jcxzq.cn.gov.cn.jcxzq.cn http://www.morning.ltxgk.cn.gov.cn.ltxgk.cn http://www.morning.c7623.cn.gov.cn.c7623.cn http://www.morning.fjfjm.cn.gov.cn.fjfjm.cn http://www.morning.zycll.cn.gov.cn.zycll.cn http://www.morning.mhpmw.cn.gov.cn.mhpmw.cn http://www.morning.lbgfz.cn.gov.cn.lbgfz.cn
