首页 > 试题广场 >

胜者为王

[编程题]胜者为王
  • 热度指数:2105 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小明,小王,小李三人正在进行一个游戏。游戏有个回合,每个人都有一个字符串,三人的字符串长度相等。每个回合他们必须更改自己字符串中的一个字母。最后每个人的分数是自己的字符串中出现次数最多的字母的数量。分数最高者获胜,输出获胜者名字,小明获胜输出xiaoming,小王获胜输出xiaowang,小李获胜输出xiaoli,如果有两个或者两个以上相同的最高分输出draw。

输入描述:
第一个一个整数
第二行字符串,表示小明的字符串。
第二行字符串,表示小王的字符串。
第二行字符串,表示小李的字符串。


输出描述:
输出一行一个字符串,表示游戏结果。
示例1

输入

7
treasurehunt
threefriends
hiCodeforces

输出

xiaowang
题目有点问题,题目说:每个回合他们必须更改自己字符串中的一个字母
测试用例并非如此,如果全部字符都变成了自己那个字母了,后面可以不再改变,被坑了?
发表于 2021-08-15 16:42:53 回复(12)
   var n = readline()
    // var Ming='treasurehunt'
    var Ming = readline()
    var mingObj = {}
    // var Wang='threefriends'
    var Wang = readline()
    var wangObj = {}
    // var Li='hiCodeforces'
    var Li = readline()
    var liObj = {}

    function setObj(str, obj) {
        for (var i = 0; i < str.length; i++) {
            if (!obj[str.charAt(i)]) {
                obj[str.charAt(i)] = 1
            } else {
                obj[str.charAt(i)]++
            }
        }
    }
    setObj(Ming, mingObj)
    setObj(Wang, wangObj)
    setObj(Li, liObj)
    var mingCount = 0
    var wangCount = 0
    var liCount = 0
    
    function findMax(n,str,count, obj) {
        for (var i in obj) {
            if (obj[i] > count) {
                count = obj[i] 
            }
        }
        if(n>str.length-count){
            count=str.length
        }
        // for(var i=0;i<n;i++){
        //     if(count<str.length){
        //         count++
        //     }else{
        //         count--
        //     }
        // }
        return count

    }
    mingCount=findMax(n,Ming,mingCount, mingObj)
    wangCount=findMax(n,Wang,wangCount, wangObj)
    liCount=findMax(n,Li,liCount, liObj)
    
    var max=Math.max(mingCount, wangCount, liCount)
    var arr = []
    arr.push(mingCount, wangCount, liCount)
    if (arr.indexOf(max) !== -1&&arr.indexOf(max)==arr.lastIndexOf(max)) {
        if (mingCount == max) {
            console.log("xiaoming");
        } else if (wangCount == max) {
            console.log("xiaowang");
        } else {
            console.log("xiaoli");
        }
    }else{
        console.log("draw");
    }
这道题有点坑啊,它又说每轮必须改一个字母,然而当n的回合足够让字符串全部变成同一个字母的时候它就不用改了
发表于 2021-08-18 14:01:31 回复(1)
字符串长度相等,直接比较字符串中的字符出现次数,比如小王有三个e,小王第一,直接输出小王
发表于 2021-08-09 10:31:19 回复(3)
首先分别获取三人手中字符串中字母出现最高次数,每个回合+1,也就是把别的字符改成出现次数最高的字母,当回合没有结束时,字符串全是相同字母,那最高分数就是字符串长度。
发表于 2021-06-25 10:58:17 回复(0)
首先需要明白一个事实,每个人得分的上限就是自己字符串的长度。

算法流程

