牛客22296题解：关灯游戏胜负判断的模拟算法与代码实现
1天前
一、题目解读
牛客22296题描述了一个关灯游戏：有n个灯泡，每个灯泡初始状态为关闭（0）或打开（1）。玩家Alice和Bob轮流操作，最后操作最后一个灯泡的人获胜。题目要求根据输入的灯泡状态序列，判断最终获胜者。核心在于通过状态序列推断最后一次操作的对象，从而确定胜负。
二、解题思路
采用简单模拟策略解题。代码通过循环依次读取每个灯泡的状态，仅记录最后一个灯泡的状态（last_bulb）。由于胜负取决于最后一个灯泡的操作权，无需考虑中间状态变化，直接根据最后状态判断：若last_bulb为打开（1），则Alice获胜；否则Bob获胜。该解法时间复杂度O(n)，空间复杂度O(1)，高效直观。
三、解题步骤
1. 初始化变量last_bulb = 0，表示初始状态未知或未记录。
2. 循环读取n个灯泡状态：
○ 若当前为最后一个灯泡（i == n - 1），更新last_bulb为当前状态。
3. 根据last_bulb值输出获胜者：若为1则输出"Alice"，否则输出"Bob"。
四、代码与注释
#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;
}五、总结
本题通过简化问题本质，将复杂游戏规则转化为对最后一个状态的追踪，避免了繁琐的逻辑模拟。代码利用循环直接获取关键信息，体现了“抓住核心，忽略冗余”的解题思想。掌握此类简化策略，对处理类似逻辑判断问题具有启发意义。
原创内容 转载请注明出处
