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的索引的集合。给定一个排列数组,执行操作将数组排序。每个操作将一个值移动到其正确的位置。计算每个索引需要的操作次数。使用线段树来跟踪可以跳过的区间。

🔎

延伸解读

题目A的交换条件与排序判断

题目A允许在左右两边都大于当前值的情况下,将当前值与后一个值交换。文章指出,这类似于插入排序,只需检查第一个元素是否为1即可判断能否排序。因为如果第一个元素是1,后续元素可以通过交换逐步归位;否则无法将最小值移到首位。这一结论简化了问题,避免了模拟交换过程。

题目B中连续AB对的最大翻转次数

对于仅由A和B组成的字符串,每次可以翻转一个AB子串,且每个下标只能翻转一次。文章分析,对于连续的AAA...BBB形式,除了最后一个B,其他位置都能参与翻转。因此,最大翻转次数等于所有连续AB对的数量减一(如果存在)。对于多个连续组,整体上除了最后一个B,其他也都能翻转,所以只需统计连续对总数并减一。

题目C的匹配策略与排序调整

给定两个数组A和B,可以任意排序B,问是否存在排列使得a_i > b_i的数量恰好为x。文章提出,将两个数组排序后,将B的前x个元素移到末尾,然后检查满足a_i > b_i的位置数是否等于x。如果等于,则输出YES并构造排列;否则输出NO。这种方法通过排序和循环移位,有效地控制了满足条件的数量。

题目D的子串和查询与奇偶性处理

数组仅由1和2组成,需要回答是否存在子串和等于x。文章指出,由于元素为1或2,总和s可以减去2的倍数得到s-2, s-4,...直到0或1。因此,若x与s奇偶性相同且x≤s,则一定存在。若奇偶性不同,则需要减去一个1,此时找到左右两边最近的1,减去该侧的所有2和这个1,得到最大可满足的奇偶性不同的和,再判断x是否不超过该值。

❓

Q&A

CodeTON Round 7 的 A 题 Jagged Swaps 中,判断数组能否排序的条件是什么?

只需要检查数组的第一个元素是否等于 1。如果第一个元素是 1,则输出 YES,否则输出 NO。

在 B 题 AB Flipping 中,如何计算最多可以翻转的次数?

找出所有连续的 AB 对的数量,然后答案就是该数量减一(如果数量大于 0)。具体实现时,可以从右向左遍历,统计每个 A 后面连续的 B 的数量,累加后减一。

C 题 Matching Arrays 中,如何构造一个排列使得 a_i > b_i 的数量恰好为 x?

将两个数组分别排序,然后将 B 数组的前 x 个元素移动到末尾(即循环移位 x 位),再检查是否恰好有 x 个位置满足 a_i > b_i。如果满足,则输出 YES 并给出构造的 B 数组。

D 题 Ones and Twos 中,如何快速回答是否存在子串和等于 x 的询问?

维护数组的总和 sum 以及所有值为 1 的索引集合。如果 x > sum,则不存在;如果 x 和 sum 奇偶性相同,则存在;否则,需要减去一个 1 来改变奇偶性,此时找到最左或最右的 1,计算减去该侧所有 2 和该 1 后的最大可能和,若 x 不超过该值则存在。

E 题 Permutation Sorting 中,如何计算每个下标完成排序所需的操作次数?

每个值的移动成本等于其当前位置与目标位置的差值,但如果有其他值提前到达目标位置,则可以减少移动次数。使用线段树维护区间,对于每个值,其移动区间为 [l, r],则所有结束位置大于 r 的区间会减少一次成本。通过从左到右访问并动态更新线段树来计算每个值的实际操作次数。

CodeTON Round 7 的题目涉及哪些主要算法或数据结构?

涉及插入排序思想、连续子串计数、排序与循环移位、集合维护、线段树等。

🏷️

标签

➡️

继续阅读