1.遍历字符串,计算3人的得分:统计出每个人字符串的字母众数mode,如果n+mode能够大于等于字符串的长度(因为总可以通过修改一些非众数字母,把多余的操作次数给消耗掉,使得剩下的操作次数能够把字符串中的所有字母都改成众数字母),得分就是这个字符串的长度;否则得分就是n+mode。
2.判断是否存在多个最高分:有就输出平局,没有就输出胜者。
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String xiaoming = br.readLine();
        String xiaowang = br.readLine();
        String xiaoli = br.readLine();
        int modeMing = getMode(xiaoming);
        int modeWang = getMode(xiaowang);
        int modeLi = getMode(xiaoli);
        if((modeMing == modeWang && modeMing > modeLi) || (modeMing == modeLi && modeMing > modeWang) || (modeWang == modeLi && modeWang > modeMing)){
            System.out.println("draw");     // 存在平局
        }else{
            if(modeMing > Math.max(modeWang, modeLi)){
                System.out.println("xiaoming");
            }else if(modeWang > Math.max(modeMing, modeLi)) {
                System.out.println("xiaowang");
            }else{
                System.out.println("xiaoli");
            }
        }
    }
    
    private static int getMode(String str) {
        int mode = 0;
        HashMap<Character, Integer> termFreq = new HashMap<>();
        for(int i = 0; i < str.length(); i++){
            char c = str.charAt(i);
            termFreq.put(c, termFreq.getOrDefault(c, 0) + 1);
            mode = Math.max(mode, termFreq.get(c));
        }
        return mode;
    }
}

发表于 2022-02-23 12:58:34 回复(6)
#include <iostream>
#include <iterator>
#include <unordered_map>
#include"bits/stdc++.h"
using namespace std;

int main() {
    int n = 3;
    int m;
    cin >> m;
    string* s = new string[n];
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    int len = s[0].length();
    vector<int> num;
    num.resize(n);
    for (int i = 0; i < n; i++) {
        int max_num = 1;
        unordered_map<char, int> map;
        const char* ss = s[i].c_str();
        for (int j = 0; j < len; j++) {
            if (map.find(ss[j]) != map.end()) {
                map[ss[j]]++;
                if (max_num < map[ss[j]]) {
                    max_num = map[ss[j]];
                }
            } else {
                map[ss[j]] = 1;
            }
        }
        num[i] = max_num;
    }

    for (int j = 0; j < 3; j++) {
        for (int i = 0; i < m; i++) {
            if (num[j] < len) {
                num[j]++;
                if(num[j]==len)
                {
                   i=m;
                }
            } else {
                num[j]--;
            }
        }
    }

    if ((num[0] == num[1] && num[0] > num[2]) || (num[0] == num[2] &&
            num[0] > num[1]) || (num[1] == num[2] && num[1] > num[0])||
        (num[0]==num[1]&&num[1]==num[2])) {
        cout << "draw" << endl;
    } else {
        if (num[0] > num[1] && num[0] > num[2]) {
            cout << "xiaoming" << endl;
        }
        if (num[1] > num[0] && num[1] > num[2]) {
            cout << "xiaowang" << endl;
        }
        if (num[2] > num[1] && num[2] > num[0]) {
            cout << "xiaoli" << endl;
        }

    }
}
// 64 位输出请用 printf("%lld")
发表于 2024-06-22 12:05:04 回复(0)
题目没问题吗,如果n为1的话,全部字符相同,那么这个时候返回len-1,但反之如果n不为1的话,且足够所有字符变化相同,那么就可以盯着一个位子,把多余的变换消去。还有那个特别长的用例,不给复制调试,很不人性化
发表于 2023-03-27 13:22:10 回复(0)
统计字符
from collections import Counter
NAMES = ["xiaoming", "xiaowang", "xiaoli"]
class Solution:
    def method(self,turns:int, names: list):
        if turns >= len(names[0]):
            return 'draw'
        max_ch = [0, 0, 0]
        for i in range(3):
            name = Counter(names[i])
            for k, freq in name.items():
                max_ch[i] = max(max_ch[i], freq)
        for i in range(3):
            remain = len(names[0]) - max_ch[i]
            max_ch[i] += min(turns, remain)
        ans = max(max_ch)
        count = 0
        index = 0
        for i in range(3):
            if ans == max_ch[i]:
                index = i
                count += 1
        return NAMES[index] if count == 1 else 'draw'
