明天信息技术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仅在做当前题的难度比前一个题大时才会兴奋,给出 nk ,求一个能让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