Codeforces Round 915 (Div. 2) 题解
A.Constructive Problems
直接找规律,或者手玩一下发现按照对角线斜着放最优(不会证),答案即为 \(max(n, m)\) 。
B.Begginer's Zelda
每次我们选择的端点一定是叶子结点,最优性是显然的。因为每次可以删掉两个叶子,设叶子数为 \(p\),答案即为 $ \left\lceil \dfrac{p}{2} \right\rceil $。
C.Largest Subsequence
发现我们选中的字典序最大的子序列内的元素不会变,只会按照题目要求循环移动。(如果会变,那么它在最开始就应该被选入子序列中。)
显然,这个子序列的字典序是单调不升的,想要排好序,就要把除了最大的字母以外的其他字母全部移到前面去,设子序列长度为 \(len\),最大的字母出现了 \(k\) 次,答案即为 \(len - k\)。
但是,不在子序列里的字母也会影响是否能成功排序,所以最后可以暴力 check 一下移动后是否排好序,没排好就说明无解。
D.Cyclic MEX
参考 HDU-4747,很像。
几乎完全一致的做法。把原本顺序的 mex 都求出来,考虑把第一个数放到最后面产生什么影响。
因为是一个环状的东西,考虑复制一遍拼在后面,方便处理。
假设当前这个数是第 \(i\) 个数,它被放到 \(i + n\) 的位置上。那么 \(i + n\) 位置上的 mex 显然和原本第 \(n\) 个位置上的 mex 相等,单点修改即可。
而删掉第 \(i\) 个数,产生的影响就是在区间 \([i + 1, i + n - 1]\) 内,mex 大于 \(a_i\) 的位置全部变成 \(a_i\),由于 mex 的前缀单调性,我们可以直接线段树二分找出要操作的区间,区间赋值即可。
对于每次的答案,询问 \([i, i + n - 1]\) 的 mex 之和,取个最小值即可。
综上,我们需要一个支持区间查和、最大值,区间复制的线段树,直接维护即可。
以上为场切。
评价:写题太慢还一直挂,多练。