if __name__ == '__main__':
    turns = int(input())
    xiaoming = input()
    xiaowang = input()
    xiaoli= input()
    names = [xiaoming, xiaowang, xiaoli]
    solution = Solution()
    res = solution.method(turns, names)
    print(res)


发表于 2022-07-13 15:15:35 回复(0)
let n = readline();
let hashMap = {
    xiaoming: readline(),
    xiaowang: readline(),
    xiaoli:readline()
}

function getMax(str){
    let xm = {};
    [...str].forEach(t => {
        if(!xm[t]) xm[t] = 1;
        else xm[t]++;
    });
    let max = 0, char;
    for(let k in xm){
        if(xm[k] > max){
            max = xm[k];
            char = k;
        }else continue;
    }
    return {max, char};
}
let {xiaoming, xiaowang, xiaoli} = hashMap;
let length = xiaoming.length;
let {max:xmMax,char:xmChar} = getMax(xiaoming),
    {max:xwMax,char:xwChar} = getMax(xiaowang),
    {max:xlMax,char:xlChar} = getMax(xiaoli);
function seak(){
    for(let i =0; i< n; i++){
        // length - xmMax 为可交换次数5 - 3 = 2
        
        if(xmChar == xwChar || xwChar == xlChar || xmChar == xlChar){
            console.log('draw');
            return;
        }
        if(xmChar.length < length){
            xmChar += xmChar.substring(0, 1);
            xmMax++;
        }
        if(xwChar.length < length){   
            xwChar += xwChar.substring(0, 1);
            xwMax++;
        }
        if(xlChar.length < length){    
            xlChar += xlChar.substring(0, 1);
            xlMax++;
        }
    }
    if(xmMax > xwMax && xmMax > xlMax){
        console.log('xiaoming')
    }else if(xwMax > xmMax && xwMax > xlMax){
        console.log('xiaowang')
    }else if(xlMax > xwMax && xlMax > xmMax){
        console.log('xiaoli')
    }else{
        console.log('draw');
    }
}
seak();
实在没看懂,只通过了36例,总共60例
编辑于 2022-04-14 23:42:59 回复(0)
//直接排个序就行
import java.util.*;
public class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = Integer.parseInt(sc.nextLine());
            String as = sc.nextLine();
            int a = getMax(as);
            int b = getMax(sc.nextLine());
            int c = getMax(sc.nextLine());
            int len = as.length();
            sc.close();
            //找到最大的两个数
            int[] nums = {a, b, c};
            Arrays.sort(nums);
            int max = nums[2], second = nums[1];
            if (max == second || len - second <= n) {
                System.out.println("draw");
            } else {
                if (max == a) {
                    System.out.println("xiaoming");
                } else if (max == b) {
                    System.out.println("xiaowang");
                } else {
                    System.out.println("xiaoli");
                }
            }
        }

        public static int getMax(String s) {
            char[] cs = s.toCharArray();
            Map<Character, Integer> map = new HashMap<>();
            int max = 0;
            for (int i = 0; i < cs.length; i++) {
                int t = map.getOrDefault(cs[i], 0);
                map.put(cs[i], t + 1);
                max = Math.max(t + 1, max);
            }
            return max;
        }
    }

发表于 2022-03-23 23:45:14 回复(0)
//ACM模式
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    string s1,s2,s3;
    cin>>n>>s1>>s2>>s3;
    unordered_map<char,int> v1,v2,v3;
    int l1,l2,l3;
    l1=l2=l3=0;
    int m=s1.size();
    for(int i=0;i<m;i++){
        v1[s1[i]]++;
        v2[s2[i]]++;
        v3[s3[i]]++;
    }
    for(auto [k,v]:v1){
        int t=v+n;
        if(t<m) l1=max(l1,t);
        else if((t-m)%2==0) l1=max(l1,m);
        else l1=max(l1,m-1);
    }
     for(auto [k,v]:v2){
        int t=v+n;
        if(t<m) l2=max(l2,t);
        else if((t-m)%2==0) l2=max(l2,m);
        else l2=max(l2,m-1);
    }
    for(auto [k,v]:v3){
        int t=v+n;
        if(t<m) l3=max(l3,t);
        else if((t-m)%2==0) l3=max(l3,m);
        else l3=max(l3,m-1);
    }
    

    if(l1>l2&&l1>l3) cout<<"xiaoming"<<endl;
    else if(l2>l1&&l2>l3) cout<<"xiaowang"<<endl;
    else if(l3>l1&&l3>l2) cout<<"xiaoli"<<endl;
    else cout<<"draw"<<endl;
     return 0;
}
理清题意很重要,博弈论,只需要对最大哈希值进行增加。没有溢出,maxlen+n;如果溢出,奇数为字符串长度-1,偶数为字符串长度。

