题解 | 小苯的真假游戏

【解题思路与题解讲解】

一、问题核心分析

1. 问题本质

给定 n 个围成一圈的小朋友，每个小朋友声称左侧的人说真话（'1'）或假话（'0'）。需统计满足以下条件的局面数：

• 若小朋友说真话 → 其声称的内容为真；
• 若小朋友说假话 → 其声称的内容为假。

2. 关键逻辑建模

设：

• a[i]：第 i 个小朋友是否说真话（1 = 真话，0 = 假话）；
• s[i]：第 i+1 个小朋友的声称（字符转数字后，s[i] ∈ {0,1}）。

根据规则推导核心公式：

• 若 a[i] = 1（说真话）→ 左侧的 a[i-1] 必须等于 s[i-1]（其声称的内容）；
• 若 a[i] = 0（说假话）→ 左侧的 a[i-1] 必须等于 1 - s[i-1]（与声称内容相反）；
• 合并为统一公式：a[i-1] = a[i] == 1 ? s[i-1] : 1 - s[i-1]。

3. 环形约束的简化

由于小朋友围成一圈，1 号左侧是 n 号，因此：

• 只需枚举 a[n] 的两种可能（0 或 1），通过公式推导所有 a[i]；
• 最终验证推导回的 a[0]（即 1 号左侧的 n 号）是否与初始假设的 a[n] 一致（环形闭合）；
• 一致则该初始假设为合法局面，否则不合法。

二、解题步骤

1. 输入处理：读取多组测试数据，每组包含 n 和 01 串 s；
2. 枚举初始状态：假设 a[n] = 1（第 n 个小朋友说真话），推导所有 a[i] 并验证环形闭合；假设 a[n] = 0（第 n 个小朋友说假话），推导所有 a[i] 并验证环形闭合；
3. 统计合法数：统计两种初始状态中合法的数量，输出结果

代码

void solve() {
    cin >> n >> s;
    s = s + s;
    string str = s;
    int ans = 0;
    vi a(n + 1, 0);
    a[n] = 1;
    for (int i = n; i >= 1; i--) {
        a[i - 1] = a[i] == (s[i - 1] - '0') ? 1 : 0;
    }
    if (a[0] == a[n]) {
        ans++;
    }
    a[n] = 0;
    for (int i = n; i >= 1; i--) {
        a[i - 1] = a[i] == (s[i - 1] - '0') ? 1 : 0;
    }
    if (a[0] == a[n]) {
        ans++;
    }
    cout << ans << endl;
}