Educational Codeforces Round 114 A-D
A. Regular Bracket Sequences
请你构造n个长度为2n的不同的合法括号序列。
如下构造即可。
1 | () |
B. Combinatorics Homework
问是否存在这样的字符串:
- 恰好有a个字母’A’
- 恰好有b个字母’B’
- 恰好有c个字母’C’
- 没有其他字母
- 有m对相同的相邻字母对
计算最大和最小的相同相邻字母对数量,判断m是否在中间即可。
最大构造就是AAA..BBB..CCC
最小构造就是拿出最多的那种字母,另外两种字母隔板插入
代码:
1 |
|
C. Slay the Dragon
有n个士兵,每个士兵有力量$a_i$。你可以用1个花费增强某个士兵的力量1.
每次询问有一条恶龙。恶龙有攻击力和防御力,你需要派出一个力量大于等于恶龙防御力的士兵进攻恶龙,并且其他士兵的力量和要大于等于恶龙攻击力。各询问独立,每次输出最小花费。
考虑贪心选取进攻的士兵:
如果选取的士兵力量太大,远大于恶龙的防御,导致浪费。
如果选取的士兵力量太小,可能其他士兵的力量和远大于恶龙的攻击力,导致浪费。
因此肯定会选择排序后,第一个力量大于等于恶龙的士兵 或 是最后一个力量小于恶龙的士兵进攻。
代码:
1 |
|
D. The Strongest Build
有n个装备栏和n种装备,每种装备有若干个,每个装备有一个力量值$a_{ij}$,同一种装备只能选取一个装在固定的装备栏上。同时有m个套装被禁用了,请问最大的装备组合力量是多少。保证至少有一套装备未被禁用。
如果最大装备组合未被禁用,那就选取最大装备组合,否则,最优组合肯定是在某一种禁用套装的基础上,选取某一种装备的前一个。
代码
1 |
|