前言
第一次接觸kick start违帆，先刷了幾輪體驗(yàn)一下浙巫，好久沒有做類似的編程題目，不太會(huì)做了...
暫時(shí)使用Python編程前方，后續(xù)也會(huì)用C++再實(shí)現(xiàn)一遍狈醉。
RoundA 地址https://codingcompetitions.withgoogle.com/kickstart/round/
Round A
1. Allocation
有 n 套房子出售。買第一棟房子花了
美元惠险。你有一個(gè) B 美元的預(yù)算可以花苗傅。你最多能買多少套房子？
輸入
輸入的第一行給出了測(cè)試用例的數(shù)量班巩，接下來是 T,T 測(cè)試用例渣慕。每個(gè)測(cè)試用例都以包含兩個(gè)整數(shù) N 和 B 的單行開始。第二行包含 N 個(gè)整數(shù)抱慌。
題解：分配問題抑进，將單價(jià)進(jìn)行升序排序强经，然后從小到大用B購(gòu)買即可。(注：kick start不提供輸入輸出處理寺渗，需要自己對(duì)輸入和輸出進(jìn)行標(biāo)準(zhǔn)化處理)
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堆盤子匿情。每個(gè)堆包含 K個(gè) 盤兰迫。每個(gè)盤子都有一個(gè)正值，描述它看起來是多么美麗【娉疲現(xiàn)在需要P個(gè) 盤子做晚餐汁果。如果他想在一堆中拿一個(gè)盤子，他也必須在那堆中拿上面的所有盤子玲躯。挑選美麗值總和最大的P個(gè)盤子据德。
輸入
每個(gè)測(cè)試用例都以包含三個(gè)整數(shù) N，K 和 P 的一行開始跷车，然后是 N行棘利。第 i 行包含 K 個(gè)整數(shù)，從上到下描述每一堆里盤子的美麗值姓赤。
題解：整個(gè)問題可以描述成下圖的情況赡译，將盤子進(jìn)行分配；從N*K中按照規(guī)則選取P個(gè)盤子不铆，可以用動(dòng)態(tài)規(guī)劃的方法來實(shí)現(xiàn)
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個(gè)遞增的正整數(shù)，然后向數(shù)組中插入K個(gè)正整數(shù)使得數(shù)組仍然遞增劳坑，同時(shí)達(dá)到數(shù)組相鄰元素差值最斜锨础；求插入后兩個(gè)相鄰元素差值的最大值是多少距芬。
題解：題目的意思可以用下面一張圖來表示涝开，通過插入K個(gè)值使得數(shù)組相鄰差值的最大值最小化
線性搜索最優(yōu)差值就可以得到目標(biāo)結(jié)果，但時(shí)間復(fù)雜度較高离斩，會(huì)超時(shí)银舱；因此可以嘗試二分搜索，從中找出最優(yōu)差值跛梗，檢驗(yàn)當(dāng)前差值是否都符合劃分次數(shù)的限制要求即可寻馏，時(shí)間復(fù)雜度明顯下降。
import math
T=int(input())
for t in range(T):
N,K=[int(_) for _ in input().split(' ')]
ts=[int(_) for _ in input().split(' ')]
delta=[]
for i,_ in enumerate(ts):
if not i:
continue
delta.append(_-ts[i-1])
def check(t):
_sum=[]
for _ in delta:
_sum.append(math.ceil(_/t)-1)
return sum(_sum)<=K
max_d=max(delta)
left=1
right=max_d
_ans=0
while left<=right:
mid=(left+right)//2
if check(mid):
right=mid-1
_ans=mid
else:
left=mid+1
print('Case #{}: {}'.format(t+1,_ans))
4. Bundling
給定N個(gè)字符串核偿，把其分配到大小為K的多個(gè)組里(K能整除N)诚欠；每個(gè)串僅能劃分到某一個(gè)組里面，且這個(gè)組的得分就等于該組所有字符串的最長(zhǎng)公共前綴的長(zhǎng)度。求劃分后各組最大分?jǐn)?shù)和轰绵。
The score of a group is equal to the length of the longest prefix shared by all the strings in that group. For example:The group {RAINBOW, RANK, RANDOM, RANK} has a score of 2 (the longest prefix is 'RA').
The group {ALLOCATION, PLATE, WORKOUT, BUNDLING} has a score of 0 (the longest prefix is '').
題解 可以看出這個(gè)題與最長(zhǎng)公共前綴有關(guān)家乘，可以使用字典樹來輔助解題，將N個(gè)字符串用字典樹進(jìn)行表示藏澳，自根而下，每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)字符耀找，每個(gè)節(jié)點(diǎn)可以保存一個(gè)前綴重復(fù)數(shù)量翔悠，即有多少個(gè)字符串有相同的前綴(從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn))，字典樹的形式如下圖所示
我們?cè)诰唧w實(shí)現(xiàn)時(shí)融求，按照遞歸的思路實(shí)現(xiàn)了下面的公式咬像，在完整測(cè)試集上出現(xiàn)了遞歸超層的RuntimeError的錯(cuò)誤。
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))
繼而做了簡(jiǎn)單的修改吃度，在創(chuàng)建字典樹的同時(shí)計(jì)算得分值杭攻，這是一種很簡(jiǎn)單巧妙的方法庇勃，建樹的過程就是從根向下的過程，而得分與公共前綴長(zhǎng)度即節(jié)點(diǎn)的深度相對(duì)應(yīng)倒彰，因此，在添加節(jié)點(diǎn)的過程中就可以計(jì)算得分蔑赘，每個(gè)節(jié)點(diǎn)都做的操作狸驳，多個(gè)節(jié)點(diǎn)合起來就對(duì)應(yīng)成上面提到的
的分?jǐn)?shù)。
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
本人簡(jiǎn)書所有文章均為原創(chuàng)缩赛，歡迎轉(zhuǎn)載耙箍，請(qǐng)注明文章出處： http://www.reibang.com/p/61876e60403d。百度和各類采集站皆不可信酥馍，搜索請(qǐng)謹(jǐn)慎鑒別辩昆。技術(shù)類文章一般都有時(shí)效性，本人習(xí)慣不定期對(duì)自己的博文進(jìn)行修正和更新旨袒，因此請(qǐng)?jiān)L問本人簡(jiǎn)書主頁(yè)查看最新信息http://www.reibang.com/u/40d14973d97c
汁针。
