CSP-S 2021

P7913 廊桥分配

并查集+贪心

将两组数据按进入机场的时间排序，每次选最小且没有访问过的航班，并且通过lower_bound求出整个一条链，将他们都打上标记。之后将所有链上的点并在一起。

复杂度\(\Theta (nlogn+k),k=1-n^2\),k是将已经搜过的点跳过的搜索次数，~~事实证明CCF的数据是真的水~~

~~这不是说明我rp好吗~~

P7915 回文

1.40pts (暴力)dfs+剪枝

剪枝是指在搜到n+1~2n个数时，与前面的序列判断是否回文，不合法直接回溯；并且因为时按照先左后右的顺序搜索，所以第一次搜到的一定是左右皆，后面的都不用搜，程序直接结束。

对于n<=20完全ok

对于n<=100看rp

~~CCF数据太垃圾，20min水过40pts~~

~~这不是说明我rp挺好吗 :)~~

2.100pts 我们发现对于每个中间形态，即子序列，它能拓展的点只有序列左边和右边一个，因此有4个指针，为序列左右的待取指针和子序列的左右指针。此时左边不行取右边，右边不行取左边，都不行-1，都行就取左边。 注意判断指针是否重合。