CSP2021游记

发表于 2022-06-05 分类于学术阅读次数： Disqus：

…

前言

这次CSP-S的难度较往年偏高，发挥也不太理想。没有一道题是很简单的题，部分分也给的不多。预估分数为100+28+28+0=156。

并没有很简单，但也不是特别复杂。本题可以用多种数据结构维护，从priority_queue到Splay都行，算法思路大致相同。本人在这只讲解自己的思路。

我们先使每架飞机进站时使用可使用的编号最小的廊桥，我们只需要维护一下廊桥的空闲情况和在廊桥中的飞机编号与出站时间即可（我采用的是两个priority_queue实现）。就可以维护出所有飞机可使用廊桥的最小廊桥数，然后随便统计一下即可。

我在考场上想过这样一个问题，如果一个飞机由于廊桥数目不够导致未使用廊桥，以至于之后的飞机使用廊桥的最小廊桥数减小，会对这种方法的正确性产生影响吗？(如果没有这个疑问可以直接跳过，不要被误导)

并不会。因为若会出现这种情况，就一定是前一架飞机的廊桥使用编号大于后面的飞机的廊桥编号，这时前一架飞机对后一架飞机无任何影响，因为每次进入的飞机一定是寻找可以用的最小编号廊桥。

这道题的方法也是多种多样，主要就是区间DP。

首先很容易想出一个 $n^4$ 的DP(就不写了)。但是注意这种情况：

()()()

如果你的方法会判重，说明方法没对，需要修改（不过我也不知道怎么改 $\dots$ ）。如果没有判重，加一个前缀和即可。

还有一种，就是维护三个不同的数组 SA、AS、ans(与题中定义相同)，然后就可以很方便地维护了。

这道题其实比较水，如果放在T1的话可能我就能AC了。我几乎已经想出了正解，但在实现的时候还是写成了DFS，着实是非常可惜。

首先，枚举第一次选左还是右，然后你就可以决定最后选的位置（这个大家都能想出来）。

然后暴力选择，优先选左，就可以写出高达 $28pts$ 的dfs。

我们考虑一下如何将这个转为正解。我们发现若某一次选择时，我们同时可以选左和右，我们的时间复杂度就会乘 $2$ 。但我们发现，我们根本不需要重新走右。

证明：

如果左右都能选，那么在我们选了做之后，选右的机会就会出现在我们的下一次选择，意思说如果我们不选右，选右的方案会一直存在。因此，不管我们这一步选左还是选右，我们总的选择方案是完全相同的，一旦选左不行，选右的结果也一样。

利用这个性质，我们的dfs瞬间变成了 $O(n)$ 的贪心，就可以愉快的通过本题了。

这道题个人认为完全是省选难度，甚至不能放在第一题。周围的巨佬以及本蒟蒻没有一个人会，也就不太关注。现在听到的感觉最科学的方法是网络流转对偶图然后最短路。

据说上午的普及组四道大模拟很简单，以为下午也会比较水。然后一看T1心态就崩了，T3也是失手犯错导致没AC，T2的暴力写到最后十分钟也没写对，总体来说发挥的不好。估计最多也就勉强一等分数线。