满减优惠

规模很小的背包问题。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)的。