【2019】CSP-J2 / S2 简要题解 + 总结

· · 个人记录

简要题解

J-T1 数字游戏

需要说什么吗（

J-T2 交通换乘

我们可以将对于每一次公交车，可以使用的地铁票的条件概括为三点：

  1. 时间差小于等于 45 分钟

  2. 票价大于等于当前公交车的价钱

  3. 满足上述条件的地铁票中，时间最早的

注意到题目的读入是依照时间顺序的，所以只要我们维护一个队列，每次及时弹出 “时间差大于 45 分钟” 的队首元素，那么在剩下的元素里，从前往后第一个满足 “票价大于等于当前公交车的价钱” 的地铁票肯定是符合题目要求的（原理显然）。

我们使用一个票不一定能及时弹出去，所以我们要打个标记，表示是否使用过；相应的，在每次弹出队首元素时如果碰到使用过的票，则也要弹出。但也许会有一个疑问 —— 如果使用过的票不及时弹出，那么会不会队列每次要遍历很久才能找到一个未使用的票？不会，因为地铁的时间是互不相同的，所以算法的时间复杂度至多为 O(45n)。

J-T3 纪念品

首先，考虑只有一个物品的情况。 每个方案无非就是由若干个 “持有 —— 卖出” 纪念品组成，那么有两种情况（约定 a_i 代表第 i 天该纪念品的价格）：

  1. 只存在于第 i 天买入，在第 i+1 天卖出的情况，则我们这样考虑：视该纪念品的重量 w_i = a_i ，价值为 v_i = a_{i+1} - a_{i}，则可以将本题转换为一个 T 天、1 个物品的完全背包模型（有物品件数、背包容量、物品的价值和重量，并且每个物品选的件数不限）。

注意这里存在一个性质 —— 由于第 i+1 天只用到了第 i 天的最优解作为 “本金”，所以要传递第 i 天的最优解到第 i+1 天，除此以外第 i 天与第 i+1 天没有任何关联。

  1. 存在于第 i 天买入，在第 k(k > i+1) 天卖出的情况，则我们可能要考虑第 i 天时该物品买入的时间，这样复杂度就大大提高了。我们试着将这种复杂的情况归约到简单的情况（上一种情况）上。

注意到题目里 “当日购买的纪念品也可以当日卖出换回金币” 这句话，它提示我们 —— 对于上述第二种情况，可以将其拆解为第 i 天买入，然后第 i+1 天先全部卖出、再全部买入（易得证不会耗费任何金币），然后第 i+2 天先全部卖出、再全部买入 …… 一直到第 j 天先全部卖出，再全部买入。

关注其与第一种情况的共同点，则我们易想到 —— 强制每一个纪念品在第 i 天买入后，在第 i+1 天立刻全部卖出。在这之后，如果买入的数量与第 i 天的相同，则实际上与上述第二种情况相同；而如果买入的数量与第 i 天的不同，则可以视作在原来未拆解的方案中，在第 i+1 天又多买入 / 卖出新的纪念品。换句话说，这种拆解可以对应任何未拆解的原方案，这样我们就可以将本题全部转换为第一种情况。

接下来扩展到 n 个物品的情况。我们可以这样思考 —— 由于每种物品只有买入、卖出两种操作，且操作次数无限次，所以我们可以将每种物品的买入、卖出放在一起操作。那如果在买入某种物品的时候，金币数降为负怎么办？则可以将后面某个物品的买入、卖出放在这之前，这个顺序是任意的。换而言之，每种物品的操作是相互独立的，不会存在 “买入 / 卖出某个物品的顺序影响是否能买入 / 卖出某个物品” 的问题，于是将本题化成 一个 T 天、n 个物品的完全背包模型，从而得到彻底解决。

算法的时间复杂度为 O(Tn~·~max(m))（max(m) 指执行过程中的最大金币数），而且空间复杂度可以利用完全背包的性质优化到一维，加上 register 优化跑过本题还是绰绰有余的。

J-T4 零件加工

S-D1-T1 格雷码

根据题面显而易见可得（f_{n,k} 含义显而易见）：

f_{n,k} = f(n-1, k) ~(k < 2^{n-1}) f_{n,k} = f(n-1,n-k-1) ~(k \geq 2^{n-1})

对着做就行，记得 ull 就行。

S-D1-T2 括号树

首先，注意到题目中有两个关键点：

  1. 题目的核心是，求出括号序列中合法的括号序列子串的个数。

  2. 题目给定了一个树，任意两个结点间有且仅有一条简单路径。

有经验的选手可以快速想到，我们可以利用动态规划的思想，设 v_i 代表每个结点的答案，则我们可以依照层数向下遍历，只要保证 v_{root_i} 已经正确地求出，那我们就可以利用类似栈的做法，将 v_i 求出。

用栈求解括号序列子串的个数，这应该是提高组 OIer 的必备技能，这里不多提了，不过稍微提及状态设计的一个要点。注意到对于任意结点 i 的答案，相当于以 i 结尾的合法子串个数 + 以 root_i 结尾的合法子串个数 + 以 root_{root_i} 结尾的合法子串个数 + ... + 以根节点结尾的合法子串个数。如果我们将 v_i 定义为以 i 结尾的合法子串个数，那么不仅考虑的情况会比上一个定义更少，并且求出最终结果也很简单 —— 做一个前缀和即可，所以定义成这种状态会更优（我考场就是没有这样转过弯来，然后死的）。

下面直接给出状态转移方程。设 pre_i 为到当前结点时上一个未匹配的左括号，则有：

  1. 先将 pre_i = pre_{root_i}（也就是假设未匹配的左括号没有减少、没有增加），方便下面表示。

  2. 当 a_i 为左括号时，v_i = 0，pre_i = i（未匹配的左括号增加）。

  3. 当 a_i 为右括号，且有可以匹配的左括号时，v_i = 1 + v_{root_{pre_i}}（也就是说，当前这个新的匹配能与 v_{root_{pre_i}} 个括号序列连起来，组成新的答案），pre_i = pre_{root_{pre_i}}（pre_i 已经被匹配掉了）。

算法的时间复杂度为 O(n)，并且注意到题目有 1 \leq f_u < u 这个性质，所以以上这个过程甚至只用循环一遍就行，

已知失误