159F
ARC159F
传送门 solution 神仙 dp 题。 下文认为 \(n\) 是题目中给定 \(n\) 的两倍。 先考虑一个给定的序列是否能被消除的条件。 猜测一下应该是 序列长度是偶数 不存在一个数,在序列中出现超过 \(\lfloor\dfrac{n}{2}\rfloor\) 次,其中 \(n\) 是序列长 ......
[ARC159F] Good Division 题解
[ARC159F] Good Division 题解 首先对于题目要求的划分方式转化一下,转化为划分的每一段都没有 绝对众数,可以证明这与题目中的要求是完全等价的,证明如下: 充分性:考虑构造一种操作方法,就是每次操作都消去一个出现次数最多的数,按照这样操作可以保证每次操作之后该区间仍然不会出现绝对 ......
ABC159F Knapsack for All Segments
原题 翻译 \(O(n^3)\) 的朴素 \(dp\) 是 simple 的 考虑定义一个子序列是”好的子序列”当且仅当 \(a_l\) 和 \(a_r\) 都在子序列中,容易发现他对答案的贡献是包含他的区间,即 \(l \times (n - r + 1)\) 先说我自己的做法:设 \(dp_{i ......