第七届传智杯初赛第二场（abc三组）补题+题解python

标签：max 题解 初赛 range 补题 ans input mod

文章目录

• 前言
• A 计算商品打折结算金额(B组、C组)
• B 茶杯和球(A组、C组)
• C 游游的字母串(A组、B组、C组)
• D 电梯(B组、C组)
• E 小欧的排列计算(A组、B组、C组)
• F 游游的字母子串(A组、B组、C组)
• G 跳跳跳(A组、B组)
• H 小红的战争棋盘(A组)

---

前言

---

在CSDN上并未找到第七届传智杯初赛第二场的相关题解，于是自己写了一个供大家参考。
附上补题链接 点此进入https://ac.nowcoder.com/acm/contest/100449#question

---

A 计算商品打折结算金额(B组、C组)

思路分析:

通过f-string格式化输出（python3.6以上）

题解：

n = float(input())
if n >= 5000:
    ans = n * 0.6
elif n >= 2000:
    ans = n * 0.7
elif n >= 500:
    ans = n * 0.8
elif n >= 100:
    ans = n * 0.9
else:
    ans = n
print(f"{ans:.1f}")

B 茶杯和球(A组、C组)

思路分析:

将球所在的杯子打上标记即可

题解：

n, x, k = map(int, input().split())
a = [0] * n
a[x - 1] = 1
for _ in range(k):
    i, j = map(int, input().split())
    a[i - 1], a[j - 1] = a[j - 1], a[i - 1]
print(a.index(1) + 1)

C 游游的字母串(A组、B组、C组)

思路分析：

仅包含小写字符串，最后所有元素要求变成相同的。因为只有26种情况，不妨从答案入手，逆向解题：
遍历从a到z，通过check函数返回需要的次数。

题解：

from math import inf

s = input()
ans = float(inf)


def check(x):
    sum = 0
    for i in s:
        res = abs(ord(i) - x)
        if res > 13:
            res = 26 - res
        sum += res
    return sum


for i in range(97, 123):
    ans = min(ans, check(i))

D 电梯(B组、C组)

思路分析：

简单的模拟题：sum1和sum2分别表示两个电梯各自的时间

题解：

n = int(input())
a = list(map(int, input().split()))
sum1 = a[0] 
sum2 = a[1]  # 初始化
for i in range(2, n):
    if sum1 < sum2:
        sum1 += a[i]
    else:
        sum2 += a[i]
print(max(sum1, sum2))

E 小欧的排列计算(A组、B组、C组)

思路分析：

所有相邻两个数的乘积均为偶数 即两个奇数不会相邻
数学排列组合（插空法 ）偶数排列完后将奇数插入空中 A(偶,偶)*C(偶+1,奇)*A(奇,奇)
涉及到的预计算阶乘、逆元求组合数可查看我的博客 [点此进入]

题解：

def pre(max_n, mod):  
    f = [1] * (max_n + 1)  
    i_f = [1] * (max_n + 1)  

    for i in range(1, max_n + 1):
        f[i] = f[i - 1] * i % mod

    i_f[max_n] = pow(f[max_n], mod - 2, mod)

    for i in range(max_n, 0, -1):
        i_f[i - 1] = i_f[i] * i % mod

    return f, i_f  

def comb(n, k, f, i_f, mod):  

    if k > n or k < 0:
        return 0
    return (f[n] * i_f[k] % mod * i_f[n - k] % mod) % mod

mod = 10 ** 9 + 7
n = int(input())
even = n // 2   # 偶数个数
odd = n - even  # 奇数个数
f, i_f = pre(n, mod)
c = comb(even + 1, odd, f, i_f, mod)
print(f[odd] * f[even] * c % mod) 

F 游游的字母子串(A组、B组、C组)

思路分析：

连续子串常常使用滑动窗口技术。
1.维护一个有条件的不定长滑动窗口；
2.右端点右移，导致窗口扩大，不满足条件；
3.左端点右移，为了缩小窗口，重新满足条件

种类不超过k可以使用哈希表（字典）统计个数实现
数据结构defaultdict相关用法 可见我的博客 点此进入

题解：

from collections import defaultdict

n, k = map(int, input().split())
s = input()
ans = left = 0
dict = defaultdict(int)  
for right in range(n):
    dict[s[right]] += 1
    while len(dict) > k:
        dict[s[left]] -= 1
        if dict[s[left]] == 0:
            dict.pop(s[left])
        left += 1

    ans = max(ans, right - left + 1)
print(ans)

G 跳跳跳(A组、B组)

思路分析：

动态规划：
环形跳跃的问题可以通过将环拆成一个线性问题来处理例如，如果选择从位置k作为起点，可以将备份a重新排为a[k], a[k+1], …, a[n], a[1], …, a[k-1]。

题解：

def solve(n, a):
    # 双倍长度的数组以便于线性处理环
    a = a + a
    dp = [[0] * (2 * n) for _ in range(2 * n)]
    # 初始化单格子的得分
    for i in range(2 * n):
        dp[i][i] = a[i] * n

    # 枚举长度从1到n-1
    for length in range(1, n):
        for l in range(2 * n - length):
            r = l + length
            step = n - (r - l)
            dp[l][r] = max(dp[l + 1][r] + step * a[l], dp[l][r - 1] + step * a[r])

    # 取 n 个连续格子的最大值
    max_result = 0
    for i in range(n):
        max_result = max(max_result, dp[i][i + n - 1])

    return max_result


n = int(input())
a = list(map(int, input().split()))
print(solve(n, a))

H 小红的战争棋盘(A组)

示例一：
输入：

3 3 2
ranko 1 1
kotori 2 2
5
ranko D
ranko W
ranko A
kotori W
kotori W

输出：

vanquish!
out of bounds!
peaceful.
ranko wins!
unexisted empire.

思路分析：

大模拟太麻烦哩，最后选择放弃。
有做出来的小伙伴可以留言讨论哦！

标签：max,题解,初赛,range,补题,ans,input,mod
From： https://blog.csdn.net/2401_87245677/article/details/145125527