🎯 选择题破解器

100道4选1单选题，一题不会，只能看总分。
如何用最少的提交次数找出所有正确答案？

提交次数
0
已确定答案
0
当前得分
-
状态
就绪
📋 题目状态（绿色=已确定，黄色=测试中）
📝 操作日志
等待开始...
💡 策略原理

问题本质

这是一个信息搜索问题。100道4选1题，共有 4100 种可能的答案组合（约 1060），我们需要通过"提交后只返回正确数量"这个反馈来定位唯一正确答案。

二分法策略（最优）

核心思想：每次提交尽可能获取最多的信息。

第一阶段：建立基准

先提交一份全A的答卷，得到基准分数 S₀。这告诉我们有多少题的正确答案是A。

第二阶段：逐题确定

对于每道题，我们需要确定它的正确答案是A/B/C/D中的哪一个。

假设当前第i题我们填的是A，其他题保持不变：

  • 把第i题改成B，提交，得分变化 Δ
  • 如果 Δ = +1，说明B是正确答案
  • 如果 Δ = -1，说明A是正确答案
  • 如果 Δ = 0，说明A和B都不对，继续测试C
最坏情况分析：
每道题最多需要测试3次（测试B、C、D，如果都不对则答案是A）。
但实际上，通过分组策略可以大幅减少提交次数。

分组优化

将题目分成若干组，同时改变一组题的答案。通过分数变化可以推断出这组题中有多少题的答案被改对/改错了。

理论最优：O(n × log₂(k)) 次提交
n=100, k=4 时约 200 次

逐题法（对照组）

最朴素的方法：对每道题依次尝试每个选项，直到找到正确答案。

最坏情况：每题需要 k-1 次尝试，共 n×(k-1) = 300 次。