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

ftggdnt

问题核心分析

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

胜负判定策略

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

• 如果**一个灯泡初始为亮（1），Alice可以通过直接操作它来获胜
• 如果**一个灯泡初始为灭（0），Bob将获得必胜策略
  
  

C++实现代码

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. int main() {
   
5.     int n;
   
6.     cin >> n;
   
7.    
   
8.     int last_bulb = 0;
   
9.     for (int i = 0; i < n; ++i) {
   
10.         int state;
    
11.         cin >> state;
    
12.         if (i == n - 1) {
    
13.             last_bulb = state;
    
14.         }
    
15.     }
    
16.    
    
17.     cout << (last_bulb ? "Alice" : "Bob") << endl;
    
18.     return 0;
    
19. }

复制代码

算**确性证明

• ‌**一个灯泡为1的情况‌：Alice可以直接选择**一个灯泡，使其变为0，同时右侧无灯泡需要翻转，直接获胜
• ‌**一个灯泡为0的情况‌：无论Alice选择哪个灯泡操作，都会导致**一个灯泡变为1，Bob可以随后操作**一个灯泡获胜
• 这种策略在双方都采取**操作时必然成立
  
  

复杂度分析

• 时间复杂度：O(n)，只需遍历一次灯泡序列
• 空间复杂度：O(1)，仅需存储**一个灯泡的状态
  
  

扩展思考

• 如果改变游戏规则，允许操作任意灯泡（不限于亮着的），胜负判定会如何变化？
• 如果改变操作范围（如只翻转相邻灯泡），策略需要如何调整？
• 这类博弈问题与Nim游戏等经典博弈模型的联系
  
  

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