CSP-S 2021 补题记录

2024-02-12 17:10:52

赛时伞兵思路请浏览CSP-S 2021 游记。

按题目难度升序排序。对某排题人充满无限的恶感。

[CSP-S 2021] T3 回文 palin

一个比较显然的事实：第一次选出来的数，它的第二次出现必然在最后。

假设我们已经选出了一个数，那么考虑在选第二个数的时候必须使它们在最后连续地出现。然后就做完了。

具体到实现，每一次从头/尾取一个数，处理出这个数第二次出现地位置。考虑如果合法，它们第二次出现地位置一定会在序列中间形成一段连续的区间。所以只需要判一下最后能不能在中间这个区间外选完其他所有数就行了。

还有一个小考虑，就是这个做法和直接爆搜有点像的地方在于它看起来也需要从正反两面去考虑是否合法。然而可以证明这是不用的。我们可以考虑每次选走一个数，中间的区间必然扩大，更有可能使后面的数被选入，所以每次合法的选择都是不劣的，所以放松地贪心去选即可。

复杂度 \(O(\sum n)\) 。code

看上去就应该有个 \(O(nlogn)\) 做法，就往数据结构这方面想。

首先按照暴力的思路，我把所有航班都映射到时间轴上，在时间轴上想办法。

可以发现，由于先到先得的原则，一架飞机停在廊桥上的代价是固定的。

(~~读者自证不难~~) 就大概手玩一下就发现了。说明起来挺麻烦的。

那么就可以预处理每一架飞机的代价，然后做个前缀和，最后枚举分配方案统计答案即可。

具体到实现，可以假定现在有无限的廊桥，用一个小根堆维护当最小的空闲廊桥，每次贪心地填进去就行了，然后记录下这个最小的廊桥，该飞机的代价就是该廊桥的编号（即至少要这么多的廊桥才能放的下它）。然后把代价统计进一个计数桶里，做个前缀和。枚举分配方式，从两边的前缀和数组中直接查询取最大值即可。

时间复杂度 \(O(nlogn)\) 。code

首先这个数据范围就非常明显地提示是个 \(O(n^3)\) 大概就是个区间 \(\rm{DP}\) 啥的可是我当时就是连暴力都打不出来。

赛后。。。考虑根本无需考虑题目给出的“超级括号序列“有什么性质，只需直接根据定义无脑区间 \(\rm{DP}\) 就行。

从定义去考虑解法，我们设 \(dp[l][r][type]\) 表示在区间 \([l,r]\) 内满足 \(type\) 性质的串的方案数。

虽然但是，懒得 \(\LaTeX\) 了，就看情况转移一下，具体看代码。

时间复杂度 \(O(n^3)\) ，带了 \(6\) 倍常数。code

在补了在补了。预计 \(\rm{NOIP}\) 前应该能补完罢 \(\rm{Q \omega Q}\) 。