Sui Xin's Blog

牛客网模拟笔试（7月场）题解

Posted on In Disqus:

丑陋的字符串

题目描述

牛牛喜欢字符串,但是他讨厌丑陋的字符串。对于牛牛来说,一个字符串的丑陋值是字符串中相同连续字符对的个数。比如字符串“ABABAABBB”的 丑陋值是3,因为有一对”AA”和两对重叠的”BB”。现在给出一个字符串,字符串中包含字符’A’、’B’和’?’。牛牛现在可以把字符串中的问号改为’A’或者’B’。牛牛现在想让 字符串的丑陋值最小,希望你能帮帮他。

解题思路

贪心。遇到 ?，直接将当前位置改为与上一个位置不同的字母。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import sys


def greed(s):
    s = list(s.strip("?"))
    length = len(s)
    for i in range(1, length):
        if s[i] == "?":
            s[i] = "A" if s[i - 1] == "B" else "B"
    res = 0
    for i in range(1, length):
        if s[i] == s[i - 1]:
            res += 1
    return res


if __name__ == "__main__":
    data = sys.stdin.readline().strip()
    print(greed(data))

庆祝61

题目描述

牛家庄幼儿园为庆祝61儿童节举办庆祝活动,庆祝活动中有一个节目是小朋友们围成一个圆圈跳舞。牛老师挑选出n个小朋友参与跳舞节目,已知每个小朋友的身高h_i。为了让舞蹈看起来和谐,牛老师需要让跳舞的圆圈队形中相邻小朋友的身高差的最大值最小,牛老师犯了难,希望你能帮帮他。 如样例所示:
当圆圈队伍按照100,98,103,105顺时针排列的时候最大身高差为5,其他排列不会得到更优的解

解题思路

将整个数组排序，先拿最小的数字出来，再依次将后面的数字排列到该数字的两边，这样可以保证最后的差值的最大值最小。实际上，最终这样排列的结果是，原来的奇数位置相邻，原来的偶数位置相邻，所以只需计算 i 与 i-2 的差值的最大值即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import sys

def find_max_min(nums):
    length = len(nums)
    nums.sort()
    res = 0
    for i in range(2, length):
        res = max(res, nums[i] - nums[i - 2])
    return res


if __name__ == "__main__":
    n = int(sys.stdin.readline().strip())
    nums = list(map(int, sys.stdin.readline().strip().split()))
    print(find_max_min(nums))

逃离农场

题目描述

牛牛在农场饲养了n只奶牛,依次编号为0到n-1, 牛牛的好朋友羊羊帮牛牛照看着农场.有一天羊羊看到农场中逃走了k只奶牛,但是他只会告诉牛牛逃走的k 只奶牛的编号之和能被n整除。你现在需要帮牛牛计算有多少种不同的逃走的奶牛群。因为结果可能很大,输出结果对1,000,000,007取模。
例如n = 7 k = 4:
7只奶牛依次编号为0到6, 逃走了4只
编号和为7的有:{0, 1, 2, 4}
编号和为14的有:{0, 3, 5, 6}, {1, 2, 5, 6}, {1, 3, 4, 6},{2, 3, 4, 5}
4只牛的编号和不会大于18,所以输出5.

解题思路

动态规划。dp[k][i][sum] 表示从前 i 个奶牛中选出 k 个，他们的和为 sum 的方案数，则转移方程为：dp[k][i][sum]=dp[k][i-1][sum]+dp[k-1][i-1][(sum-i+n)%n]。在代码中，使用循环来压缩掉了 dp 的第二维。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import sys


def compute_res(n, k):
    dp = [[0] * n for _ in range(k + 1)]
    dp[0][0] = 1  # 取 0 个出来，和为 n 的倍数
    for i in range(n):
        for j in range(k, 0, -1):
            # 需要倒序循环，不然会覆盖掉
            for x in range(n):
                # 和为 x 的倍数
                dp[j][x] = (dp[j][x] + dp[j - 1][(x - i + n) % n]) % (1e9 + 7)
    return int(dp[k][0])


if __name__ == "__main__":
    n_k = sys.stdin.readline().strip().split()
    n, k = int(n_k[0]), int(n_k[1])
    print(compute_res(n, k))
Related Posts