KickStart 2020-Round-A python版解题
前言
第一次接触kick start，先刷了几轮体验一下，好久没有做类似的编程题目，不太会做了...
暂时使用Python编程，后续也会用C++再实现一遍。
RoundA 地址https://codingcompetitions.withgoogle.com/kickstart/round/
Round A
1. Allocation
有 n 套房子出售。买第一栋房子花了
美元。你有一个 B 美元的预算可以花。你最多能买多少套房子？
输入
输入的第一行给出了测试用例的数量，接下来是 T,T 测试用例。每个测试用例都以包含两个整数 N 和 B 的单行开始。第二行包含 N 个整数。
题解：分配问题，将单价进行升序排序，然后从小到大用B购买即可。(注：kick start不提供输入输出处理，需要自己对输入和输出进行标准化处理)
T=input()
for i in range(int(T)):
_=input().split(' ')
N=int(_[0])
B=int(_[1])
As=input().split(' ')
As=[int(_) for _ in As]
As.sort()
res=0
for a in As:
if a <= B:
res+=1
B-=a
if B<=0:
break
print('Case #{}: {}'.format(i+1,res))
2. Plates
有 N堆盘子。每个堆包含 K个 盘。每个盘子都有一个正值，描述它看起来是多么美丽。现在需要P个 盘子做晚餐。如果他想在一堆中拿一个盘子，他也必须在那堆中拿上面的所有盘子。挑选美丽值总和最大的P个盘子。
输入
每个测试用例都以包含三个整数 N，K 和 P 的一行开始，然后是 N行。第 i 行包含 K 个整数，从上到下描述每一堆里盘子的美丽值。
题解：整个问题可以描述成下图的情况，将盘子进行分配；从N*K中按照规则选取P个盘子，可以用动态规划的方法来实现
按照动态规划的思路，我们需要建立基本的动态规划公式，对应dp[i][j]，dp[N][K]就是最后要的结果。
分析过程如下
T=int(input())
for i in range(T):
N,K,P=[int(_) for _ in input().split(' ')]
Ns=[]
res=0
for _ in range(N):
Ns.append([int(_) for _ in input().split(' ')])
_sum=[]
_sum.append([0 for _ in range(K)])
for _ in Ns:
_tmp=[]
_tmp.append(0)
for idx,x in enumerate(_):
if not idx:
_tmp.append(x)
else:
_tmp.append(x+_tmp[-1])
_sum.append(_tmp)
res=[[0 for _ in range(P+1)] for _ in range(N+1)]
for n in range(1,N+1):
for p in range(P+1):
for x in range(0,min(K,p)+1):
res[n][p]=max(res[n][p],_sum[n][x]+res[n-1][p-x])
print('Case #{}: {}'.format(i+1,res[N][P]))
3. WorkOut
给定N个递增的正整数，然后向数组中插入K个正整数使得数组仍然递增，同时达到数组相邻元素差值最小；求插入后两个相邻元素差值的最大值是多少。
题解：题目的意思可以用下面一张图来表示，通过插入K个值使得数组相邻差值的最大值最小化
结果所需的最优差值
题解 可以看出这个题与最长公共前缀有关，可以使用字典树来辅助解题，将N个字符串用字典树进行表示，自根而下，每个节点对应一个字符，每个节点可以保存一个前缀重复数量，即有多少个字符串有相同的前缀(从根节点到当前节点)，字典树的形式如下图所示
同时，这个题目还符合贪心算法的思想，即计算最长公共前缀对应的分值就能得到最后的最大分值；公共前缀长度为
我们在具体实现时，按照递归的思路实现了下面的公式，在完整测试集上出现了递归超层的RuntimeError的错误。
from collections import defaultdict
class Char_Tree():
def __init__(self):
self.root={}
self.root.setdefault('num',0)
self.end='#'
def insert(self,word):
node=self.root
for char in word:
node=node.setdefault(char,{})
node.setdefault('num',0)
node['num']+=1
node[self.end]=None
T=int(input())
for t in range(T):
N,K=[int(_) for _ in input().split(' ')]
str_list=[]
for _ in range(N):
str_list.append(input())
predix=[]
ct=Char_Tree()
for _ in str_list:
ct.insert(_)
def travel(tree,step,_sum,ans ):
for _ in tree:
if _=='num' or _=='#':
continue
if tree:
s,ans=travel(tree[_],step+1,0,ans)
_sum+=s
#print('tree',tree)
tmp=(tree['num']-_sum)/K
if tmp:
ans+= tmp*step
_sum+=tmp*K
return _sum,ans
_,ans=travel(ct.root,0,0,0)
print('Case #{}: {}'.format(t+1,ans))
继而做了简单的修改，在创建字典树的同时计算得分值，这是一种很简单巧妙的方法，建树的过程就是从根向下的过程，而得分与公共前缀长度即节点的深度相对应，因此，在添加节点的过程中就可以计算得分，每个节点都做的操作，多个节点合起来就对应成上面提到的
的分数。
from collections import defaultdict
class Char_Tree():
def __init__(self,K):
self.root={}
self.root.setdefault('num',0)
self.end='#'
self._sum=0
self.K=K
def insert(self,word):
node=self.root
for char in word:
if char in node:
node=node[char]
self._sum-=node['num']//self.K
#node.setdefault('num',0)
node['num']+=1
self._sum+=node['num']//self.K
else:
node=node.setdefault(char,{})
node.setdefault('num',1)
self._sum+=1//self.K
#node[self.end]=None
T=int(input())
for t in range(T):
N,K=[int(_) for _ in input().split(' ')]
str_list=[]
for _ in range(N):
str_list.append(input())
predix=[]
ct=Char_Tree(K)
for _ in str_list:
ct.insert(_)
print('Case #{}: {}'.format(t+1,ct._sum))
END
本人简书所有文章均为原创，欢迎转载，请注明文章出处： https://www.jianshu.com/p/61876e60403d。百度和各类采集站皆不可信，搜索请谨慎鉴别。技术类文章一般都有时效性，本人习惯不定期对自己的博文进行修正和更新，因此请访问本人简书主页查看最新信息https://www.jianshu.com/u/40d14973d97c
。
