主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
题解：AT_arc184_a [ARC184A] Appraiser
最后更新于 2025-08-28 09:03:15
作者
2huk
分类
题解
题解
AT_arc184_a
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
交互题真好玩。虽然我不会做。 ## 题意 有 $n = 1000$ 枚硬币，其中有 $m = 10$ 个是假币，剩下的是真币。你需要用不多于 $q = 950$ 次询问交互库任意两枚硬币的真假是否相同。最后输出哪些是假币。 ## 做法 显然你可以通过 $k - 1$ 次询问得到 $k$ 个硬币的相对真假关系。每次拿它和第一个问即可。 那么我们可以通过 $10$ 次操作得到 $11$ 个硬币的相对真假关系。如果这 $11$ 个硬币全部相同，那么我们可以确定这 $11$ 个硬币都是**真币**。 所以我们考虑将 $1000$ 个硬币分成 $90$ 组，每组 $11$ 个。还剩 $10$ 个再组成一组。 显然前 $90$ 组中，我们可以通过 $90 \times 10 = 900$ 次询问得到每一组中硬币的相对真假关系。 因为只有 $10$ 个假币，所以在前 $90$ 组中，至多有 $10$ 个组存在假币。我们在剩下的 $80$ 组中随便选一个都是真币，把这个作为基准，以后要单独判断的都和这个真币比较。 那么那 $10$ 个组中，哪些是真哪些是假呢？显然我们只需要那基准和这个组中的**任意一个**比较，都能依次推出每个组所有金币的真假。 剩下的 $10$ 个未分组的金币拿基准和它单独比较即可。总次数最多 $90\times10+10+10=920$。 https://atcoder.jp/contests/arc184/submissions/58049698
正在渲染内容...
点赞
2
收藏
0
