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

2025.10.23 闲话-全局位运算 max 的解法

2025.10.23 闲话-全局位运算 \(max\) 的解法

三部分将使用不同的策略求解。

Part.1 \(xor-max\)

这一类问题算是最简单的,每次插入一个数,在 \(Trie\) 树上跳,先查询这个数产生的最大值。

查询时如果当前位是 \(o\) 则优先向 \(!o\) 跳,再向 \(o\) 跳,容易证明一定是最优的(\(o\oplus(!o)=1\), \(o\oplus o=0\))。

查询完后直接插入 \(Trie\) 树即可。

复杂度 \(O(n\log V)\)

Part.2 \(and-max\)

这类问题就比较困难了。

因为如果当前位是 1,那么可以大胆的跳 1,然后跳 0。

可是如果当前位是 0,就比较棘手了,因为可以跳 1,也可以跳 0,没有先后顺序,复杂度很容易变得很劣。

这时发现一件事,当前位是 0 时,如果 1 有两个或以上的点经过,那么这两个点一定会与出更优的答案,那么当前这个点就不用去遍历 1 的子树了!

那么只可能有一个点经过 1 时才搜,这时复杂度是 \(O(\log V)\) 的。

总复杂度就是 \(O(n\log^2 V)\),实测效率趋近较大常数 \(O(n\log V)\)

另一种做法是暴力合并......这也是对的......(好像被创飞了😭😭😭😭😭😭😭😭😭😭😭😭😭😭)

又精心思考了一下,发现其实暴力合并和这个做法的本质是相同的。

Part.3 \(or-max\)

我不会,求教。

http://www.hskmm.com/?act=detail&tid=37557

相关文章:

  • 习题-无限集与选择公理
  • Error: [WinError 10013] 以一种访问权限不允许的方式做了一个访问套接字的尝试及其解决方法
  • 项目管理软件是不是伪需求?
  • 题解:CF2115F1 Gellyfish and Lycoris Radiata (Easy Version)
  • 低代码如何重塑IT部门价值?
  • LIS 略解
  • 低代码如何引爆全员创新?揭秘技术民主化背后的蒲公英效应
  • LLM学习笔记DAY10
  • 2025工业冰水机/冷水机厂家推荐东莞市凯诺机械,高效制冷稳定运行
  • 2025小型低温/工业/风冷/一体式螺杆冷冻机厂家推荐:东莞凯诺机械专业制冷解决方案
  • 2025水冷螺杆/风冷螺杆冷水机厂家推荐东莞市凯诺机械,高效制冷稳定可靠
  • LLM学习笔记DAY9
  • OJ模拟面试3(异步判题架构)
  • Edge浏览器网页设置深色模式(仅搜索结果界面)
  • 2025 年 AI 编程工具 TOP5 排名:谁在重新定义研发效率?
  • noipd8t2 - Slayer
  • 【Go】go学习笔记
  • todolist
  • 利用排列组合法实现TOPN路径计算
  • 达梦数据库获取判断字段中的json数据中的值
  • 2025 废气处理/废气治理/环保/污水/分子筛/除臭设备推荐榜:上海深城以专利技术破局,3 家企业凭场景适配登榜,助力异味治理升级
  • Web3 行业 Solidity 高级后端开发工程师岗位要求
  • API 搜索的下一代形态-Apipost智能搜索:只需用业务语言描述需求,就能精准定位目标接口!
  • 2025包装机/全自动包装机/非标定制生产线厂家推荐昆仑智能装备,专业高效!
  • 2025拖鞋机/酒店拖鞋生产线厂家推荐昆仑智能,高效稳定自动化解决方案
  • 2025年口罩机厂家权威推荐榜单:全自动口罩机器,全自动KN95口罩机,高效智能生产线专业选购指南
  • 2025提升机/自动提升机厂家推荐垚林机械,高效稳定省心之选
  • 二分图
  • 2025不锈钢方形/消防/生活/保温水箱厂家推荐莞南节能,专业耐用品质保障
  • 2025-10-23 DeepSeek R1本地部署(ollama)