Shiroha白羽的博客
·
CodeTON Round 6 (Div. 2)
💡
原文中文，约3800字，阅读约需9分钟。
📝
内容提要
本文讨论了多个编程题目，包括构造数组以达到特定的MEX值、通过位运算优化数组的异或和、在矩阵中找到特定值的最小矩形，以及在预算限制下最大化字典序的数组。每个题目都提供了解题思路和代码实现。
🎯
关键要点
- 题目A要求构造一个长度为n，最大值为x，MEX为k的数组，若k > x + 1或n < k则无解，其他情况下可以构造满足条件的数组。
- 题目B给出两个数组a和b，通过位运算求得数组a的异或和的最大值和最小值，关键在于a的长度的奇偶性。
- 题目C涉及一个数组和一个矩阵，要求找到每个数字在矩阵中出现的最小矩形，需根据数字在数组中的首次和末次出现位置进行计算。
- 题目D要求在预算限制下，最大化一个初始为0的数组的字典序，通过贪心策略和单调递增栈处理来实现。
❓
延伸问答
如何构造一个特定MEX值的数组？
构造一个长度为n，最大值为x，MEX为k的数组时，若k > x + 1或n < k则无解，其他情况下可以构造满足条件的数组。
如何通过位运算优化数组的异或和？
给定两个数组a和b，异或和的最大值和最小值取决于a的长度的奇偶性，奇数时选择尽可能多的b，偶数时尽可能少选。
如何在矩阵中找到特定值的最小矩形？
对于每个数字x，找到其在数组中的首次和末次出现位置，然后根据这些位置计算出包含所有出现x的最小矩形。
在预算限制下如何最大化数组的字典序？
通过贪心策略和单调递增栈处理，尽可能将预算分配给前面的元素，以最大化字典序。
构造数组时MEX值的条件是什么？
MEX值的条件是k必须小于等于x + 1且n必须大于等于k，否则无法构造满足条件的数组。
如何处理数组的异或和以获得最大值？
处理时需关注数组长度的奇偶性，奇数时尽量选择更多的b元素，偶数时则尽量不选择，以获得最大异或和。
➡️
