首页 > 其他分享 >CF1764G1 题解

CF1764G1 题解

时间:2023-03-03 20:57:04浏览次数:55  
标签:lfloor log 题解 CF1764G1 rfloor dfrac 交互

题意

传送门

交互库有一个 \([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\)。

标签:lfloor,log,题解,CF1764G1,rfloor,dfrac,交互
From: https://www.cnblogs.com/FishJokes/p/17176931.html

相关文章

  • lg7335 [JRKSJ R1] 异或 题解
    本题的标签中含有trie,但是这道题可以不用trie做。考虑列出本题的dp方程:设\(f_{k,i}\)表示前\(i\)个数选了\(k\)段的答案,\(s_i\)为数组的前缀异或和当不选择第\(i\)位,使用......
  • 【题解】P6271 [湖北省队互测2014]一个人的数论
    很久之前存的古代经典题,思路是cyj的。感谢那时候先辈们的分享精神,这就是十年前的OI圈子吗。思路莫比乌斯反演。首先注意到一个自然数幂次和,令\(F(n)=\sum\limit......
  • 前端问题解决步骤
    总结,有错误看错误,没明显错误看逻辑。F12查看(看连接是否有错误。)在看NetWork查看选项Fetch/XHR(看具体接口对应相关数据是否正确)找后端代码和前端代码的逻辑问题。(swagg......
  • pdf.js 预览时红章、电子签和部分文字无法显示问题解决方案
    pdf红章无法预览的问题修复方案:node_modules/pdfjs-dist/es5/build/pdf.worker.js注释一行代码:this.setFlags(_util.AnnotationFlag.HIDDEN)pdf电子签、部分文字不......
  • lg8935 [JRKSJ R7] 茎 题解
    由于标签内包含背包和树形dp,所以考虑用背包dp和树形dp求解。考虑每次合并2个连通块(一个包含根节点),设\(f_{i,j}\)表示\(i\)子树内,操作\(j\)次的方案数(未合并连通块),设\(f_{i......
  • [已解决]Android studio连接远程MySQL问题解决
    我电脑安装的是8.0的MySQL,导入使用的jar包是mysql-connector-java-5.0.71、首先先按照大佬的链接配置好一些东西,注意!已经安装8.0版本MySQL的保持原样就行,不用重新安装5.0......
  • istio 常见问题解决
    1.Commanderroroutput:xtablesparameterproblem:iptables-restore:unabletoinitializetable'nat'  Failedtoexecute:iptables-restore--noflush/tmp/i......
  • Everything 搜索失败问题解决
    平时用的好好的Everything突然某一天用不了了,什么东西都搜不出来了……就搜桌面上摆着的文件都搜不出来……下文介绍下我的解决方案解决方案任务栏找到Everything......
  • HBase存储空间撑爆导致拒绝服务的问题解决思路与操作方法记录
    时间:2022年3月29日;问题:tmss数据源切换完成后,源表数据将HBase集群内节点的存储空间撑爆,导致HBase集群内节点拒绝服务;修复:查询HDFS占用空间情况:hdfsdfs-df-h;确认是否......
  • ARC_C题解
    ARC009C错排数\(\times{C(n,k)}\)错排数可以用递推公式:\(D_n=(n-1)\times(D_{n-1}+D_{n-2})\)。具体的原理是考虑\(1\)这个位置是第几个元素填的,假设是\(k\)。分为两种情......