首页 > 试题广场 >

关灯游戏

[编程题]关灯游戏

热度指数：1487 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

在 Alice 生日的那天， Bob 送给了她 n 个灯泡。他们决定用这些灯泡玩一个游戏：他们把这些灯泡从左往右排成一行，在初始时，有些灯泡是点亮的，有些灯泡是熄灭的。接下来，他们轮流进行操作，Alice 首先操作。在每一次操作中，轮到操作的人需要选择一个点亮的灯泡，然后把它以及它右边的所有灯泡的状态进行一次改变，即把点亮的灯泡熄灭，把熄灭的灯泡点亮。如果在某一个人操作完之后，所有的灯泡都变成了熄灭状态，那么那个人就赢得了游戏。 Alice 和 Bob 都想赢得游戏，在他们都足够聪明的情况下，最后谁会赢呢？

数据范围： $1 \le n \le 10^5 \$ ，输入只包含 0 和 1

输入描述:

第一行包含一个整数，表示灯泡的个数。

第二行包含个 0 或 1，表示初始时灯泡的状态，0 表示熄灭，1 表示点亮。

输出描述:

如果最后Alice能赢，输出Alice，或则输出Bob。

示例1

输入

3
0 1 1

输出

Alice

示例2

输入

5
1 1 1 0 0

输出

Bob

算法知识视频讲解

laglangyue

发表于 2020-06-23 21:34:33

没搞懂这道题，完全没思路，借鉴了讨论区大脑的dp,优化了存储。为什么会想到dp，思考之，只可意会，发现其实只与1的数量和最后一位是否为1有关。 import java.util.Scanner; public class Main { public static void main(Str 展开全文

苏觅云

发表于 2022-05-20 22:39:06

#include<cstdio> using namespace std; int main() { int n, t; scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d", 展开全文

17c89

发表于 2024-01-16 15:09:54

import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner in = new Scanner(System.in); while 展开全文

时倾.一世

发表于 2021-09-25 15:06:04

最开始读完题目后没有想出合适的解决方案，在讨论区看到了一个大佬的思路，瞬间就觉得清晰了起来————只需要看最后一个数字是0还是1。是0，说明需要操作偶数次灯才能全灭，那么就是Bob嬴；是1，说明需要奇数次灯才能全灭，那么就是Alice嬴。 import java.util.*; public cla 展开全文