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) 并不满足单峰性,然后就知道三分是假的了。
当然那个大样例的图画出来大概是这样的:
也就是说实际上大样例面对部分三分是能过的,还是相对比较水,当然至少有些人的三分被卡了。
Code:Github CodeBase-of-Plozia CSP-S 2021 airport.cpp
T2 括号序列(bracket)
先咕着。
T3 回文(palin)
先咕着。
T4 交通规划(traffic)
先咕着。