首页 > 试题广场 >

消消看

[编程题]消消看

热度指数：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

说明

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

算法知识视频讲解

牛客834002708号

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        while(T-- > 0){
            StringBuffer s = new StringBuffer(in.next());
            int niumei = 0, niuniu = 0, targe = 0;
            while(s.length() > 0){
                targe++;               // 消除次数
                if(s.indexOf("1") >= 0){
                    int a[] = Test1(String.valueOf(s)); // 寻找最长的连1子串
                    s = s.delete(a[0],a[0]+a[1]);       // 返回最开始出现的下标a[0]，和连1的长度a[1]
                    if(targe%2 == 1){  // 先手
                        niumei += a[1];
                    }else{             // 后手
                        niuniu += a[1];
                    }
                    continue;
                }
                if(s.indexOf("0") >= 0){  // 当所有的1消除完后，只剩下0，全部消除即可，不加分
                    s = s.delete(s.indexOf("0"),s.length());
                    continue;
                }
            }
            String winner = niumei>niuniu ? "Niumei":(niumei==niuniu ? "Draw":"Niuniu");
            System.out.println(winner);
            if(Math.abs(niumei-niuniu) != 0){
                System.out.println(Math.abs(niumei-niuniu));
            }
        }
    }
    public static int[] Test1(String s){  // 返回最长的连1子串
        int max=0, index = 0;
        for(int i=0;i<s.length();i++){
            int sum=0, targe=i;
            while(i<s.length() && s.charAt(i)=='1'){
                sum++;
                i++;
            }
            if(sum > max){
                max = sum;
                index = targe;
            }
        }
        int a[] = new int[]{index, max};
        return a;
    }
}

发表于 2021-08-15 22:54:43 回复(0)

JavaScript

herroXu

发表于 2021-07-23 13:51:30 回复(0)

牛客527764874号

def get_count(n_list):
    a, b = 0, 0
    # 用 split 并且去除''之后取长度排序
    n_list = sorted([len(n) for n in [i for i in n_list.split('0') if i is not '']],reverse=True)
    for i,n in enumerate(n_list):
        # 牛妹先手
        if i%2 == 0:
            a+=n
        else:
            b+=n
    if a > b:
        print('Niumei')
        print(a - b)
    elif b > a:
        print('Niuniu')
        print(b - a)
    else:
        print('Draw')


times = input()
test_list = [input() for n in range(int(times))]
for n_list in test_list:
    get_count(n_list)

# 题目中 <两个人都以最优策略且以得分高为目标进行消除>
# 故 1 未消除完的时候是不会考虑消除 0 所以不存在消除 0 而 1 产生合并的情况
# 而且从游戏角度，去消除 0 之后把长的 1 列让给对面，这不是送分吗？

编辑于 2021-10-26 23:18:24 回复(5)

百无一用20180710151936

// 1. 先消除 1, 先手必定选择先消除最长的 1 串
// 2. 后手同样如此, 如此交替下去, 直到串中没有 1
// 3. 此时剩下的全为 0, 消除也不得分
// 因此, 只需要统计串中连续 1 的个数组成数组
// 对数组降序进行排序, 奇数索引的值累加为先手的得分
// 偶数索引的值累加为后手的得分
int main_niumei() {
    int T;
    while (cin >> T) {//T有几个字符串
        string str;
        for (int i = 0; i < T; i++) {
            cin >> str;
            vector<int> block;//block数组
            int score1 = 0, score2 = 0;
            int num = 0;
            for (auto& c : str) {//遍历str字符串
                if (c == '1') num++;
                else {
                    if (num > 0) {
                        block.push_back(num);//连续1的个数插入block尾部
                        num = 0;
                    }
                }
            }
            if (num) block.push_back(num);//111011,最后11不经过0，需加此行
            sort(block.begin(), block.end(), greater<int>());//降序排列，升序可用less<int>()
            for (int i = 0; i < block.size(); i++)
            {
                if (i % 2 == 0)
                {
                    score1 += block[i];
                }
                else
                {
                    score2 += block[i];
                }

            }
            if (score1 > score2) {
                cout << "Niumei" << endl;
                cout << score1 - score2 << endl;
            }
            else if (score1 < score2) {
                cout << "Niuniu" << endl;
                cout << score2 - score1 << endl;
            }
            else cout << "Draw" << endl;
        }
    }
    return 0;
}

