当前位置: 首页 > ds >正文

[蓝桥杯 2025 省 Python B] 异或和

暴力(O(n^2)):

def xor_sum(n, arr):total = 0for i in range(n):for j in range(i + 1, n):total += (arr[i] ^ arr[j]) * (j - i)return total# 主函数
if __name__ == "__main__":n = int(input())arr = list(map(int, input().split()))print(xor_sum(n, arr))

只能通过部分示例

单独处理 k,前缀和优化“(j - i)”:

        

大规模数据(按位分治 + 前缀和优化), 根据全部测试用例的提示:
对于所有评测用例,1 ≤ n ≤ 10**5 ,1 ≤ ai ≤ 2**20    
必须将复杂度优化到 O(n log A)  ≈  O(n * 20)      -- A ≈ 2²⁰def xor_weighted_sum(n, a):MAX_BITS = 20ans = 0for k in range(MAX_BITS):  # 遍历每一位(最多 20 位)cnt_0 = 0cnt_1 = 0pos_sum_0 = 0pos_sum_1 = 0for i in range(n):bit = (a[i] >> k) & 1if bit == 0:# 当前是0,贡献 = 前面所有为1的位置之和 - (数量 * 当前索引)contrib = cnt_1 * i - pos_sum_1else:# 当前是1,贡献 = 前面所有为0的位置之和 - (数量 * 当前索引)contrib = cnt_0 * i - pos_sum_0ans += contrib << k  # 每一位贡献乘上 2^k# 更新状态if bit == 0:cnt_0 += 1pos_sum_0 += ielse:cnt_1 += 1pos_sum_1 += ireturn ans# 主程序
if __name__ == "__main__":n = int(input())a = list(map(int, input().split()))print(xor_weighted_sum(n, a))

http://www.xdnf.cn/news/1434.html

相关文章:

  • 2025-04-23 Python深度学习3——Tensor
  • 设计模式之策略模式
  • 富文本编辑器实现
  • C++ STL 容器简介(蓝桥杯适用精简版)
  • 解决报错:this[kHandle] = new _Hash(algorithm, xofLen);
  • Java面试题汇总
  • CSS-跟随图片变化的背景色
  • 【Java学习笔记】选择结构
  • 4月23日作业
  • 聊聊自动化用例的维护
  • Java 实现单链表翻转(附详细注释)
  • PH传感器详解(STM32)
  • 配置kafka与spark连接
  • 标题:掌握 PowerShell 防火墙管理:C# 中的高效操作指南
  • Kafka 核心使用机制总结
  • vue实现静默打印pdf
  • Redis 详解:安装、数据类型、事务、配置、持久化、订阅/发布、主从复制、哨兵机制、缓存
  • 华为AR1200 telnet设置
  • zkPass案例实战之合约篇
  • 使用react的ant-design-pro框架写一个地图组件,可以搜索地图,可以点击地图获取点击的位置及经纬度
  • 彻底禁用windows的语音识别快捷键win+ctrl+s
  • 【计算机视觉】CV项目实战- SORT 多目标跟踪算法
  • 融山科技前端面经
  • Fabric.js 设置画布背景
  • OpenCV 图形API(57)颜色空间转换-----将图像从 RGB 色彩空间转换为 YUV 色彩空间函数RGB2YUV()
  • Ragflow、Dify、FastGPT、COZE核心差异对比与Ragflow的深度文档理解能力​​和​​全流程优化设计
  • python后端程序部署到服务器 Ubuntu并配合 Vue 前端页面运行
  • 【CSS】层叠,优先级与继承(四):层叠,优先级与继承的关系
  • 电液伺服高频应力腐蚀疲劳试验机
  • 长连接、短连接与WebSocket的基本知识