首页 > 试题广场 >

消消看

[编程题]消消看

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

牛牛和牛妹最近迷上了新版消消看，该游戏规则如下：

在一个 $\text {01}$ 串中，每一轮，玩家都可以选择一串连续相同字符进行消除，消除之后，左右两侧剩余的字符自动拼接，重新形成一个字符串。
例如：在 $\text {101001}$ 中，牛牛选择了第四个和第五个字符，它们连续且都是 $\text 0$ ，满足消除条件，而当它们消除之后，左侧剩余的 $\text {101}$ 和右侧剩余的 $\text {1}$ 会拼接到一起，即：消除后剩余的 $\text {01}$ 串为： $\text {1011}$
计分规则如下：消除了几个 $\text 1$ 就计几分。
直到消成空串时游戏结束。

对于一串全新的 $\text {01}$ 串，由牛妹先手进行消除，两个人都以最优策略且以得分高为目标进行消除，请问最后，哪个人的得分会比较高？

输入描述:

本题为多组测试数据，第一行输入一个正整数 ，代表测试数据组数。

对于每组测试数据，一行输入一个长度不超过  的  串，代表初始形态。

输出描述:

对于每组测试数据，如果牛妹得分高，则在第一行输出 ，第二行输出一个分数代表牛妹比牛牛高几分；如果牛牛得分高，则在第一行输出 ，第二行输出一个分数代表牛牛比牛妹高几分；如果两个人分数相同，则只需要在一行输出 .

示例1

输入

2
111111
111011

输出

Niumei
6
Niumei
1

说明

第一个测试数据中，牛妹可以一次性消除所有字符，得到  分，而牛牛  分。
第二个测试数据中，牛妹先消除前三个字符，得到  分，剩余字符为 ，牛牛选择末尾两个字符消除，得到  分，至此，字符只剩下 ，牛妹消除掉这个字符，但由于该字符是 ，所以不得分。总计牛妹得到  分，牛牛得到  分。

算法知识视频讲解

Python

pein531

两人为了赢肯定每次都选择消除连续的1，如果某个人选择消除连续的0，那下一步操作的人就坐收渔翁之利了，不符合题设。所以按照0分割字符串，将连续的1串按照长度降序排列，然后牛妹和牛牛交替取出连续的1串，就是两人消除的顺序，直接累加上1串的长度可以计算得到牛妹和牛牛的得分。

import re

T = int(input())
while T > 0:
    lst = sorted(re.split("0+", input()), key=lambda seq: -len(seq))
    niumei, niuniu = 0, 0
    for i, item in enumerate(lst):
        if i % 2 == 0:
            niumei += len(item)
        else:
            niuniu += len(item)
    if niumei > niuniu:
        print("Niumei")
        print(niumei - niuniu)
    elif niumei < niuniu:
        print("Niuniu")
        print(niuniu - niumei)
    else:
        print("Draw")
    T -= 1

发表于 2022-01-21 21:56:48 回复(0)