蓝桥杯23年第十四届省赛-异或和之和|拆位、贡献法
题目链接:
蓝桥杯2023年第十四届省赛真题-异或和之和 - C语言网 (dotcpp.com)
1.异或和之和 - 蓝桥云课 (lanqiao.cn)
参考题解:
蓝桥杯真题讲解:异或和之和 (拆位、贡献法)-CSDN博客
洛谷P9236 [蓝桥杯 2023 省 A] 异或和之和 题解_c加加区间异或问题洛谷ir-CSDN博客
说明:
1.需要知道一个重要的结论(图片来自参考题解):
注:为什么A^B=C可以得到B^C=A ?在原式上两边同时异或上一个B,根据异或的性质,B^B=0,与0异或等于本身。
2.那么由前缀和可以得出
(sum(j,i)为i和j这个区间上面的异或和,右下角第二排的式子等号两边同时异或上一个s[j-1]得到第一排的式子):
3.从推出的这个式子来看,sum[i,j]=s[i]^s[j-1],(i右端点,j左端点)
说明任意一个区间上面的异或和都可以转化成两个异或前缀和的异或和。再考虑到,对于一个二进制位来说,异或和结果为1的时候才会对结果有影响(贡献),而奇数个1异或为1,偶数个为0,对应到这里的两个数(前缀和)异或,那么就是一个前缀和为0,一个为1,那么把n个数都进行拆位,就可以 对每一个二进制位 做操作数是0或1(只有拆成二进制的0和1才能直接用前面的结论)的异或位运算。
于是统计,在第k位(从0开始数)上,n个数中对应前缀和为0、1的数量,记为n0,n1,那么最后在这一位上的对结果的贡献就是n0*n1* 。
这里注意:需要把S[0]考虑进来,左端点位置为1的时候计算区间需要s[0] ,而S[0]为0 ,所以0的初始数量为1
为什么会是n0 * n1 * ?因为n0是前缀和为0的数量,n1是前缀和为1的数量,我们在n0个位置里面选一个,再在n1个位置里选一个,他们计算出来的区间异或和sum(i,j)是为1的,且这个sum(i,j)不重复,因为你计数的0和1的位置是不重复的,那么计算出来的sum(i,j)的至少由一个端点跟别的sum不一样,那么n0*n1是sum(i,j)为1的个数,乘上这一位上的基数即可。
4.另一种思路:
在参考题解第二个文章里,提出了另一种思路,既然
对于一个二进制位来说,异或和结果为1的时候才会对结果有影响(贡献),而奇数个1异或为1,偶数个为0
那么我统计我当前位置是出现1的奇数次还是偶数次,根据
sum[i,j]=s[i]^s[j-1]
为奇数次,s[i]为1,要求s[j-1]为偶数次;
为偶数次,s[i]为0,要求s[j-1]为奇数次(即要求总的次数为奇数)。
于是很容易去找(记前面为偶数次的 位置数 为 even,奇数次为odd):
s[i]为奇数次,是不是就有 even+1个 为奇数次1 的区间?(因为这even个偶数次的 位置都可以作为s[j-1]的这个j-1位置,还有s[0]=0,0也是偶数次,这个没被计数到,(1,i)也是一个奇数个的区间,所以还要加1)
s[i]为偶数次,是不是就有 odd个 为奇数次1 的区间,因为是要求s[j-1]为奇数次,所以不加1.
或者可以这样考虑:
s[i]为奇数次,even个前面为偶数次的 位置,这些位置第一次出现对应的数肯定是1,且这个1只出现一次(对应这个偶数),否则1的数量就变了,0可以出现无数次,那么就是对应一个偶数o,他出现的第一个位置m,a[m](假设a为第k位上,这n个数的01序列的数组名)为1,s[m-1]肯定只出现了o-1次,这个位置不能组成合法区间,去掉。
而对于一个奇数p,第一次出现的位置r,a[r]为1,s[r-1]为偶数次p-1,需要加上这个位置。
于是合法的区间=even-出现的偶数的数量(若出现2,4,则数量为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 N=1e5+10;
int ans=0;
int a[N];
int s[N];//异或前缀和 //vector<int> num[N];
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];//ans+=a[i];s[i]=s[i-1]^a[i];}for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){int sum=s[j]^s[i-1];// sum(i,j)^s[i-1]=s[j]两百年同时异或s[i-1]消掉左边的 s[i-1]ans+=sum;}}cout<<ans;return 0;
}
说明3对应代码:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int ans=0;
int a[N];
int s[N];
//异或前缀和
int odd,even,cnt=0,radix=1;
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i]; }radix=1;for(int i=0;i<=20;i++){//这里同样注意:需要把S[0]考虑进来,左端点位置为1的时候计算区间需要s[0] ,而S[0]为0 //所以0的初始数量为1 int n0=1,n1=0;for(int j=1;j<=n;j++){//求第i位上的二进制前缀和 s[j]=s[j-1]^(a[j]&1);if(s[j]==1){n1++;} else{n0++;}a[j]=a[j]>>1;}ans+=n0*n1*radix;radix=radix<<1;}cout<<ans;return 0;
}
说明4对应代码:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int ans=0;
int a[N];
int s[N];
//异或前缀和
int odd,even,cnt=0,radix=1;
signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}// 对二进制的21个位置中的第j个位置算n个数的贡献 //注意:是 0-20位!!!有21个位置 for(int j=0;j<=20;j++){cnt=0;odd=0,even=0;//对第i个数而言,它的二进制形式的第j位(从0开始数),能找到的能贡献1的区间数,//这个区间是i和前i个数组成的。有多少个能贡献1的区间在第i位上结果就加上多少个1 (最后结果要乘上第j位对应的基数:2的j次方) for(int i=1;i<=n;i++){//对n个数计算第j位上的异或和之和 //注意:取出最后一位的方法 int tt=a[i]&1;//取出二进制位 if(tt==1){//计算二进制第j位上,到第i个数是出现了几个1,用前缀和累加可以在O(1)复杂度计算出 s[i]=s[i-1]+1;}else{s[i]=s[i-1];}if(s[i]%2==0){//到第i数出现了偶数个1,那么他能找到 前i项中为奇数次的数量 个贡献1的区间 even++;ans+=(odd)*radix;//注意乘上第j位对应的基数 }else{//到第i数出现了奇数个1,那么他能找到 前i项中为偶数次的数量+1 个贡献1的区间 odd++;ans+=(even+1)*radix;}a[i]=a[i]>>1;//第i个数左移一位,方便下一次取j+1位 }radix=radix<<1;//j+1位,基数变成原来的2倍 }// for(int i=1;i<=n;i++){
// for(int j=i;j<=n;j++){
// int sum=s[j]^s[i-1];// sum(i,j)^s[i-1]=s[j]两百年同时异或s[i-1]消掉左边的 s[i-1]
// ans+=sum;
// }
// }cout<<ans;return 0;
}
相关文章:
蓝桥杯23年第十四届省赛-异或和之和|拆位、贡献法
题目链接: 蓝桥杯2023年第十四届省赛真题-异或和之和 - C语言网 (dotcpp.com) 1.异或和之和 - 蓝桥云课 (lanqiao.cn) 参考题解: 蓝桥杯真题讲解:异或和之和 (拆位、贡献法)-CSDN博客 洛谷P9236 [蓝桥杯 2023 省 A]…...
Unity进阶之路(1)回顾与思考
首先呢,博主在这里先反思一下自己这几个月,其实并没有多少进步。 在寒假中,博主几乎是独立编写了一个小程序的完整UI和一个Uniapp的雏形。那段时间是博主生产力最高的时间段。几乎是每天8点起来开始编写代码,晚上一直忙到很晚。 …...
【C语言】——指针八:指针运算笔试题解析
【C语言】——指针八:指针运算笔试题解析 一、题一二、题二三、题三四、题四五、题五六、题六七、题七 一、题一 //程序输出结果是什么 int main() {int a[5] { 1,2,3,4,5 };int* ptr (int*)(&a 1);printf("%d, %d", *(a 1), *(ptr - 1));return…...
JVM字节码与类的加载——class文件结构
文章目录 1、概述1.1、class文件的跨平台性1.2、编译器分类1.3、透过字节码指令看代码细节 2、虚拟机的基石:class文件2.1、字节码指令2.2、解读字节码方式 3、class文件结构3.1、魔数:class文件的标识3.2、class文件版本号3.3、常量池:存放所…...
小程序如何通过公众号发送新订单提醒
当客户在小程序上下单后,公众号会发送订单通知,这可以让管理员及时获知用户下单情况,方便及时处理订单和提供服务。下面是具体介绍如何设置公众号来发送订单服务通知。 方式一:通过采云公众号发送订单通知 此种方式是默认的通知…...
聊聊公众号最让我不爽的两个痛点
本文首发于 Python猫 微信公众号最让我不爽的地方有两个,而且有很多人虽然也不爽,却不知道原因。 本文想聊聊公众号的两个痛点,因为我经常收到私信问这两个问题,本文算是一次集中的回复吧。 第一个不爽的点是公众号会屏蔽外链&…...
【leetCode】2810. 故障键盘
文章目录 [2810. 故障键盘](https://leetcode.cn/problems/faulty-keyboard/)思路一:模拟代码:思路二:双端队列代码: 2810. 故障键盘 思路一:模拟 用StringBuilder来拼贴字符遍历字符串,如果遇到i,对拼贴好…...
xshell7连接ubuntu18.04
🎡导航小助手🎡 1.查看ubuntu IP2.开启openssh-server3.静态IP设置4.Xshell连接 1.查看ubuntu IP 输入下面命令查看IP ifconfig -a可以看到网卡是ens33,IP为192.168.3.180。 2.开启openssh-server 1、执行下句,下载SSH服务 s…...
真正的力量:实力与人际关系的平衡艺术
在当今社会,人们常常在追求个人发展和建立良好人际关系之间寻找平衡。有一种观点认为,“没有实力,就不要对别人好。不然,很容易被定义为讨好。”这句话在一定程度上揭示了实力与人际关系之间的微妙联系。本文将探讨这一观点的深层…...
Acwing.1388 游戏(区间DP对抗思想)
题目 玩家一和玩家二共同玩一个小游戏。 给定一个包含 N个正整数的序列。 由玩家一开始,双方交替行动。 每次行动可以在数列的两端之中任选一个数字将其取走,并给自己增加相应数字的分数。(双初始分都是 0分) 当所有数字都被…...
Numpy数组转换为csv文件
参考:Converting Numpy Array to CSV 在数据分析和处理中,经常会涉及到将数据从一个形式转换为另一个形式的操作。 其中,将Numpy数组转换为csv文件是一种常见的操作,因为csv文件是一种通用的数据存储格式,方便与其他软…...
替代安全指标(Surrogate Safety Measures (SSM) )
替代安全措施(Surrogate Safety Measures (SSM) )用于从数据中寻找接近碰撞,或可能发生(但实际没有发生)的碰撞事件。 SSM的两个合格标准: (1)它应该来自与碰撞直接相关的交通冲突&…...
usb_camera传输视频流编码的问题记录!
前言: 大家好,今天给大家分享的内容是,一个vip课程付费的朋友,在学习过程中遇到了一个usb采集的视频数据流,经过ffmpeg编码,出现了问题: 问题分析: 其实这个问题不难,关键…...
Linux安装nginx保姆级教程
文章目录 前言一、nginx安装(保姆级教程)1.安装nginx依赖2.安装wget3.创建nginx安装目录4.下载nginx5.查看下载好的nginx6.解压缩7.查看当前目录下的文件→进入nginx-1.8.0目录→查看当前目录下的文件8.安装nginx9.查看nginx安装目录并启动nginx10.网络请…...
leetcode-判断二分图
. - 力扣(LeetCode) 存在一个 无向图 ,图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph ,其中 graph[u] 是一个节点数组,由节点 u 的邻接节点组成。形式上,…...
算法day30 回溯6
332 重新安排行程 给你一份航线列表 tickets ,其中 tickets[i] [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。 所有这些机票都属于一个从 JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK …...
分享three.js实现乐高小汽车
前言 Web脚本语言JavaScript入门容易,但是想要熟练掌握却需要几年的学习与实践,还要在弱类型开发语言中习惯于使用模块来构建你的代码,就像小时候玩的乐高积木一样。 应用程序的模块化理念,通过将实现隐藏在一个简单的接口后面&a…...
gpt的构造和原理
gpt是序列预测模型。 问答是通过确定问答格式样本训练出来的!比如“Q:xxxx.A:xxx"本质还是根据前面的序列预测后面的序列。在自回归训练过程中,文本序列(可能包含问题和紧随其后的答案)被视为一个整体输入到模型…...
基于springboot实现教师人事档案管理系统项目【项目源码+论文说明】计算机毕业设计
基于springboot实现IT技术交流和分享平台系统演示 摘要 我国科学技术的不断发展,计算机的应用日渐成熟,其强大的功能给人们留下深刻的印象,它已经应用到了人类社会的各个层次的领域,发挥着重要的不可替换的作用。信息管理作为计算…...
K8S之Job和CronJob控制器
这里写目录标题 Job概念适用场景使用案例 CronJob概念适用场景使用案例 Job 概念 Job控制器用于管理Pod对象运行一次性任务,例如:对数据库备份,可以直接在k8s上启动一个mysqldump备份程序,也可以启动一个pod,这个pod…...
基于SSM的基于个人需求和地域特色的外卖推荐系统(有报告)。Javaee项目。ssm项目。
演示视频: 基于SSM的基于个人需求和地域特色的外卖推荐系统(有报告)。Javaee项目。ssm项目。 项目介绍: 采用M(model)V(view)C(controller)三层体系结构&…...
哈佛大学商业评论 --- 第三篇:真实世界中的增强现实
AR将全面融入公司发展战略! AR将成为人类和机器之间的新接口! AR将成为人类的关键技术之一! 请将此文转发给您的老板! --- 本文作者:Michael E.Porter和James E.Heppelmann 虽然物理世界是三维的,但大…...
华为ICT七力助推文化产业新质生产力发展
创新起主导作用的新质生产力由新劳动者、新劳动对象、新劳动工具、新基础设施等四大要素共同构成,符合新发展理念的先进生产力质态;具有高科技、高能效、高质量等三大突出特征。而通过壮大新产业、打造新模式、激发新动能,新质生产力能够摆脱…...
FastGpt流程
1.知识库 引入文本——>数据清洗 最好将pdf/ppt/xx转换成文本,在文本里面进行数据清洗(以防知识库删除后,数据清洗失效) 可以插图,将图片通过网页检查F12查看路径放进去 或者直接在csdn放,直接复制链接…...
怎么在UE游戏中加入原生振动效果
我是做振动触感的。人类的五感“视听嗅味触”,其中的“触”就是触觉,是指皮肤、毛发与物体接触时的感觉。触感可以带来更加逼真的沉浸式体验。但也许过于司空见惯,也是习以为常,很多人漠视了触感的价值。大家对触感的认知还远远不…...
【Hadoop技术框架-MapReduce和Yarn的详细描述和部署】
前言: 💞💞大家好,我是书生♡,今天的内容主要是Hadoop的后两个组件:MapReduce和yarn的相关内容。同时还有Hadoop的完整流程。希望对大家有所帮助。感谢大家关注点赞。 💞💞前路漫漫&…...
蓝桥杯刷题 前缀和与差分-[3507]异或和之和(C++)
题目描述 给定一个数组 Ai,分别求其每个子段的异或和,并求出它们的和。 或者说,对于每组满足 1≤L≤R≤n 的 L,R求出数组中第 L 至第 R 个元素的异或和。 然后输出每组 L,R 得到的结果加起来的值。 输入格式 输入…...
background背景图参数边渐变CSS中创建背景图像的渐变效果
效果:可以看到灰色边边很难受,希望和背景融为一体 原理: 可以使用线性渐变(linear-gradient)或径向渐变(radial-gradient)。以下是一个使用线性渐变作为背景图像 代码: background: linear-gradient(to top, rgba(255,255,255,0)…...
『大模型笔记』吴恩达:AI 智能体工作流引领人工智能新趋势
吴恩达:AI 智能体工作流引领人工智能新趋势 文章目录 一. 概述二. AI 智能体的设计模式2.1. 反思(Reflection)2.2. 使用工具(Tool use)2.3. 规划(Planning)2.4. 多智能体协作(Multi-agent collaboration)三. 最后总结四. 参考文献一. 概述 我期待与大家分享我在 AI 智能体方面…...
腾讯光子工作室群 一面 (30min)
问题: 你毕业是打算考研还是直接工作 深挖项目(介绍、剖析遇到问题如何解决): 你在进行攻击的时候会不会有穿模的情况,怎么解决 为什么会造成卡顿(多嘴说的) 说说行为树和状态机之间的差别 …...
中山网站优化/百度客户端手机版
线段树出了名的操作是lazy标记。 普通lazy标记涉及到pushup和pushdown 这个pushup只涉及两个儿子合并,并且两个儿子是两个点。 但是有的时候,两个儿子是两个树,pushup复杂度就爆炸了。 给你一个线段树的树套树,外层的线段树pushup…...
一起做网店网站入驻收费/网站关键词排名查询工具
普通的英文半角空格   no-break space (普通的英文半角空格但不换行) 中文全角空格 (一个中文宽度)   en空格 (半个中文宽度)   em空格 (一个中文宽…...
大学生个人网站怎么做/网络媒体软文案例
数据扩展(data extent)数据扩展是为存储数据而分配的一组连续的数据块。段分配空间的时候总是以extent为单位来分配的。在创建一个段时,指定一个initial extent,即初始数据扩展,当初始扩展中的数据块已经装满,且有新数据插入需要空…...
企业网站如何部署/合肥seo快排扣费
微信扫码,直接进入部落窝教育微课堂如果你经常用PS修图的话,对于蒙版想念应该并不陌生。但是,你知道吗?PPT中同样也有蒙版。当图片清晰度不高时;当图片不能直观的反映所对应的文字内容,即影响了内容传达时&…...
php网站怎么做的/最知名的网站推广公司
Struts2常用标签总结 一 介绍 1.Struts2的作用 Struts2标签库提供了主题、模板支持,极大地简化了视图页面的编写,而且,struts2的主题、模板都提供了很好的扩展性。实现了更好的代码复用。Struts2允许在页面中使用自定义组件&…...
长春哪家网络公司做网站专业/十大跨界营销案例
PS:使用if判断时,需要在判断结束处填入"fi",表示if语句块的结束 例如: if [ $ACTION "add"]then... ...;else... ...;fi在整数中比较使用如下 //-eq 等于(equal) if [ "$a" -eq "$b" ] //-ne不等于(no equal) if [ "…...