发表于 2021-09-07 19:27:51 回复(0)

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)

_大白_

import java.util.*;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = Integer.parseInt(sc.nextLine());
        for (int i = 0; i < num; ++i) {
            fun(sc.nextLine());
        }
    }
     
    public static void fun(String input) {
        // 记录各个连着的1的数量
        List<Integer> list = new ArrayList<Integer>();
        int num = 0;
        for (int i = 0; i < input.length(); ++i) {
            if (input.charAt(i) == '1') {
                num++;
            } else {
                if (num != 0) {
                    list.add(num);
                }
                num = 0;
            }
        }
        if (num != 0) {
            list.add(num);
        }
        Collections.sort(list);
        int score = 0;
        int add = 1;
        for (int i = list.size() - 1; i >= 0; --i) {
            score += (add * list.get(i));
            add *= (-1);
        }
         
        if (score == 0) {
            System.out.println("Draw");
        } else if (score < 0) {
            score *= (-1);
            System.out.println("Niuniu");
            System.out.println(score + "");
        } else {
            System.out.println("Niumei");
            System.out.println(score + "");
        }
    }
}

发表于 2021-07-30 11:15:59 回复(0)

天涯叹雪

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
    int T;
    while (cin >> T) {
        string str;
        for (int i = 0; i < T; i++) {
            cin >> str;
            vector<int> block;
            int score1 = 0, score2 = 0;
            int num = 0;
            for (auto& c : str) {
                if (c == '1') num++;
                else {
                    if (num > 0) {
                        block.push_back(num);
                        num = 0;
                    }
                }
            }
            if (num) block.push_back(num);
            sort(block.begin(), block.end(), greater<int>());
            for (int i = 0; i < block.size(); i += 2) {
                score1 += block[i];
                if (i + 1 < block.size()) score2 += block[i + 1];
            }
            if (score1 > score2) {
                cout << "Niumei" << endl;
                cout << score1 - score2 << endl;
            }
            else if (score1 < score2) {
                cout << "Niuniu" << endl;
                cout << score2 - score1 << endl;
            }
            else cout << "Draw" << endl;
        }
    }
    return 0;
}

发表于 2021-07-21 17:22:42 回复(0)

做一个努力学习的奋斗者

import java.util.*;
public class Main {
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            while(sc.hasNextLine()){
                String s = sc.nextLine();
                int n = Integer.parseInt(s);
                String[] str = new String[n];
                for(int i=0;i<n;i++){
                    str[i]= sc.nextLine();
                    getRes(str[i]);
                }
            }
        }
       //创建一个方法
      public static void getRes(String s){
          //记录字符串中的每段连续1的个数
          ArrayList<Integer> list = new ArrayList<>();
          int count =0;
          for(int i=0;i<s.length();i++){
              if(s.charAt(i)=='1'){
                  count++;
              }else{
                  if(count>0){
                      list.add(count);
                      
                  }
                  count=0;
              }
              
          }
          //当字符串跑完的时候，需要判断count是否为0，不为0就得加入
          if(count>0){
                  list.add(count);
          }
          //排序list
          Collections.sort(list);
          //System.out.println(list);
          int Niumei = 0;
          int Niuniu = 0;
          for(int i=list.size()-1;i>=0;i--){
              if((i+1-list.size())%2==0){
                  Niumei += list.get(i);
              }else{
                  Niuniu += list.get(i);
              }
          }
          if(Niumei>Niuniu){
              System.out.println("Niumei");
              System.out.println(Niumei-Niuniu);
          }else if(Niumei==Niuniu){
              System.out.println("Draw");
          }else{
              System.out.println("Niuniu");
              System.out.println(Niuniu-Niumei);
          }
      }
}

