题解思路

这是一道经典的二分查找逆向推导问题。核心在于理解二分搜索的状态转移过程，并根据反馈序列精确还原搜索轨迹。

1. 二分查找过程分析

标准的二分查找过程包括：

1. 中点计算：$g = \lfloor \frac{l + r + 1}{2} \rfloor$（这里使用上偏中点）
2. 比较判断：
   • 如果 $g > x$（猜大了），返回'1'，搜索区间更新为 $[l, g-1]$
   • 如果 $g \leq x$（猜小了或猜对了），返回'0'，搜索区间更新为 $[g, r]$

2. 逆向推导算法

根据反馈字符串，我们可以逆向模拟二分查找过程：

算法步骤：

1. 初始化搜索区间：$l = 1, r = 2^{20}$
2. 对于第i轮反馈 $feedback[i]$：
   • 计算当前轮的猜测值：$g = \lfloor \frac{l + r + 1}{2} \rfloor$
   • 如果 $feedback[i] = '1'$：说明 $g > x$，更新 $r = g - 1$
   • 如果 $feedback[i] = '0'$：说明 $g \leq x$，更新 $l = g$
3. 20轮结束后，$l = r = x$

3. 上偏中点的重要性

题目使用的是上偏中点公式 $\lfloor \frac{l + r + 1}{2} \rfloor$，这确保了：

• 当区间长度为偶数时，选择靠右的中点
• 避免了死循环和边界处理问题
• 保证了20轮二分能够精确确定唯一解

4. 复杂度分析

• 时间复杂度：$O(T \times 20) = O(T)$
• 空间复杂度：$O(1)$

Java题解代码

import java.io.*;
import java.util.*;

public class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder result = new StringBuilder();
        
        int T = Integer.parseInt(br.readLine().trim());
        
        for (int t = 0; t < T; t++) {
            String feedback = br.readLine().trim();
            long secretNumber = recoverSecretNumber(feedback);
            result.append(secretNumber).append("\n");
        }
        
        System.out.print(result.toString());
    }
    
    /**
     * 根据二分查找的反馈序列还原秘密数字
     * @param feedback 长度为20的反馈字符串，'0'表示猜小了或猜对了，'1'表示猜大了
     * @return 还原出的秘密数字
     */
    private static long recoverSecretNumber(String feedback) {
        long left = 1;
        long right = 1L << 20; // 2^20 = 1048576
        
        // 模拟20轮二分查找过程
        for (int round = 0; round < 20; round++) {
            // 计算本轮的猜测值（上偏中点）
            long guess = (left + right + 1) / 2;
            
            char response = feedback.charAt(round);
            
            if (response == '1') {
                // 猜大了，secret number在左半部分
                right = guess - 1;
            } else {
                // 猜小了或猜对了，secret number在右半部分（包含guess）
                left = guess;
            }
        }
        
        // 经过20轮二分后，left = right = secret number
        return left;
    }
}

C++题解代码

#include <iostream>
#include <string>
#include <ios>

using namespace std;

class SecretNumberDecoder {
public:
    void solve() {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        
        int T;
        cin >> T;
        
        while (T--) {
            string feedback;
            cin >> feedback;
            
            long long secretNumber = recoverSecret(feedback);
            cout << secretNumber << "\n";
        }
    }
    
private:
    /**
     * 基于二分查找反馈序列还原秘密数字
     */
    long long recoverSecret(const string& feedback) {
        long long left = 1;
        long long right = 1LL << 20; // 2^20
        
        // 逐步模拟二分查找过程
        for (int i = 0; i < 20; i++) {
            // 计算当前轮次的猜测值（使用上偏中点）
            long long currentGuess = (left + right + 1) / 2;
            
            if (feedback[i] == '1') {
                // 响应为1：猜测值大于秘密数字
                right = currentGuess - 1;
            } else {
                // 响应为0：猜测值小于等于秘密数字
                left = currentGuess;
            }
        }
        
        return left; // 此时left == right == 秘密数字
    }
};

int main() {
    SecretNumberDecoder decoder;
    decoder.solve();
    return 0;
}