Shiroha白羽的博客
·
Codeforces Round 897 (Div. 2)
💡
原文中文，约3000字，阅读约需8分钟。
📝
内容提要
A. 给定一个长度为n，最大值为x，MEX为k的数组，求所有值的和的最大值。B. 给定两个数组a和b，允许选择任意次的b数组中的任意一个bj，然后让a[i]=a[i]|bj，求最终得到的数组a中所有的异或和最大和最小的可能。C. 给定一个长度为n的数组a和一个n×n的矩阵b，b[i][j]=min(a[i],a[j])。对于每个数字x，求在矩阵b中能够找到对应一个最小的矩形，此矩形包含了所有出现x的位置，求出这个矩形的大小。D. 给定一个初始数组，每一个值都是0，每次可以选择花费ci元，使得前i个元素加一，最多只能花费k元，求能够得到最大字典序的数组。
🎯
关键要点
- 构造一个长度为n，最大值为x，MEX为k的数组，求所有值的和的最大值。
- 在k > x + 1或n < k的情况下无解，其他情况下构造数组并计算和。
- 给定两个数组a和b，允许选择b中的任意一个元素，使得a[i] = a[i] | b[j]，求最终数组a的异或和的最大和最小值。
- 通过分析比特位的奇偶性来决定选择b的策略，以达到最大和最小的异或和。
- 给定一个长度为n的数组a和一个n×n的矩阵b，b[i][j]=min(a[i],a[j])，求每个数字x在矩阵b中对应的最小矩形的大小。
- 通过记录每个值在数组a中第一次和最后一次出现的位置，计算矩形的大小。
- 给定一个初始数组，每个值为0，花费ci元使得前i个元素加一，最多花费k元，求最大字典序的数组。
- 通过单调递增栈处理c的值，贪心选择前面的值尽可能大，以达到最大字典序。
➡️
