解题思路

  1. 题目分析：

    • 个灯泡从左到右排列
    • Alice先手，Bob后手
    • 每次操作必须选择一个亮着的灯泡
    • 选中的灯泡及其右边的灯泡状态都会改变
    • 所有灯泡熄灭时游戏结束

  2. 解题策略：

    • 关键观察：最后一个灯泡的状态决定胜负
    • 如果最后一个灯泡是亮的(1)，Alice必胜
    • 如果最后一个灯泡是灭的(0)，Bob必胜

代码

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    // 读入灯泡状态
    int last_bulb;
    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;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        // 读入灯泡状态
        int lastBulb = 0;
        for(int i = 0; i < n; i++) {
            int state = sc.nextInt();
            if(i == n-1) lastBulb = state;
        }
        
        // 根据最后一个灯泡状态判断胜负
        System.out.println(lastBulb == 1 ? "Alice" : "Bob");
    }
}

n = int(input())
bulbs = list(map(int, input().split()))

# 根据最后一个灯泡状态判断胜负
print("Alice" if bulbs[-1] == 1 else "Bob")

算法及复杂度

  • 算法：数学推理
  • 时间复杂度： - 只需要读取输入
  • 空间复杂度： - 只需要存储最后一个灯泡的状态