AtCoder Beginner Contest 440 题解
AtCoder Beginner Contest 440目录
[*]AtCoder Beginner Contest 440
[*]
[*]A. Octave
[*]B. Trifecta
[*]C. Striped Horse
[*]解题思路
[*]1. 周期简化
[*]2. 转化为滑动窗口
[*]D. Forbidden List 2
[*]E. Cookies
[*]F待会再补吧
如果题解中有什么问题可以找我反馈，谢谢！
打了一坨，ABD打完迅速把所有题都做了结果弘文了
A. Octave
直接输出 \(x * pow(2, y)\)。
B. Trifecta
排序即可。
C. Striped Horse
多算了条件，2W > n是可能的结果WA了
涂色规则的周期性!!
解题思路
1. 周期简化
由于 N 可能很大，但涂色规则是按 2W 取模的，意味着方块 i 和方块 i+2W 的涂色情况永远相同。
我们可以把所有方块按 (i(mod2W)) 分类，将落在同一个余数位置的方块成本 Ci 累加。
[*]设 as 为所有满足 i ≡ r(mod 2W) 的方块的成本之和。
[*]数组 as 的长度仅为 2W。
2. 转化为滑动窗口
题目要求找一个 x 使得总成本最小。在取模 2W 的意义下，这等价于在长度为 2W 的环形数组 as 中，找到连续的 W 个位置，使它们的和最小。
在处理环时，最好是复制两边。
[*]预处理：创建一个大小为 2W 的数组 as，遍历所有方块 i∈，执行 as += C。
[*]倍增：将 as 复制一份拼接在末尾，得到长度为 4W 的数组 d2。
[*]求和：
[*]先计算 d2 中前 W 个元素的和作为初始 ans。
[*]使用滑动窗口：每次右移一位，加上新进入窗口的元素，减去离开窗口的元素。
[*]在滑动过程中不断更新 ans。
[*]输出：最终的 ans 即为答案。
简单题解结束
D. Forbidden List 2
观察，发现值大，不可做。
二分即可
我们设定二分的左边界 \(L\)，右边界\(R\) 为一个足够大的数，如。
对于二分的中点\(mid\)，我们需要计算区间 \(\) 中有多少个有效数字（即不在 中的数）。
check：upper_bound(a.begin(), a.end(), mid) - lower_bound(a.begin(), a.end(), x);
why?
假设我们有一个有序向量 a：
[*]lower_bound(begin, end, x)：
返回指向第一个大于或等于 \(x\) 的元素的迭代器。
[*]upper_bound(begin, end, mid)：
返回指向第一个大于 \(mid\) 的元素的迭代器。
[*]Ad-Hoc一下
开E
E. Cookies
贪心贪贪贪
Ad-Hoc:最大和 \(S1=K×max(A_i)\)。后续解通过将最大值替换为较小值产生，利用优先队列维护最小“损失值”来有序搜索前 \(X\) 大和。
[*]预处理：将 \(A_i\) 降序排列，计算 \(D_i=A_1−A_i+1\) (替换一个的损失)。
[*]状态设计：堆中存 {loss, id, cnt}。
[*]加数量：{loss + D, id, cnt + 1} (当前种多换一个)。
[*]换种类：{loss - D + D, id+1, cnt} (将当前一个换成更小的)。
[*]去重：通过限定 id 递增及特定的转移顺序，确保每种多重集组合只被压入堆一次。
复杂度：\(O(N \log N+X \log X)\)。
可以过。
F待会再补吧
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 不错，里面软件多更新就更好了 感谢分享，学习下。 谢谢分享，辛苦了 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 收藏一下 不知道什么时候能用到 东西不错很实用谢谢分享 这个好，看起来很实用 热心回复！ 谢谢楼主提供！ 不错，里面软件多更新就更好了 yyds。多谢分享 谢谢楼主提供！ 感谢分享，下载保存了，貌似很强大 很好很强大我过来先占个楼 待编辑 不错，里面软件多更新就更好了 感谢分享 过来提前占个楼 感谢分享，学习下。 不错，里面软件多更新就更好了
页:
[1]