EDU-CFR-114(Div.2) 解题报告

cxm1024 · 2021-10-12 21:42:52 · 个人记录

更好的阅读体验

赛时AC 2道题，赛后补题做出来一道（赛时交了4发，赛后交了十几发才过，太残忍了）

总体难度比较高，可能题解会比较冗长

A. Regular Bracket Sequences

Problem

输入 n，输出 n 个互不相同的、合法的、长度为 2n 的括号序列。

Solution\ 1

update: 我的解法非常复杂，可以直接看 Solution\ 2 CF官方题解的做法（想看看我的憨批做法也行）

考虑一开始在 (0,0) 点，左括号往右上走，右括号往右下走，则合法的括号序列一定在 x 轴之上。现在考虑最简单的括号序列：(((...(())...)))，即

展现在坐标系上，就是一个山峰形，那么我们考虑将山峰的顶砍一刀，让它凹进去，变成

这样就得到了下一种合法序列，再下一种就再把左边的山峰砍一刀（自始至终都不管右边），每次砍左边的山峰，由于最初的山峰高度为 n，每砍一刀左边的山峰高度 -1，看 n-1 刀的最终高度为 1，加上最初的单峰山，就得到了 n 种合法括号序列。

实现上，把最初的 {+1,+1,...,+1,+1,-1,-1,...,-1,-1} 序列存到数组里，每次交换一对 +1,-1 变成 -1,+1，再转换成括号序列输出即可。

Solution\ 2

CF官方题解，让我觉得我的解法太复杂了。直接引用英文原版，肯定能看懂。

start with the sequence ()()()()...; merge the first 4 characters into one sequence to get (())()()...; merge the first 6 characters into one sequence to get ((()))()...; and so on.

B. Combinatorics Homework

Problem

你有 a 个 A、b 个 B、c 个 C，问能否组成“恰好有 m 对相邻两个字符相同”的字符串。

Solution

显然，只要 m 在“相邻两个字符相同的对数”的最大值和最小值之间，就一定可以。最大值很简单，若干个 A、若干个 B、若干个 C 这样排，(a-1)+(b-1)+(c-1) 就行（别忘了 \max(0,...)），问题是最小值怎么求呢？我们可以发现一种典型情况：最大值太大，两个较小值用尽浑身解数拆散，最大值也还有剩余；还有一种情况就是两个较小值不需要用全部的力气拆散，数量最多的字母已经被拆得一对也没有了。针对后者，我们很轻松的就能猜出来一定总能互相拆的一对也不剩，无需多考虑，而针对前者，需要算出来两个数量较少的字母用尽浑身解数能把数量最大的拆得还剩几对。我们发现 ABABAAAA 和 AABAABAA 是一样的，于是我们又可以得到，尽可能多的拆散，就是把较少的两种字母分散开插进最多的字母里，怎么插无所谓，只要它们自己不连在一起就行。这样我们能够得到，针对前一种情况，能组成的对数的最小值为 max-1-(all-max)（感性理解一下），将它和 m 比较即可。

C. Slay the Dragon

Problem

你有 n 个勇士，每个勇士有一定的能力值 a_i，每组数据给出一条龙的防御力 x 和攻击力 y，你需要派出一个能力值 \ge x 的勇士来攻击龙，剩余的勇士防御，防御的勇士能力值之和必须 \ge y。你每次可以花费 1 的代价将一个勇士的能力值提高 1，对于每组数据，回答最少花费。注意：每组数据相互独立，每组数据提高的勇士能力值不会保存到下一组数据。

Solution

这题竟然卡常！！！（痛骂 Codeforces）可能需要用 ios::sync_with_stdio(false) 才能过

很容易想到，每次可以用比龙的防御力小的能力值最大的人去打龙（给他提高一点），或是用第一个比龙的防御力大的人去打龙（不需要提高），然后再按需提高剩下的人（提高谁都没有区别，只需要考虑他们的和就行），取这两种方案中花费较小的一种。然后你就会发现细节巨多，当调了 n 遍终于调出错来时，你就会发现

Time limit exceeded on test 6

加上 ios::sync_with_stdio(false) 或快读可过（如果你是 scanf 党，当我没说）。