Shiroha白羽的博客
·
CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!)
💡
原文中文，约4200字，阅读约需10分钟。
📝
内容提要
给定一个数组，判断是否可以通过交换相邻的值来排序，前后的值都小于左右的值。使用插入排序来检查第一个值是否正确。给定一个AB数组，翻转AB子字符串。每个索引只能翻转一次。通过计算连续的AB子字符串的数量，找到最大翻转次数。给定两个AB数组，对数组B进行排序，并检查是否存在一个排列，其中ai > bi的数量恰好为x。对两个数组进行排序，并将B的前x个值移动到末尾。给定一个由1和2组成的数组，执行操作将值更改为1或2。检查是否存在一个子字符串的和等于x。维护总和和值为1的索引的集合。给定一个排列数组，执行操作将数组排序。每个操作将一个值移动到其正确的位置。计算每个索引需要的操作次数。使用线段树来跟踪可以跳过的区间。
🎯
关键要点
- 允许选择一个值，其左右两边都是大于当前值的情况下，将当前值和后面的那个值交换，判断是否可以排序。
- 使用插入排序的方式，只需确保第一个值是正确的。
- 对于由AB组成的数组，翻转AB子字符串，每个下标只能翻转一次，计算最大翻转次数。
- 通过找出连续的AB对的数量来确定可翻转的次数。
- 对于两个AB数组，排序后判断是否存在一个排列，使得ai > bi的数量恰好为x。
- 将B数组的前x个值移动到末尾以满足条件。
- 对于仅由1和2组成的数组，检查是否存在子串的和等于x。
- 维护总和及值为1的索引集合以解决问题。
- 对于排列数组，计算每个索引需要的操作次数以完成排序。
- 使用线段树来跟踪可以跳过的区间以优化操作次数。
➡️
