CSP-S 2021 补题记录

Jr_Zlw · 2021-11-14 19:45:22 · 个人记录

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

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

[CSP-S 2021] T3 回文 palin

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

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

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

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

复杂度 O(\sum n) 。code

[CSP-S2021] T1 廊桥分配 airport

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

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

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

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

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

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

时间复杂度 O(nlogn) 。code

[CSP-S 2021] T2 括号序列 bracket

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

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

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

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

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

[CSP-S 2021] T4 交通规划 traffic

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

理解了个大概，不过代码几乎是对着题解打的 TAT 所以还是请移步洛谷题解区。

不过为了文章的完整性还是随便写写，（不建议浪费时间细看）。

首先最重要的一点： 看懂题意 。看懂之后 k=2 的 45 分其实很好想。

考虑 k=2 的时候：

• 两个点颜色相同，答案为 0 。
• 两个点颜色不同，贪心地想，黑白双色点会将图分为两块。恰好连接在不同色块之间的边会产生贡献。
• 于是可以再将图进行转化，将一个四边围成的格子看成一个点，两个格子的共边权为两点间的边权。
• 就从一个边界上的大点(即射线间的点)跑一遍最短路就能出答案了。

然后考虑扩展为大问题。实际上可以发现，这张图还是会被分为很多个不同色块。

然后实际上就变成每个不同颜色点之间两两配对产生的答案。

同时可以看到一个区间内的配对点不会交叉选择（肯定不优）。

所以断环成链，区间 \rm{DP} ，经典套路，欢迎来玩 。复杂度 O(k^3+knmlog(nm)) 。No Code。

细节很多，很不好写。所以我是对着题解打哒！ 。比较恶习的是建图和多组数据的清空。。。

NOIP 2021 rp++