CSP-S 2021 题解

我的 CSP-S 2021 游记

T1 廊桥分配(airport)

这次 T1 带有很大的迷惑性。

其实吧本身这个 T1 不难,以国内区为例子,我们设 s u s_{u} su​ 表示当分配给国内区 u u u 个廊桥的时候国内区有几架飞机能够停靠,不难发现如果规定 s u s_{u} su​ 表示有几架飞机刚好停在第 u u u 个廊桥,就可以直接单点修改然后做一遍前缀和。

由于飞机停靠遵循先来后到原则,因此实际上求出 s u s_{u} su​ 数组是可以用两个优先队列解决的,复杂度 O ( n log ⁡ n ) O(n \log n) O(nlogn)。

对国内区和国际区分别做一次,得到 s 1 , s 2 s1,s2 s1,s2 两个数组之后,答案就是 max ⁡ i = 0 n ( s 1 i + s 2 n − i ) \max_{i=0}^{n}(s1_i+s2_{n-i}) maxi=0n​(s1i​+s2n−i​)。

这个做法倒是挺简单的,就是一个贪心思路,但问题是考场上给的两个小样例很具有迷惑性,让人以为如果设 f ( x ) = s 1 x + s 2 n − x f(x)=s1_x+s2_{n-x} f(x)=s1x​+s2n−x​,这个 f ( x ) f(x) f(x) 是满足单峰性的,然后很多人就写了个三分于是愉快的挂掉了()

实际上考场上的大样例输出来看一眼就知道 f ( x ) f(x) f(x) 并不满足单峰性,然后就知道三分是假的了。

当然那个大样例的图画出来大概是这样的:

CSP-S 2021 题解

也就是说实际上大样例面对部分三分是能过的,还是相对比较水,当然至少有些人的三分被卡了。

Code:Github CodeBase-of-Plozia CSP-S 2021 airport.cpp

T2 括号序列(bracket)

先咕着。

T3 回文(palin)

先咕着。

T4 交通规划(traffic)

先咕着。

上一篇:CSP-J 2021 题解


下一篇:CSP-S 2021 题解