ARC#135 题解
ARC135D
题意
给定一个 的矩阵, 每个位置上有一个整数
我们称一次操作为选择 , 令 的值均增加 .
你可以执行有限次操作, 求 的最小值.
题解
我们设 ,
显然, 任意一次操作不会改变 的值或 的值. 又 , 所以答案的最小值不小于 , 接下来我们构造一组能使答案到达该界的解.
我们转换问题, 给定 , 求一个 满足 , 最小化 .
我们考虑到一个 的影响. 显然会影响 和 . 问题转变为给定 , 一次操作是选择 并消耗 , 令 . 求最小代价使 均变为 .
我们考虑如下构造:
- 如果存在 , 做操作 .
- 如果存在 , 做操作 .
- 如果存在 , 做操作 .
- 如果存在 , 做操作 .
容易说明这样构造的是合法且最小的解.
ARC135E
题意
给定 . 我们称一个长度为 的序列 合法当且仅当以下条件满足:
解法
设 . 重写限制为 .
容易发现
Lemma 1
.
考察没有 的限制的话 会是多少. 显然 , . 考察 对 的影响, 显然每个数最多使 增加 1, 所以 .
由 Lemma 1 显然可以得到一个 的做法.
Lemma 2
的不同取值个数是 的.
不妨令 , . 首先 的取值个数是 的. 其次, 显然有 , 所以 . 又因为 是单调不升的, 所以 也是单调不升的, 也即 的取值个数也是 的.
所求的一段 相同的 可以由这段 和起始/结束位置计算得到.
ARC135F
题意
给定 . 一长度为 之序列 满足 . 对于一序列 , 我们称一次操作为对于所有 之位置 , 将 从序列 中删去. 现对 连续施 次操作, 问剩下的所有数之和.
.
解法
考察一序列 操作后得到的 序列有什么特点. 可以发现 . 令 .
于是一系列操作后所求之和即: , 其中 为最后剩下数之个数. 此做法之时间复杂度为 .
考察到 , 可以根据 分组得到一个 的做法.
考察折半. 不妨假设 为偶数, . 仿照前例, 考察 . 根据 分组, 也即要对每个 求
考察 预处理所有形如 形式的和式, 这样的和式之数量是 的.
综合这两个算法, 时间复杂度是 的