Atcoder Beginner Contest 281

D. Max Multiple (DP)

题意

在长度为 \(N\) 的序列 \(A\) 中，找到 \(K\) 个元素其和为 \(D\) 的倍数，找出满足要求最大的和，没有则返回 -1。

数据范围

\(1\leq K \leq N \leq 100\)
\(1\leq D \leq 100\)
\(0\leq a_i \leq 10^9\)

思路

• 观察数据范围 ，\(N,D,K\) 都是 100 以内，再尝试贪心选前 \(K\) 大来手摸一下，发现就是个经典的 DP 。
• 容易设计出状态 \(dp_{i,j,k}\) 表示前 \(i\) 个选 \(j\) 个元素和的模数为 \(k\) 的最大和，答案为 \(dp_{N,K,0}\) 。
  • PS: 模数为 \(k\) 的这一维状态，灵感其实来源于一些数位 dp 的题目，但其实也算很常见的住哪个台设计了。
• 转移：\(dp_{i,j,k} = \max(dp_{i-1,j,k}, dp_{i-1,j-1,(k-a_i)%D})\) ，当然 % D 以后要转成正数。
• 时间复杂度 \(O(N*K*D)\)

Solution

评测记录

E. Least Elements (STL(multiset)、维护增量)

题意

给了长度为 \(N\) 的数列 \(A\) ，和整数 \(M,K\) 。

需要求出每个长度为 \(M\) 的连续子段中，前 \(K\) 小的元素和。

数据范围

\(1\leq K \leq M \leq N \leq 2\times 10^5\)
\(1\leq a_i \leq 10^9\)

思路

• 从 \(K=M\) 开始考虑（其实是我最开始读错了以为就是个优先队列裸题） 。
  • 这种情况下，就是个优先队列裸题，考虑维护增量的方式，一个优先队列就搞定了。
• 如果 \(K<M\) 呢？
  • 实际上依然考虑维护增量，每次移动的时候，在子段中将插入的元素为 \(x\)，要被删除的元素为 \(y\) 。
  • 因为我们只关心前 \(K\) 小个元素的数值，因此简单分类讨论一下，考虑先做删除后做插入。
  • 删除 \(y\) 。
  • \(y\) 不在前 \(K\) 小中，不做操作。
  • \(y\) 在前 \(K\) 小中，和应该减去 \(y\) ，并且调整第 \(k\) 小的元素为比它大的一个元素。
  • \(x\) 不在前 \(K\) 小中，不做操作。
  • \(x\) 在前 \(K\) 小中，第 \(K\) 小应该向更小的方向移动一次。
  • 将 \(x\) 插入。
• 大概流程入上，思路出来就可以借用 STL 了。使用 multiset<pair<int,int>> 维护 {a[i], i} 即可。
• 实现会有一些小细节但是不多，根据实现方式，我为了方便将 \(K=M\) 的 case 直接特判掉了，防止 RE。
• 时间复杂度 \(O(N*logN)\)

Solution

评测记录

F. Xor Minimization (Trie 上分治 or DP)

原题：CF1285D

评测记录