发表于 2022-02-19 18:43:07 回复(0)

大鹏175

牛牛能赢吗，我觉得赢不了啊

发表于 2021-09-06 14:24:55 回复(0)

牛客700331789号

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
// 1. 先消除 1, 先手必定选择先消除最长的 1 串
// 2. 后手同样如此, 如此交替下去, 直到串中没有 1
// 3. 此时剩下的全为 0, 消除也不得分
// 因此, 只需要统计串中连续 1 的个数组成数组
// 对数组降序进行排序, 奇数索引的值累加为先手的得分
// 偶数索引的值累加为后手的得分
//reference： https://yuanlehome.github.io/ZUdtS6UUmrVCKLed/
public class 消消看 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int times = Integer.parseInt(sc.nextLine());
        for (int i = 0; i < times; i++) {
            game(sc.nextLine());
        }
    }

    public static  void game(String a) {
        int n = a.length();
        ArrayList<Integer> b = new ArrayList<Integer>();
        //计算连续或者单个1从左到右依次出现的总共次数，例如 输入: s = "0110110101001111"
        //那么 b[2,2,1,1,4]
        int left = 0, right = 0;
        while (right < n) {
            if (a.charAt(right) == '1') {
                left = right;
                while (right < n && a.charAt(right) != '0') {
                    right++;
                }
                b.add(right - left);
            }
            right++;
        }
        //降序排列b
        Collections.sort(b, Collections.reverseOrder());

        int[] res = new int[2];
        //牛妹的得分
        for (int i = 0; i < b.size(); i += 2) {
            res[0] += b.get(i);
        }
        //牛牛的得分
        for (int i = 1; i < b.size(); i += 2) {
            res[1] += b.get(i);
        }

        if (res[0] > res[1]) {
            System.out.println("NiuMei");
            System.out.println(res[0] - res[1]);
        } else if (res[0] < res[1]) {
            System.out.println("NiuNiu");
            System.out.println(res[1] - res[0]);
        } else {
            System.out.println("Draw");
        }
    }
}

发表于 2021-08-21 14:15:49 回复(0)

牛客295778374号

这题出的，不清不楚，最后剩 01010010应该先消连着的00还是先消1，最后剩0101010，是先消0，让1挨着，还是先消1

发表于 2021-08-17 14:40:22 回复(5)

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)

冰糖201911192013500

之前一直在做leetcode，第一次做阿里巴巴的题，就给我整蒙了，怎么还需要输入输出？来练练手

import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String temp = in.nextLine();
        int n = Integer.parseInt(temp);
        for (int i = 0; i < n; i++) {
            String string = in.nextLine();
            Map<Integer, Integer> numsLength = findNumsLength(string);
            final int[] nienie = {0};
            final int[] niemei = {0};
            boolean[] a = {false}; //用来表示牛牛先拿一个小的
            numsLength.forEach(
                    (length, nums) -> {
                        while (nums != 0) {
                            if (a[0]){
                                nienie[0] += length;
                                a[0] = false;
                            } else {
                                niemei[0] += length;
                                a[0] = true;
                            }
                            nums --;
                        }
 
                    }
            );
            if (niemei[0] > nienie[0]){
                System.out.println("Niumei");
                System.out.println(niemei[0] - nienie[0]);
            } else {
                System.out.println("Draw");
            }
        }
    }
 
    private static Map<Integer, Integer> findNumsLength(String string) {
        Map<Integer, Integer> res = new TreeMap<>((a,b) -> b-a);
        int n = string.length();
        int curr = 0;
        for (int i = 0; i < n; i++) {
            if (string.charAt(i) == '1'){
                curr++;
            }
            if (i == n-1 || string.charAt(i) == '0') {
                res.put(curr, res.getOrDefault(curr, 0) + 1);
                curr = 0;
            }
        }
        return res;
    }
}

