【洛谷】P9236 [蓝桥杯 2023 省 A] 异或和之和
题目链接
P9236 [蓝桥杯 2023 省 A] 异或和之和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路
1. 暴力求解
直接枚举出所有子数组,求每个子数组的异或和,再对所有的异或和求和
枚举所有子数组的时间复杂度为O(N^2),求每个子数组的异或和又要遍历一次数组,所以总的时间复杂度为O(N^3)
2. 优化
异或中有这么一个性质:a ^ b ^ b = a,即两个相同元素异或后为0,此性质推广到子数组同理
因此我们可以用前缀和的思想来快速得出一个区间的异或和。
此时可以将时间复杂度优化为O(N^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;
}
讲的不够清楚也请大家多多见谅,有错误或问题可以在评论区指出。
相关文章:
【洛谷】P9236 [蓝桥杯 2023 省 A] 异或和之和
题目链接 P9236 [蓝桥杯 2023 省 A] 异或和之和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 思路 1. 暴力求解 直接枚举出所有子数组,求每个子数组的异或和,再对所有的异或和求和 枚举所有子数组的时间复杂度为O(N^2)&…...
ThreadLocal加切面实现线程级别的方法缓存
1、实现效果 当一个请求线程多次请求A方法时,只会触发一次A方法的实际调用,会将方法结果缓存起来,避免多次调用。 2、实现过程 1. 需要一个注解ThreadLocalCache,在需要缓存的方法上加上该注解 2. 需要一个切面,借助ThreadLocal,将结果缓存起来,利用环绕通知来实现方法拦截从…...
使用 Flume 将 CSV 数据导入 Kafka:实现实时数据流
使用 Flume 将 CSV 数据导入 Kafka:实现实时数据流 文介绍了如何使用 Apache Flume 将 CSV 格式的数据从本地文件系统导入到 Apache Kafka 中,以实现实时数据流处理。通过 Flume 的配置和操作步骤,我们可以轻松地将数据从 CSV 文件中读取并发…...
对代理模式的理解
目录 一、前言二、案例1 代码2 自定义代理类【静态代理】2.1 一个接口多个实现,到底注入哪个依赖呢?2.1.1 Primary注解2.1.2 Resource注解(指定name属性)2.1.3 Qualifier注解 2.2 面向接口编程2.3 如果没接口咋办呢?2.…...
#QT项目实战(天气预报)
1.IDE:QTCreator 2.实验: 3.记录: (1)调用API的Url a.调用API获取IP whois.pconline.com.cn/ipJson.jsp?iphttp://whois.pconline.com.cn/ipJson.jsp?ip if(window.IPCallBack) {IPCallBack({"ip":&quo…...
数据挖掘|关联分析与Apriori算法详解
数据挖掘|关联分析与Apriori算法 1. 关联分析2. 关联规则相关概念2.1 项目2.2 事务2.3 项目集2.4 频繁项目集2.5 支持度2.6 置信度2.7 提升度2.8 强关联规则2.9 关联规则的分类 3. Apriori算法3.1 Apriori算法的Python实现3.2 基于mlxtend库的Apriori算法的Python实现 1. 关联分…...
ChatGPT Excel 大师
原文:ChatGPT Excel Mastery 译者:飞龙 协议:CC BY-NC-SA 4.0 序言 欢迎来到 Excel 掌握的变革之旅,在这里,尖端技术和永恒专业知识在“ChatGPT Excel 掌握:释放专家技巧和窍门的力量”中融合。在当今快节…...
C 语言中的 end, _end 符号
使用 man 3 end 可以看到相关符号的解释 这些符号不是在 C 语言文件和头文件中定义的,它们是 ld 在链接所有 .o 文件的时候自己添加的。 end 和 _end 的地址,就是最终程序的堆的起始地址 要打印它们的话,一个样例程序在下面: …...
绿联 安装PDF工具
这是一个强大的本地托管的基于 Web 的 PDF 操作工具,使用 docker,允许您对 PDF 文件执行各种操作,例如拆分、合并、转换、重组、添加图像、旋转、压缩等。这个本地托管的 Web 应用程序最初是 100% ChatGPT 制作的应用程序,现已发展…...
备战蓝桥杯---数论相关问题
目录 一、最大公约数和最小公倍数 二、素数判断 三、同余 四、唯一分解定理 五、约数个数定理 六、约数和定理 五、快速幂 六、费马小定理 七、逆元 一、最大公约数和最小公倍数 文章链接:最大公约数和最小公倍数 二、素数判断 文章链接:在J…...
苹果手表Apple Watch录了两个半小时的录音,却只能播放4秒,同步到手机也一样,还能修复好吗?
好多人遇到这个情况,用苹果手表Apple Watch录音,有的录1个多小时,有的录了3、4小时,甚至更长时间,因为手表没电,忘记保存等原因造成录音损坏,都是只能播放4秒,同步到手机也一样&…...
RGB三通道和灰度值的理解
本文都是来自于chatGPT的回答!!! 目录 Q1:像素具有什么属性?Q2:图像的色彩是怎么实现的?Q3:灰度值和颜色值是一个概念吗?Q4:是不是像素具有灰度值,也有三个颜色分量RGB?Q5:灰度图像是没有色彩的吗?Q6: 彩色图像是既具有灰度值也具有RGB三…...
ARM、X86、RISC-V三分天下
引入: 简单的介绍一下X86、ARM、RISC-V三种cpu架构的区别和应用场景。 目录 简单概念讲解 1. X86架构 2. ARM架构 3. RISC-V架构 应用场景 X86、ARM和RISC-V是三种不同的CPU架构,它们在设计理念、指令集和应用场景上有一些区别。 简单概念讲解 1. X…...
力控机器人原理及力控制实现
力控机器人原理及力控制实现 力控机器人是一种能够感知力量并具有实时控制能力的机器人系统。它们可以在与人类进行精准协作和合作时,将力传感技术(Force Sensing Technology)和控制算法(Control Algorithm)结合起来&a…...
最小生成树
最小生成树问题是指给定一个带权的无向图,删除一些边使得这个无向图变成一棵树,并且权值之和最小。 解决此类问题的方法主要有两种:Prim算法,Kruskal算法 Prim 算法 从一个点开始,逐步扩展,每次选择权值…...
二维动画制作软件 Animate 2024 for mac激活版
Animate 2024 for Mac是一款功能强大的二维动画制作软件,专为Mac用户打造。它提供了丰富的动画编辑功能,使用户能够轻松创建出生动逼真的动画作品。无论是短片、广告还是游戏等应用领域,Animate 2024都能发挥出出色的表现。 软件下载…...
相对论中关于光速不变理解的补充
近几个月在物理直播间聊爱因斯坦相对论,发现好多人在理解爱因斯坦相对论关于基本假设,普遍认为光速是不变的,质能方程 中光速的光速不变的,在这里我对这个假设需要做一个补充,他是基于质能方程将光速C 在真是光速变化曲…...
面试(04)————JavaWeb
1、网络通讯部分 1.1、 TCP 与 UDP 区别? 1.2、什么是 HTTP 协议? 1.3、TCP 的三次握手,为什么? 1.4、HTTP 中重定向和请求转发的区别? 1.5、 Get 和 Post 的区别? 2、cookie 和 session 的区别&am…...
Debian12 使用 nginx 与 php8.2 使用 Nextcloud
最近将小服务器升级了下系统,使用了 debian12 的版本,正好试试 nginx 和 php-fpm 这种方式运行 Nextcloud 这个私有云的配置。 一、基本系统及应用安装 系统:debian12 x86_64 位版本最小安装,安装后可根据自己需求安装一些工具&…...
Java设计模式:代理模式的静态和动态之分(八)
码到三十五 : 个人主页 心中有诗画,指尖舞代码,目光览世界,步履越千山,人间尽值得 ! 在软件设计中,代理模式是一种常用的设计模式,它为我们提供了一种方式来控制对原始对象的访问。在Java中&a…...
【论文通读】AgentStudio: A Toolkit for Building General Virtual Agents
AgentStudio: A Toolkit for Building General Virtual Agents 前言AbstractMotivationFramework评估GUI GroudingReal-World Cross-Application Benchmark Suite Conclusion 前言 来自昆仑万维的一篇智能体环境数据大一统框架工作,对未来计算机智能体的发展具有指…...
wordvect嵌入和bert嵌入的区别
Word2Vec 嵌入和 BERT 嵌入之间有几个关键区别: 训练方式: Word2Vec:Word2Vec 是一个基于神经网络的词嵌入模型,它通过训练一个浅层的神经网络来学习单词的分布式表示。它有两种训练方式:连续词袋模型(CBOW…...
渗透测试练习题解析 5(CTF web)
1、[安洵杯 2019]easy_serialize_php 1 考点:PHP 反序列化逃逸 变量覆盖 【代码审计】 通过 GET 的方式获取参数 f 的值,传递给变量 function 定义一个过滤函数,过滤掉特定字符(用空字符替换) 下面的代码其实没什么用…...
PCA(Principal Component Analysis,主成分分析)
PCA(Principal Component Analysis,主成分分析)是一种在数据分析中广泛应用的统计方法,主要用于数据降维、可视化和去噪。以下是对PCA的发展史、工作原理以及理论基础的详细解释: Principal Component Analysis 一、PC…...
干货 | 探索CUTTag:从样本到文库,实验步步为营!
CUT&Tag(Cleavage Under Targets and Tagmentation)是一种新型DNA-蛋白互作研究技术,主要用于研究转录因子或组蛋白修饰在全基因组上的结合或分布位点。相比于传统的ChIP-seq技术,CUT&Tag反应在细胞内进行,创新…...
提质不增本,降本不降质
#公益巡讲# #质量万里行# 公开课、沙龙活动...
数据结构---顺序表实现
目录 1.顺序表 2.动态顺序表的实现 (4)顺序表初始化 (5)顺序表销毁 (6)顺序表的插入 a.尾插 b.头插 (7)顺序表的删除 a.尾删 b.头删 (8)指定位置之…...
python docx 添加动态表格
在Python中,使用python-docx库可以创建Word文档并添加动态表格。以下是一个简单的例子,演示如何创建一个包含动态内容的表格: from docx import Document# 创建一个Word文档 document Document()# 添加一个标题 document.add_heading(动态表…...
git配置多SSH
目的: 一台电脑可以让github、gitee等账号同时存在,让不同账号配置不同的密钥 第一步:创建不同平台的SSH公钥 执行命令: ssh-keygen -t rsa -C "对应仓库邮箱地址" -f ~/.ssh/id_rsa.github 如果执行上面的命令&…...
IDEA连接SqlServer数据库
目录 下载jar包 下载sqljdbc_12.6压缩包 解压 导入IDEA 新建文件夹 复制粘贴进JDBC文件夹并设为library 编写类及方法 代码 下载jar包 以sqljdbc_12.6为例 下载sqljdbc_12.6压缩包 最新地址:sqljdbc 官方最新地址 解压 解压即用 导入IDEA 新建文件夹 复制…...
旅游网站排名排行榜/河南百度推广代理商
一、概述 观察者模式又叫做发布-订阅(Publish/Subscribe)模式、模型-视图(Model/View)模式、源-监听器(Source/Listener)模式或从属者(Dependents)模式。 观察者模式定义了一种一对多…...
一级页面的网站怎么做/合肥seo管理
Quartz简介 Quartz 是一种功能丰富的,开放源码的作业调度库,可以在几乎任何Java应用程序集成。Quartz可以用来创建简单或复杂的日程安排执行几十,几百,甚至是十万的作业数 - 作业被定义为标准的Java组件,可以执行几乎…...
手机网站公司/域名注册需要哪些条件
如何获取光标下的文本?因此,如果我将鼠标悬停在它上面并且单词“hi”,我可以阅读它吗?我想我需要用QTextCursor.WordUnderCursor做一些事情,但我不确定是什么.有帮助吗? 这就是我现在正在努力解决的问题: textCursor text.cursor…...
做家政有专门的网站吗/网络营销策划的方法
脉动阵列(Systolic Array)本身是一个“古老”的概念,在1982年就已经提出了,可是,最近由于Google的TPU采用了这个结构作为计算的核心结构,脉动阵列又一次地火了起来。我也是因为关注TPU才开始去了解脉动阵列…...
宜兴做网站/seo的主要内容
在Java中,把这些不同类型的输入、输出抽象为流(Stream),而其中输入或输出的数据称为数据流(Data Stream),用统一的接口来表示,从而使程序设计简单明了。首先我要声明下:所谓的输入输出都是相对内存而言的还要讲几个基本概念&#…...
怎么做网站页面代码搜索/郑州企业网站seo
解决办法1 cd /etc chown root:shadow shadow chmod ur,gr shadowhttps://blog.csdn.net/newthinker_wei/article/details/8650798 ↩︎...