牛客22296题 关灯游戏胜负判定 算法解析

问题核心分析

牛客22296题灯游戏是一个典型的博弈论问题，关键在于分析最后一个灯泡的状态。游戏规则要求每次操作必须选择一个亮着的灯泡，并翻转该灯泡及其右侧所有灯泡的状态。

胜负判定策略

通过观察可以发现，游戏的胜负实际上由‌最后一个灯泡的初始状态‌决定：

1. 如果最后一个灯泡初始为亮（1），Alice可以通过直接操作它来获胜

2. 如果最后一个灯泡初始为灭（0），Bob将获得必胜策略

C++实现代码

#include <iostream>
using namespACe std;

int main() {
    int n;
    cin >> n;
    
    int last_bulb = 0;
    for (int i = 0; i < n; ++i) {
        int state;
        cin >> state;
        if (i == n - 1) {
            last_bulb = state;
        }
    }
    
    cout << (last_bulb ? "Alice" : "Bob") << endl;
    return 0;
}

算法正确性证明

1. ‌最后一个灯泡为1的情况‌：Alice可以直接选择最后一个灯泡，使其变为0，同时右侧无灯泡需要翻转，直接获胜

2. ‌最后一个灯泡为0的情况‌：无论Alice选择哪个灯泡操作，都会导致最后一个灯泡变为1，Bob可以随后操作最后一个灯泡获胜

3. 这种策略在双方都采取最优操作时必然成立

复杂度分析

• 时间复杂度：O(n)，只需遍历一次灯泡序列

• 空间复杂度：O(1)，仅需存储最后一个灯泡的状态

扩展思考

1. 如果改变游戏规则，允许操作任意灯泡（不限于亮着的），胜负判定会如何变化？

2. 如果改变操作范围（如只翻转相邻灯泡），策略需要如何调整？

3. 这类博弈问题与Nim游戏等经典博弈模型的联系