offer收割编程练习赛4简要分析

3
1

满减优惠

规模很小的背包问题。O(2^N)的枚举或者DP可以搞定。

积水的城市

稀疏图最短路,可以参考 https://hihocoder.com/problemset/problem/1093

罚抄一百遍

经过分析可以发现每行的开头或者是一个单词,或者是一个空格。设文本中的单词数是T,则在2T行以内必然出现循环。 例如样例在第8行开始循环:

123456789
Good good
 study   
day day   
up Good  
good     
study day
 day up  
Good good (开始循环)

值得一提的是循环不一定从第1行开始,例如对于M=6是2-7行循环。

123456
Good  
good  
study 
day 
day up
 Good
good  
study 
day 
day up

根据循环节计算最后一个字符的位置,复杂度是O(T)的。不过这题细节很多,不容易写对。

分隔相同整数

首先分析一下什么情况下是无解的。设当前数目最多的整数有C个,易知当且仅当C + C - 1 > N时无解。

所以我们需要在保持C + C + 1 <= N的情况下,尽量选字典序小的数排在前面。利用带索引的堆可以使选择一个整数复杂度是O(logN)的。

0 answer(s)

write answer 切换为英文 切换为中文


转发分享