CF1764G1 题解
2024-10-21 06:44:58
题意
交互库有一个 \([1,n]\) 的排列 \(p\),你可以询问 \(l,r,k\),交互库会返回 \(\lfloor\dfrac{p_l}{k}\rfloor,\lfloor\dfrac{p_{l+1}}{k}\rfloor,\dots,\lfloor\dfrac{p_r}{k}\rfloor\) 中不同数的个数。你需要在 \(30\) 次询问内找到 \(p\) 中 \(1\) 的位置。
\(n\in[3,1024]\)。
题解
好交互题!
我们发现很难从询问中得出信息,于是观察一些特殊的 \(k\)。当 \(k\) 为 \(n\) 时,若区间包含 \(n\) 则为 \(2\),否则为 \(1\)。于是可以二分出 \(n\)。
但这种方式难以推广到其他 \(k\)。想一下 \(n\) 的特殊之处:其除 \(n\) 取下整的值唯一。而 \(1\) 除 \(2\) 取下整的值也唯一。
于是对于 \(i\in[1,n]\),考虑 \(Q(1,i,2)-Q(1,i-1,2)\) 与 \(Q(i,n,2)-Q(i+1,n,2)\)。不难发现若 \(p_i=1\),二者均为 \(1\);否则必然一者为 \(1\),一者为 \(0\)。
上面是差分形式,前缀和即为 \(Q\)。于是可以二分,每次查询前缀和,找到第一个二者均为 \(1\) 的位置。这里需要 \(2\log n\) 次。
注意到上面的分析忽略了 \(n\) 为偶数的情形,此时 \(n\) 的位置二者也均为 \(1\)。上面我们提到了 \(\log n\) 找 \(n\) 的方法,于是将 \(n\) 的贡献处理掉即可。总查询次数 \(3\log n\)。
最新文章
- C#开发微信门户及应用(25)-微信企业号的客户端管理功能
- WinForm常用属性
- 修改mysql密码
- velocity-tools-beta1.jar与velocity-tools.jar不兼容
- java 25 - 3 网络编程之 Socket套接字
- [20150522]RPM包的管理
- JSoup——用Java解析html网页内容
- 创建ArcGIS API for JavaScript的第一个示例程序
- 转:printf打印输出2进制
- linux强大IDE——Geany配置说明
- centos 6.X 安装node
- js框架——angular.js
- phpExcel读取excel文件数据
- android 开发中,经常遇到http://dl-ssl.google.com/ 无法访问的问题解决
- Dictionary实现先进先出代替Queue
- 新年Flag,零基础程序媛编程学习计划(持续更新ing)~~
- DenseNet 论文阅读笔记
- Log4j使用笔记
- C++11 并发指南四(<;future>; 详解三 std::future &; std::shared_future)
- ContextMune上下文菜单中,二级菜单获取及状态设置
热门文章
- python循环结构之while循环
- 面对集中式缓存实现上的挑战,Redis交出的是何种答卷?聊聊Redis在分布式方面的能力设计
- [Leetcode]环形链表 II
- MQ系列11:如何保证消息可靠性传输(除夕奉上)
- MySQL 字符串长度 char_length、length
- django框架之drf:3、API执行流程、Response源码剖析、序列化器的简介和使用、反序列化的校验
- Failed to execute goal org.apache.maven.plugins:maven-resources-plugin:3.1.0
- Quartz.Net 官方教程 Tutorial 1/3(Jobs 和 Trigger)
- File、FileReader、Base64、Blob基本使用以及Buffer、ArrayBuffer之间的转换
- SpringCloud 消费请求Eureka调用服务提供者报错