首页 > 试题广场 >

消消看

[编程题]消消看

热度指数：1958 时间限制：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

说明

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

算法知识视频讲解

Java

方一二

题目说明：由牛妹先手进行消除，两个人都以最优策略且以得分高为目标进行消除

最优策略且得分最高说明有 1 就不会消 0，并且一定是选择消除当前最长的 1子串，

因为有 1 消除 0,那就是给对手送分

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int size = scan.nextInt();
        String[] strings = new String[size];
        for(int i = 0; i < size; i++){
            strings[i] = scan.next();
        }
        for(int i = 0; i < size; i++){
            solve((strings[i]));
        }
    }
    //由牛妹先手进行消除，两个人都以最优策略且以得分高为目标进行消除
    //最优策略且得分最高  说明  有 1 就不会消 0， 然后消 目前最长的 1串，
    //有 1 消除 0,那就是给对手送分
    public static void solve(String nums){
        String[] strs = nums.split("0");
        List<Integer> lens = new ArrayList();
        for(String str : strs){
            if(str.length() > 0 && str.charAt(0) == '1'){
                lens.add(str.length());
            }
        }
        Collections.sort(lens);
        int sum = 0; //最后求的 差值
        int add = 1;
        for(int i = lens.size()-1; i >= 0; i--){
            sum += lens.get(i)*add;
            add *= -1;
        }
        
        if(sum > 0){
            System.out.println("Niumei");
            System.out.println(sum);
        }
        else if(sum < 0){
            System.out.println("Niuniu");
            System.out.println(-1 * sum);
        } else{
            System.out.println("Draw");
        }
    }
}

编辑于 2021-08-13 10:33:25 回复(0)

Java

牛客647025800号

public static void main(String[] args) {
         Scanner input =new Scanner(System.in);
          System.out.println("输入测试数据的行数");
          int count = input.nextInt();
          String[] strings = new String[count];
         for (int i = 0; i <count ; i++) {
             System.out.println("输入测试数据");
             strings[i] = input.next();
         }
         for (int i = 0; i <count ; i++) {
             String str = strings[i];
             int meiCount = 0;
             int geCount = 0;
             int num = 0;
             while (true){
                 char[] chars = str.toCharArray();
                 int strLenth = str.length();
                 int maxCount = 0;
                 int start = 0;
                 int end = 0;
                 for (int j = 0; j <chars.length ; j++) {
                     int maxJCount = 0;
                     char c = chars[j];
                     int q = j;
                     while (true){
                         q++;
                         if (q<str.length()){
                             char c1 = str.charAt(q);
                             if (c==c1){
                                 maxJCount++;
                                 if (maxCount<maxJCount){
                                     maxCount = maxJCount;
                                     start = j;
                                     end = q;
                                 }
                             }else{
                                 break;
                             }
                         }else{
                             break;
                         }

                     }
                 }
                 if (maxCount>0){
                     maxCount++;
                    StringBuilder stringBuilder = new StringBuilder(str);
                    stringBuilder.delete(start,end+1);
                    str = stringBuilder.toString();
                 }
                 if (strLenth == str.length()){
                     break;
                 }
                 if (num%2==0){
                     meiCount += maxCount;
                 }else{
                     geCount += maxCount;
                 }
                 num++;

             }
             if (meiCount>geCount){
                 System.out.println("Niumei");
                  System.out.println(meiCount-geCount);
             }else if (meiCount<geCount){
                 System.out.println("Niuniu");
                 System.out.println(geCount-meiCount);
             }else{
                 System.out.println("Draw");

             }

         }
    }

发表于 2021-07-27 16:49:05 回复(0)