发表于 2021-08-07 14:45:11 回复(0)

牛客888550950号

这个用例跟题目要求不一样啊

发表于 2021-08-05 16:52:47 回复(0)

horsetall

package com.mawei;  import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Scanner;  public class Demo5 { public static void main(String[] args) {
        Scanner in = new Scanner(System.in);   int num = in.nextInt();  String[] str = new String[num];  for (int i = 0; i<num; i++){
            str[i] = in.next();  } int nums =0;  List<Integer> list = new ArrayList<Integer>();  for (int j = 0; j<num; j++){ //记录连着的1的数量  for (int k = 0; k<str[j].length(); k++){ if (str[j].charAt(k) == '1'){
                    nums++;  }else{ if (nums != 0){
                        list.add(nums);  }
                    nums = 0;  }
            } if (nums != 0){
                list.add(nums);  } //对list集合升序排序  Collections.sort(list);  int add = 1;  int score = 0;   for (int m = list.size()-1; m>0; m--){
                score += (list.get(m)*add);  add *= (-1);  } if (score == 0){
                System.out.println("Draw");  }else if(score > 0){
                System.out.println("Niumei");  System.out.println(score + "");  }else{
                score *= (-1);  System.out.println("Niuniu");  System.out.println(score + "");  }

        }

    }
}

发表于 2021-08-01 12:25:54 回复(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)

22届失业鼠鼠

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

string s;
vector<int> arr;

void slove(){
    cin>>s;
    int Niumei = 0 , Niuniu = 0;
    for(int i = 0 ; i < s.size() ; i++){
        if(s[i] == '1'){
            int j = i;
            while(j < s.size() && s[j] == '1') j++;
            arr.push_back(j-i);
            i = j-1;
        }
    }
    
    sort(arr.begin() , arr.end(),greater<int>());
    for(int i = 0 ; i <arr.size() ; i++){
        if(i%2==0) Niumei+=arr[i];
        else Niuniu+=arr[i];
    }
    //cout<<Niumei<<" "<<Niuniu<<endl;
    arr.clear();
    if(Niumei > Niuniu){
        puts("Niumei");
        cout<<Niumei - Niuniu<<endl;
    }else if(Niuniu > Niumei){
        puts("Niuniu");
        cout<<Niuniu - Niumei<<endl;
    }else puts("Draw");
    
}
int main()
{
    int t;
    cin>>t;
    while(t--){
        slove();
    }
    return 0;
}

发表于 2021-07-17 13:36:20 回复(0)

黑莓婆婆

#include<bits/stdc++.h>
using namespace std;

int calc(string& s) {
    int n = s.length();
    if (n == 0) return 0;
    vector<int> arr;
    s += '0';
    int i = 0;
    while (i <= n) {
        while (i <= n && s[i] == '0') {
            i++;
        }
        if (i > n) break;
        int cnt = 0;
        while (i <= n && s[i] == '1') {
            cnt++;
            i++;
        }
        arr.push_back(cnt);
    }
    if (arr.size() == 0) return 0;
    sort(arr.begin(), arr.end());
    int score = 0;
    i = arr.size() - 1;
    while (i >= 0) {
        score += arr[i--];
        if (i >= 0) {
            score -= arr[i--];
        }
    }
    return score;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        string s;
        cin >> s;
        int score = calc(s);
        if (score == 0) {
            cout << "Draw" << endl;
        }
        else {
            cout << "Niumei" << endl;
            cout << score << endl;
        }
    }
    return 0;
}

将连续1的串长度存入数组，两者都选最大的，因此排序后，两个逐个选，算出差就行。因为niumei先选，因此niumei不可能比niuniu少。

发表于 2021-07-16 19:54:05 回复(0)