Shiroha白羽的博客
·
Codeforces Round 890 (Div. 2)
💡
原文中文，约4400字，阅读约需11分钟。
📝
内容提要
A. 给定一个序列，每个操作可以将所有值减1，除非它已经为0。目标是找到使序列非递减所需的最小操作次数。 B. 给定一个数组，确定是否存在另一个数组，使得元素之和相等且每个元素都不同。 C. 给定一个初始数组，每个操作可以增加一个值，如果它小于或等于下一个值。目标是在最多k次操作后找到数组的最大值。 D. 给定n个元素的排列，目标是以5 * n^2的代价找到最大值的索引。 E1. PermuTree（简化版本）：给定一棵树和n个元素的排列，找到满足方程a_u < a_lca(u, v) < a_v的最大次数。
🎯
关键要点
-
给定一个序列，通过减少值来使其变为非递减序列，需找到最小操作次数。
-
判断是否存在另一个数组，使得两个数组的元素和相等且每个元素不同。
-
在最多k次操作下，找到初始数组的最大值，操作为增加小于或等于下一个值的元素。
-
通过询问逆序对数量，找到排列的最大值索引，代价为5 * n^2。
-
在树上找到满足特定条件的排列次数，需进行子节点的合理划分。
➡️
