Python实战 – CF R916(Div.3) #1914

明天信息技术Python考试，今天用Python写一下Div3锻炼一下代码能力。

T1 Problemsolving Log

题意：

Monocarp在完成一些任务，他完成任务A需要1分钟，任务B需要2分钟……给出一串长度为 n 的字符串，由大写字母构成，表示Monocarp在 i 分钟完成的任务是什么，判断Monocarp可以完成多少个任务。

分析：

即判断字母数量，模拟即可。

Code：

T = int(input())
while(T) :
    n = int(input())
    s = input()
    dic = [0] * 30
    for i in s:
        dic[ord(i) - ord('A') + 1] += 1
    cnt = 0
    for i in range(1, 27):
        if dic[i] >= i: cnt += 1
    print(cnt)
    T -= 1

T2 Preparing for the Contest

题意：

Monocarp在做题，共有 n 个题，每个题的难度为 1,2,3,\ldots,n ，Monocarp仅在做当前题的难度比前一个题大时才会兴奋，给出 n 和 k ，求一个能让Monocarp兴奋 k 次的做题顺序。

分析：

不让他兴奋，递减；让他兴奋，递增，输出即可。

Code：

T = int(input())
while(T) :
    a, b = input().split()
    a, b = int(a), int(b)
    tmp = a - b
    for i in range(tmp, 0, -1):
        print(i, end = " ")
    for i in range(tmp + 1, a + 1):
        print(i, end = " ")
    T -= 1

T3 Quests

题意：

有 n 个任务，在完成 i 任务时，i 之前的所有任务都必须完成。同时，可以多次完成某个任务。总共可以做 k 次任务，第一次完成 i 任务的贡献为 a_i ，后面完成 i 任务的贡献为 b_i ，求最大贡献。

分析：

先走完，然后往后退，把后面一段转化为前面最大的 b_i。

只要维护每位上的前面一段的最大的 b_i 即可。

Code：

T = int(input())
while(T) :
    n, k = input().split()
    n, k = int(n), int(k)
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    c = [0] * (n + 1)
    mx = b[0]
    sum = 0
    ans = 0
    for i in range(0, min(n, k)):
        mx = max(b[i], mx)
        c[i] = mx #预处理
        sum += a[i]
    sum += mx * max(k - n, 0)
    ans = sum
    #print(ans)
    tmp = max(0, k - n)
    for i in range(min(n, k) - 1, 0, -1): #退回
        sum -= c[i] * tmp
        tmp += 1
        sum -= a[i]
        sum += c[i - 1] * tmp
        ans = max(ans, sum)
    print(ans)
    T -= 1