第七届传智杯初赛第二场（abc三组）Python题解详解与补题攻略

文章目录

前言

在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(奇,奇)
涉及到的预计算阶乘、逆元求组合数可查看我的博客 [点此进入]

题解：

mod = 10 ** 9 + 7

def C(n, m):
    p, q = 1, 1
    for i in range(1, m + 1):
        p = p * (n - i + 1) % mod
        q = q * i % mod
    return p * pow(q, mod - 2, mod) % mod

def A(n, m):
    p = 1
    for i in range(1, m):
        p = p * (n - i + 1) % mod
    return p % mod

n = int(input())
even = n // 2  # 偶数个数
odd = n - even  # 奇数个数
# A(odd,odd)*A(even,even)*C(even+1,odd)
print(A(odd, odd) * A(even, even) * C(even + 1, odd) % 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组)

思路分析：

环形区间DP问题

【算法】动态规划专题⑫ —— 环形区间DP python

题解：

n = int(input())
a = list(map(int, input().split()))
a += a
dp = [[0] * n * 2 for _ in range(n * 2)]
for i in range(n * 2):
    dp[i][i] = a[i]

for len in range(2, n + 1):
    for i in range(n * 2 - len):
        j = i + len - 1
        step = len
        dp[i][j] = max(dp[i + 1][j] + a[i] * step, dp[i][j - 1] + a[j] * step)
ans = 0
for i in range(n):
    ans = max(ans, dp[i][i + n - 1])
print(ans)

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.

思路分析：

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

作者：查理零世