【题解】牛客模考 · 2021年第一次校招模拟笔试

天弃之子

题意

游戏共有 关，每一关有 个按钮，其中只有一个可以过关，选择错误就会重新开始

玩家可以通过试错记住正确的按钮

问玩家运气最差时（每一关都要试 次才过关）共需要按多少次按钮才能通关。

分析

这道题最重要的环节就是读懂题目

从题意中分析出【每一关都要试 次】之后就比较容易了

对于每一关来说，都要进行 次失败

每次失败要先通过前面的 关，再算上当前这关，需要按 次按钮

所以往答案里累加

再算上最终成功的那次，通过 关需要按 次按钮即可

C++ 代码

long long findMaxButtons(vector<int>& a) {
    long long res = a.size();
    for(int i = 0; i < a.size(); i ++) {
        //  第i关要失败a[i] - 1次，每次都要按i次按钮，每次都要按i次按钮，共(a[i] - 1) * i次
        res += (long long)(a[i] - 1) * (i + 1);
    }
    return res;
}

Java 代码

public long findMaxButtons (int[] a) {
    long res = a.length;
    for(int i = 0; i < a.length; i ++) {
        //  第i关要失败a[i] - 1次，每次都要按i次按钮，每次都要按i次按钮，共(a[i] - 1) * i次
        res += (long)(a[i] - 1) * (i + 1);
    }
    return res;
}

Python 代码

def findMaxButtons(self , a ):
    n = len(a)
    res = n
    for i in range(0, n):
        # 第i关要失败a[i] - 1次，每次都要按i次按钮，每次都要按i次按钮，共(a[i] - 1) * i次
        res += (a[i] - 1) * (i + 1)
        return res

刷墙

题意

一个长度为 的 串，要把串变成某个位置左边全是 ，右边全是 至少要修改几个字符

分析

我们不知道应该把串变成几个 几个 ，考虑枚举 和 的分界点

设串的下标为 ，枚举的分界点为 ，令 全部为 ， 全部为

把 这个区间内的数全变成 的次数等于这个区间内 的个数

把 这个区间内的数全变成 的次数等于这个区间 的个数

可以预处理前缀和 为 中 的个数，然后就可以在 的时间复杂度内求出每个分界点要变化的数的个数，更新答案即可

C++ 代码

#include<cstdio>
#include<algorithm>

using namespace std;

const int N = 100010;

char s[N];
int sum[N];

int main()
{
    int n;
    scanf("%d%s", &n, s + 1);

    for(int i = 1; i <= n; i ++)
        sum[i] = sum[i - 1] + s[i] - '0';

    int res = n;
    for(int i = 0; i <= n; i ++)
    {
        //  [1, i]中'0'的个数为 i - sum[i]
        //  [i + 1, n]中'1'的个数为 sum[n] - sum[i]
        res = min(res, i - sum[i] + sum[n] - sum[i]);
    }
    printf("%d\n", res);
    return 0;
}

Java 代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        String s = ' ' + sc.next();

        int[] sum = new int[n + 1];
        for(int i = 1; i <= n; i ++) {
            sum[i] = sum[i - 1] + s.charAt(i) - '0';
        }

        int res = n;
        for(int i = 0; i <= n; i ++)
        {
            //  [1, i]中'0'的个数为 i - sum[i]
               //  [i + 1, n]中'1'的个数为 sum[n] - sum[i]
            res = Math.min(res, i - sum[i] + sum[n] - sum[i]);
        }
        System.out.println(res);
    }
}

Python 代码

n = int(raw_input())
s = ' ' + raw_input()

sum = [0] * (n + 1)
for i in range(1, n + 1):
    sum[i] = sum[i - 1] + int(s[i])

res = n
for i in range(0, n + 1):
    # [1, i]中'0'的个数为 i - sum[i]
    # [i + 1, n]中'1'的个数为 sum[n] - sum[i]
    res = min(res, i - sum[i] + sum[n] - sum[i])
print res

胜者为王

题意

三个人各自拥有一个字符串，他们的字符串长度相等，游戏进行 回合，每回合每个人必须修改自己字符串中的一个字母，每个人最终得分是他字符串中出现次数最多的字母数量，判断谁最终得分最多。

分析

有一个显而易见的贪心策略是先找到出现最多的字母是哪个，然后把其他字母尽可能都改成这个字母

设出现次数最多的字母数量是 ，再进行 回合，这个字母就可以有 个

如果 不必担心在全部改成同一个字母之后每回合还必须改掉一个

可以留一个字母先改成其他字母，在最后一回合再改成目标字母即可

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 100010;

char a[N], b[N], c[N];
int cnt[256];

int main()
{
    int n;
    scanf("%d%s%s%s", &n, a, b, c);

    int x = 0, y = 0, z = 0;
    for(int i = 0; a[i]; i ++)  x = max(x, ++ cnt[a[i]]);
    memset(cnt, 0, sizeof cnt);
    for(int i = 0; b[i]; i ++)  y = max(y, ++ cnt[b[i]]);
    memset(cnt, 0, sizeof cnt);
    for(int i = 0; c[i]; i ++)  z = max(z, ++ cnt[c[i]]);

    int len = strlen(a);
    x = min(x + n, len);
    y = min(y + n, len);
    z = min(z + n, len);

    if(x > y and x > z)  puts("xiaoming");
    else if(y > x and y > z)  puts("xiaowang");
    else if(z > x and z > y)  puts("xiaoli");
    else  puts("draw");
    return 0;
}

Java 代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String a = sc.next();
        String b = sc.next();
        String c = sc.next();

        int[] cnt = new int[256];
        int x = 0, y = 0, z = 0;
        for(int i = 0; i < a.length(); i ++) {
            x = Math.max(x, ++ cnt[a.charAt(i)]);
        }
        for(int i = 0; i < cnt.length; i ++)  cnt[i] = 0;
        for(int i = 0; i < b.length(); i ++) {
            y = Math.max(y, ++ cnt[b.charAt(i)]);
        }
        for(int i = 0; i < cnt.length; i ++)  cnt[i] = 0;
        for(int i = 0; i < c.length(); i ++) {
            z = Math.max(z, ++ cnt[c.charAt(i)]);
        }
        int len = a.length();
        x = Math.min(x + n, len);
        y = Math.min(y + n, len);
        z = Math.min(z + n, len);
        if(x > y && x > z)  System.out.println("xiaoming");
        else if(y > x && y > z)  System.out.println("xiaowang");
        else if(z > x && z > y)  System.out.println("xiaoli");
        else  System.out.println("draw");
    }
}

Python 代码

n = int(raw_input())
a = raw_input()
b = raw_input()
c = raw_input()

x, y, z = 0, 0, 0
cnt = [0] * 256
for i in a:
    cnt[ord(i)] += 1
    x = max(x, cnt[ord(i)])

cnt = [0] * 256
for i in b:
    cnt[ord(i)] += 1
    y = max(y, cnt[ord(i)])

cnt = [0] * 256
for i in c:
    cnt[ord(i)] += 1
    z = max(z, cnt[ord(i)])

length = len(a);
x = min(x + n, length);
y = min(y + n, length);
z = min(z + n, length);

if x > y and x > z:
    print "xiaoming"
elif y > x and y > z:
    print "xiaowang"
elif z > x and z + y:
    print "xiaoli"
else:
    print "draw"