Round A 2020 - Kick Start 2020 - python 版代码

目录

1. Allocation
2. Plates
3. Workout
4. Bundling
   1. 字典树
   2. 递归（测试数据 2 会超过递归层数限制）

https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ffc7

Allocation

T 组数据，每组两行，第一行 N，B 代表有 N 个待售房屋，你拥有的钱是 B。第二行是 N 个整数，代表每个房屋的价格。
求能购买的最多房屋数量。

T = int(input())
for t in range(T):
    N, B = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    cnt = 0
    for x in a:
        if B < x:
            break
        cnt += 1
        B -= x
    print('Case #%d: %d' % (t+1, cnt))

Plates

T 组数据。每组数据 N + 1 行：第一行 N， K， P，代表有 N 摞盘子，每摞都是 K 个。一共需要挑出 P 个。后面 N 行每行是 K 个整数代表这摞盘子中每个盘子的颜值，顺序是从上到下。

需要保证挑出的盘子的颜值的和最大。

T = int(input())
for t in range(T):
    N, K, P = map(int, input().split())
    s = []
    for _ in range(N):
        s.append(list(map(int, input().split())))
    for i in range(N):
        for j in range(1, K):
            s[i][j] += s[i][j-1]
        s[i].append(0)
    dp = [[0] * (P+1) for _ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1, P+1):
            for x in range(0, min(j, K)+1):
                dp[i][j] = max(dp[i][j], dp[i-1][j-x] + s[i-1][x-1])
    print('Case #%d: %d' % (t+1, dp[N][P]))

Workout

T 组数据，每组两行，第一行 N，K 代表一个严格递增数列中有 N 个数，我们可以向其中插入 K 个任意数字。第二行是这 N 个整数。
插入数字后我们希望数列的相邻数字差的最大值尽可能小，求这个最小值。

import math
T = int(input())
for t in range(T):
    N, K = map(int, input().split())
    s = list(map(int, input().split()))
    d = []
    for i in range(1, len(s)):
        d.append(s[i]-s[i-1])
    maxv = max(d)
    if maxv < 2:
        print('Case #%d: %d' % (t+1, maxv))
    else:
        d.sort(reverse=True)
        l, r = 1, maxv
        while l < r:
            m = l + r >> 1
            ks = 0
            for dd in d:
                if dd <= m:
                    break
                ks += math.ceil(dd/m)-1
            if ks > K:
                l = m + 1
            else:
                r = m
        print('Case #%d: %d' % (t+1, r))

Bundling

把 N 个字符串分成 K 个组（N 一定被 K 整除）。每组的分数是这一组字符串最长公共前缀的和。求全局分数最大

字典树

T = int(input())
for tt in range(T):
    N, K = map(int, input().split())
    ss = []
    for _ in range(N):
        ss.append(input())
    base = ord('A')
    class TrieNode:
        def __init__(self):
            self.cnt = 0
            self.children = [None] * 26
        def add(self, s):
            self.cnt += 1
            if not s:
                return
            
            if not self.children[i]:
                self.children[i] = TrieNode()
            self.children[i].add(s[1:])
    root = TrieNode()
    for s in ss:
        t = root
        for ch in s:
            t.cnt += 1
            i = ord(ch) - base
            if not t.children[i]:
                t.children[i] = TrieNode()
            t = t.children[i]
        t.cnt += 1
    cnt = 0
    root.cnt = 0
    stack = [root]
    while stack:
        t = stack.pop()
        cnt += t.cnt // K
        for c in t.children:
            if c and c.cnt >= K:
                stack.append(c)
    print('Case #%d: %d' % (tt+1, cnt))

递归（测试数据 2 会超过递归层数限制）

T = int(input())
for t in range(T):
    N, K = map(int, input().split())
    ss = []
    for _ in range(N):
        ss.append(input())
    ss.sort()
    cnt = [0]
    def find(i, j, k):
        s = i
        while s < j and k >= len(ss[s]):
            s += 1
        x = s
        while s < j:
            while x < j and ss[x][k] == ss[s][k]:
                x += 1
            if x - s >= K:
                cnt[0] += (x - s) // K
                find(s, x, k+1)
            s = x
    find(0, len(ss), 0)
    print('Case #%d: %d' % (t+1, cnt[0]))