【题解】牛客模考 · 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"
