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待会再补吧