发表于 2021-12-22 21:26:34 回复(0)
(1)首先计算每个字符串中最多出现的字符;
(2)计算每个人经过n过回合后能够出现的最大字符数,如果在第一步Max已经是字符串长度,那么直接返回字符串长度,若Max在第一步不等于字符串长度,则计算Max+n回合是否大于字符串长度,如果大于则直接返回字符串长度,如果小于则Max=Max+n;
(3)对每个人经n回合后得到的最大字符数进行比较。
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		String m = scanner.next();
		String w = scanner.next();
		String l = scanner.next();
		int m_max = getCount(m,n);
		int w_max = getCount(w,n);
		int l_max = getCount(l,n);
		if(m_max>w_max) {
			if(m_max>l_max) {
				System.out.println("xiaoming");
			}else if(m_max==l_max){
				System.out.println("draw");
				
			}else {
				System.out.println("xiaoli");
			}
			
		}else if(m_max==w_max) {
			if(m_max<l_max) {
				System.out.println("xiaoli");
			}else {
				System.out.println("draw");
			}
		}else {
			if(w_max>l_max) {
				System.out.println("xiaowang");
			}else if(w_max==l_max){
				System.out.println("draw");
				
			}else{
				System.out.println("xiaoli");
			}
			
		}
		
	
		
	}
	public static int getCount(String s,int n) {
		int max = 0;
		int len = s.length();
		Map<Character, Integer> map = new HashMap<Character, Integer>();
		for(int i = 0;i<len;i++) {
			if(map.containsKey(s.charAt(i))) {
				map.put(s.charAt(i),map.get(s.charAt(i))+1);
			}else {
				map.put(s.charAt(i), 1);
			}
			max = map.get(s.charAt(i))>max?map.get(s.charAt(i)):max;
			
		}
		max = max==len?len:(max+n>len?len:max+n);//关键代码
		
		return max;
	}

}


发表于 2021-09-08 10:43:39 回复(0)
统计第一回合字符串重复最高个数count。当count小于字符串长度size时,count+1,否则count-1。最后比较三个count即可
发表于 2021-08-17 07:14:17 回复(0)
#include<bits/stdc++.h>
using namespace std;

int score(string& s, int n) {
    unordered_map<char, int> M;
    for (auto c : s) M[c]++;
    int res = 0, m = s.size();
    for (auto& it : M) {
        int t = it.second + n;  // 最多
        if (t < m) {  // 不可全变
            res = max(res, t);
        }
        else if ((t - m) % 2 == 0) {  // 可全变
            return m;
        }
        else {
            res = max(res, m - 1);
        }
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    string s1, s2, s3;
    cin >> s1;
    cin >> s2;
    cin >> s3;
    int x1 = score(s1, n);
    int x2 = score(s2, n);
    int x3 = score(s3, n);
    if (x1 > x2 && x1 > x3) {
        cout << "xiaoming" << endl;
    }
    else if (x2 > x1 && x2 > x3) {
        cout << "xiaowang" << endl;
    }
    else if (x3 > x1 && x3 > x2) {
        cout << "xiaoli" << endl;
    }
    else {
        cout << "draw" << endl;
    }
}
统计每个字符的个数,计算n个回合最多出现多少个该字符,当可全变为该字符时,返回字符串长度即为得分,否则取最大。
发表于 2021-07-05 23:48:41 回复(0)