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

P14134 题解——随机化太帅了

题意

有一个 \(0 \sim n - 1\) 的排列 \(a_1 \dots a_n\),有以下两种询问:

  • 询问一个集合 \(S\),交互库返回 \(\min_{x \in S} a_x + \operatorname{mex}_{x \in S} a_x\)。(这种询问最多 \(35\) 次)
  • 询问一个集合 \(S\), 交互库返回 \(\min_{x \in S} a_x - \operatorname{mex}_{x \in S}a_x\)。(这种询问最多 \(1\) 次)

你的目标是找出 \(0\) 的位置。

特殊性质 A

序列的前一半是偶数,后一半是奇数。

那么只需在前一半里面二分,如果一个区间里面包含 \(0\),那么他的询问 1 一定返回 1。

解法

我们要意识到,询问 2 一定是用来区分 \(1\)\(0\) 的。

但是没有特殊性质时,我们的询问 1 的值或许会一样。比如 1 02 这两个集合,返回的都是 \(2\)。所以我们的首要任务就是将 \(1\)\(0\) 分到两个集合中。

确定性算法想不到,随机化算法出战。考虑随机打乱序列将其分成两个部分,如果其中一个部分的询问 1 为 \(1\),此时表明 \(1\)\(0\) 被分到了两个集合里,此时再用一次询问 2,即可区分 \(0\)\(1\)。这边的期望询问次数为 \(2\)

最后再在 \(0\) 的那个集合中二分就可以了。

询问次数 \(O(\log n) + O(1)\)

Code

#include <bits/stdc++.h>
using namespace std;int n, ans;int query(int op, vector<int> &a, int l, int r){cout << "? " << op << ' ' << r - l + 1;for(int i = l; i <= r; i++) cout << ' ' << a[i];cout << endl;int res;    cin >> res;return res;
}int main(){cin >> n;if(n == 1){cout << "! " << 1 << endl;return 0;}vector<int> a(n + 1, 0);for(int i = 1; i <= n; i++) a[i] = i;random_device rd;mt19937 g(rd());while(1){shuffle(a.begin() + 1, a.end(), g);if(query(1, a, 1, n / 2) == 1) break;}vector<int> v;if(query(2, a, 1, n / 2) == 1) v.assign(a.begin() + 1 + (n + 1) / 2, a.end());else v.assign(a.begin() + 1, a.begin() + 1 + n / 2);v.insert(v.begin(), 0);int l = 1, r = v.size() - 1;while(l <= r){int mid = (l + r) >> 1;if(query(1, v, l, mid) == 1){ans = v[mid];r = mid - 1;}else l = mid + 1;}cout << "! " << ans;return 0;
}
http://www.hskmm.com/?act=detail&tid=24742

相关文章:

  • 2025 年北京档案存放公司 升职猫档案服务平台:16 年老牌机构的合规服务与高效解决方案解析
  • 2025电容厂家最新品牌推荐排行榜白皮书,固态,高压,牛角,安规,CBB,超级,红宝石电解,螺栓,超级电容推荐这十家公司!
  • bug汇总
  • 2025石材加工厂家最新品牌推荐排行榜:大祥工艺,业务覆盖东北,辽宁盖州,专业浮雕雕刻高级技师
  • centos7升级降级内核 centos升级降级内核 centos升级内核 centos降级内核
  • Photoshop 在线网页版?是的,它来了!免费使用指南
  • 基于Python+Vue开发的母婴商城管理系统源码+运行步骤
  • 2025防火隔断品牌最新推荐排行榜:甲级防火玻璃隔断厂家深度解析,精选优质品牌助力采购决策!
  • 机器学习Day5-模型诊断 - 详解
  • 这些行业软件你用过哪个
  • 提供远程服务
  • 分享一些软件资讯
  • 2025美缝剂源头厂家最新推荐权威排行榜:深度解析五大品牌实力与选购指南
  • 2025数控铣床厂家最新企业品牌推荐排行榜, 双头数控铣床,双面数控铣床,龙门数控铣床,双侧数控铣床推荐这十家公司!
  • 2025最新推荐点胶机源头厂家权威排行榜:涵盖自动点胶机,果冻胶,无痕内衣,热熔胶类设备,助力企业精准挑选优质厂家
  • 前端开源JavaScrip库 - 详解
  • Probabilistic method小记
  • 数据生成方法初步调研
  • Elastic Stack 9.1.4 发布:重要安全更新与功能优化
  • 2025钛白粉源头厂家最新推荐排行榜:覆盖广东珠三角东莞华南深圳长三角地区的优质供应商解析
  • 完整教程:图论回溯
  • 用 Whisper 打破沉默:AI 语音技术如何重塑无障碍沟通方式? - 指南
  • 做题记录(Oct.)
  • 生成式AI改进极端多标签分类技术
  • 2025.10.5——1绿
  • 【清晰教程】利用Git工具将本地项目push上传至GitHub仓库中 - 指南
  • 题解:2025.10.信友队.智灵班选拔面试题目
  • MX WEEK4
  • 实用指南:蓝桥杯_DS18B20温度传感器---新手入门级别超级详细解析
  • 2025.10.4 刷题