CF Round 997 记录 题解 （div. 2 A - E）
今天（P.S. 其实是很久以前）上午VP CodeForces Round 997 (Div. 2)。
-
[CodeForces 2056A] Shape Perimeter
计算重叠部分即可。
-
[CodeForces 2056B] Find the Permutation
我们总是建从小节点到大节点的有向边，对这个DAG进行拓扑排序。因为我们有时并不想让一个小节点往大节点连边，所以用堆维护入度为零的点即可。（可恶，赛时多测不清空卡了我一发。）
-
[CodeForces 2056C] Palindromic Subsequences
挺玄学的构造题。我们希望大概长这样的结构：
1 , 1 , 1 , … , 1 , ⏟ a 个 1 2 , 3 , 4 , … , a + 3 , 1 , 1 , 1 , … , 1 ⏟ a − 1 个 1 \underbrace{1,\ 1,\ 1,\ \dots,\ 1,}_{a个1}\ 2,\ 3,\ 4,\ \dots, a + 3,\ \underbrace{1,\ 1,\ 1,\ \dots,\ 1}_{a-1个1} a个1 1, 1, 1, …, 1, 2, 3, 4, …,a+3, a−1个1 1, 1, 1, …, 1
这样构造出的答案有 a ( a + 2 ) + 1 = a 2 a(a + 2) + 1 = a^2 a(a+2)+1=a2 个，可以通过。稍微分讨一下即可。
赛后看了一下题解，发现自己好唐：
1 , 2 , 3 , … , n − 2 , 1 , 2 1,\ 2,\ 3,\ \dots,\ n-2, \ 1,\ 2 1, 2, 3, …, n−2, 1, 2
-
[CodeForces 2056D] Unique Median
又是一道正难则反，计算坏的序列的个数。这道题的trick挺巧妙的，但没接触过，确实想不出来。发现长度为奇数的序列一定不是坏的，所以只考虑偶数长度序列。对于一个序列的中位数 x x x，将序列中 ≤ x \le x ≤x 的数化为 − 1 -1 −1，其它的化为 1 1 1。若最终区间和为 0 0 0，那么这个序列就是坏的。另外要注意去重。维护前缀和即可。
-
[CodeForces 2056E] Nested Segments
组合数学。这个包含或不交的关系恰好和昨天的B差不多。我们想要尽可能多的节点数量，那么需要构造成二叉树。（这里具体不想证明。）对于某一个节点，设其儿子数量为 c n t u cnt_u cntu，则计算 ∏ C c n t u − 1 \prod C_{cnt_u - 1} ∏Ccntu−1（卡特兰数）即可。