首页 > 其他分享 >题解:【JROI-7】hibernal

题解:【JROI-7】hibernal

时间:2022-11-13 00:14:50浏览次数:82  
标签:一组 二进制 题解 JROI 一位 hibernal

题目链接

交互题,显然返回值为 \(1\) 时在所分的两个组中各一个,否则则在所分的同一个组中。

限制次数的题一般都从数据范围入手,可以发现最大范围 \(log_21000 \approx 9\),再看这个最大操作次数为 \(19\) 次,八成就是跑两遍相关的算法了。

考虑二进制拆分,首先将按照二进制每一位上分组,每次单独看一位,将这一位上是 \(0\) 的分在一组里面,是 \(1\) 的分在一组里面,如果不在同一组中则说明最终答案的两个下标在二进制这一位下不同,询问次数为 \(log_2n\)。

由于两个不同的数他们的二进制位上必然有一位不同,我们随便选一个不同的位,然后分成两组二分答案。具体就是始终固定一组,然后找另一组中的那一个数,因为我们知道了

标签:一组,二进制,题解,JROI,一位,hibernal
From: https://www.cnblogs.com/LittleTwoawa/p/16885159.html

相关文章

  • uView list 控件分页加载出现抖动问题解决方案
    使用u-list 组件 动态加载数据时 滑动列表元素 会出现抖动的情况解决 设置preLoadScreen为根据page的动态变换就可以了preLoadScreen 列表前后预渲染的屏数,1......
  • AtCoder Beginner Contest 277 题解
    掉大分力(悲A-^{-1}直接模拟。#include<bits/stdc++.h>#defineIOSios::sync_with_stdio(false)#defineTIEcin.tie(0),cout.tie(0)#defineintlonglongusing......
  • CSP-J2022 题解
    一、乘方\(\text{pow}\)洛谷题面我们看数据范围:对于\(100\%\)的数据,保证\(1\lea,b\le10^9\)可以轻易得知,即使没有别的限制,至少也应该用快速幂解决而这题只......
  • 洛谷P5309 Ynoi 2011 初始化 题解
    题面。我也想过根号分治,但是题目刷得少,数组不敢开,所以还是看题解做的。这道题目要用到根号分治的思想,可以看看这道题目和我的题解。题目要求处理一个数组a,支持如下操作......
  • LG3174 [HAOI2009] 毛毛虫 题解
    LG3174[HAOI2009]毛毛虫对于一棵树,我们可以将某条链和与该链相连的边抽出来,看上去就象成一个毛毛虫,点数越多,毛毛虫就越大。给定一棵树,求其最大的毛毛虫的大小。容易......
  • error in anyjson setup command: use_2to3 is invalid.问题解决
    报错errorinanyjsonsetupcommand:use_2to3isinvalid.解决因为在setuptools58之后的版本已经废弃了use_2to3pipinstallsetuptools==57.5.0......
  • 11.12 直升考 D2T2 题解
    考场上觉得人均AB,然后上午砸了,就很慌。现在还是觉得上午很砸,仍很慌。T3暴力可过??题意:给定\(n\)个格子,初始全为白色,一个人按顺序染黑一些格子,当一个格子左右的格子都被......
  • 洛谷 P4135 作诗 题解
    题面。之前做过一道很类似的题目洛谷P4168蒲公英,然后看到这题很快就想到了解法,做完这题可以对比一下,真的很像。题目要求区间内出现次数为正偶数的数字的数量。数据范......
  • 题解 P5188 【[COCI2009-2010#4] PALACINKE】
    postedon2022-07-2520:12:26|under题解|source做法:矩阵优化DP+容斥原理。矩阵优化DP先不要考虑商品,写个不管约束条件的DP。令\(f_{t,u}\)表示在\(t\)......
  • 题解 ABC270G【Sequence in mod P】
    postedon2022-10-2013:58:54|under题解|source有个地方写错了,改一下problemSoso有一个无穷序列\(\{X_i\}\)定义如下:\[X_i=\begin{cases}S,&(i=0)\\(A\cdo......