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[r] 为所有满足 i ≡ r(mod 2W) 的方块的成本之和。
  
• 数组 as 的长度仅为 2W。
  

2. 转化为滑动窗口

题目要求找一个 x 使得总成本最小。在取模 2W 的意义下，这等价于在长度为 2W 的环形数组 as 中，找到连续的 W 个位置，使它们的和最小。

在处理环时，最好是复制两边。

• 预处理：创建一个大小为 2W 的数组 as，遍历所有方块 i∈[1,N]，执行 as[i % (2W)] += C。
  
• 倍增：将 as 复制一份拼接在末尾，得到长度为 4W 的数组 d2。
  
• 求和：
  
  
  
  • 先计算 d2 中前 W 个元素的和作为初始 ans。
    
  • 使用滑动窗口：每次右移一位，加上新进入窗口的元素，减去离开窗口的元素。
    
  • 在滑动过程中不断更新 ans。
    
  
  
• 输出：最终的 ans 即为答案。
  

简单题解结束
D. Forbidden List 2

观察，发现值大，不可做。
二分即可
我们设定二分的左边界 \(L\)，右边界\(R\)  为一个足够大的数，如。
对于二分的中点\(mid\)，我们需要计算区间 \([X, 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], id, cnt + 1} (当前种多换一个)。
    
  • 换种类：{loss - D[id] + D[id+1], id+1, cnt} (将当前一个换成更小的)。
    
  
  
• 去重：通过限定 id 递增及特定的转移顺序，确保每种多重集组合只被压入堆一次。
  

复杂度：\(O(N \log N+X \log X)\)。
可以过。
F待会再补吧


来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！