Codeforces Global Round 16 A-E
A. Median Maximization
n个非负数的和是s,问中位数最大可以是多少。
前一半都取0最优。
代码:
1 |
|
B. MIN-MEX Cut
给一个01字符串,一个01字符串的mex运算返回0/1/2。可以将所给的01字符串分割成若干个子字符串,问所有子字符串的mex总和最小是多少。
先将连续的相同字符都处理成一个字符。然后是一个01交替出现的字符串,考虑不分割时答案为2,所有1
可以拆成单独的子字符串,贡献为0,连续的一段0可以拆成一个子字符串,贡献为1,也就是看连续的0出现了几段,和2取min即可。
代码:
1 |
|
C. MAX-MEX Cut
在B题的基础变为两个01字符串,分割的时候两个字符串同步。求所有子字符串最大mex和。
例如:
1 | 01100 |
容易发现,除下列两种情况,其他都分割成长度为1的子字符串就是最优的。
1 | 01 |
分类讨论太麻烦了,选择了DP,DP[i]只会从DP[i-1]、DP[i-2]转移
1 |
|
D1. Seating Arrangements (easy version)
读完题就会了。求顺序对即可(甚至不用数据结构优化)。
代码:
1 |
|
D2. Seating Arrangements (hard version)
最后的结果是确定的,对于ai相同的,贪心从上到下,从右到左放置。
1 |
|
E. Buds Re-hanging
能切的先全部切出来。最后肯定形成了若干个深度为2、叶子数量大于0的子树。
然后将所有子树连接起来即可。显然将当前子树的根连接到上一个子树的一个叶子上是最优的。因此答案就是拆完之后的叶子总数-(子树的数量-1)
1 |
|