【题解】CodeForces-1905

发布时间 2023-12-19 10:17:31作者: SoyTony

Page Views Count

CodeForces-1905A Constructive Problems

发现沿着对角线放就行了,答案是 \(\max(n+m)\)

提交记录:Submission - CodeForces

CodeForces-1905B Begginer's Zelda

最优操作每次删两个叶子(除了最后一次只剩两个节点),所以答案是叶子个数除以二上取整。

提交记录:Submission - CodeForces

CodeForces-1905C Largest Subsequence

发现移动一次之后字典序最大的子序列在某种意义上不变,只是结尾减少一个字符,每次移动之后对应的最后一个元素就在序列末尾,那么就会移动直到只剩下相同的前缀,所以模拟并判断是否合法即可。

提交记录:Submission - CodeForces

CodeForces-1905D Cyclic MEX

发现一个前缀 \([1,i]\)\(\mathrm{mex}\) 就是 \(\min_{j=i+1}^n \{p_j\}\),于是环的情况把序列复制一边,之后就是对每个位置 \(i\) 求以 \(i\) 为右端点的所有长度 \(<n\) 区间的最小值之和。再仔细考虑发现长度 \(\ge n\) 的一定有 \(0\) 了,那么对答案没影响,直接求以 \(i\) 为右端点的所有区间最小值之和就行了,单调栈解决问题。

提交记录:Submission - CodeForces

CodeForces-1905E One-X

可以归纳证明,规模一定的线段树每一层的区间大小最多只有两种,那么而算答案形如左右区间各取非空子集的方案数乘积,所以关键是对每种区间长度算一下个数和编号和,拿个堆维护就做完了。

提交记录:Submission - CodeForces

CodeForces-1905F Field Should Not Be Empty

提交记录:Submission - CodeForces