2023 syzx 秋季训练 2

发布时间 2023-09-22 20:22:48作者: gzyqwq

A

\(a_i\) 非递减,说明二进制最高位也是非递减的,如果有3个最高位相等,答案为 1,否则 \(n \leq 100\),则可以 \(O(n^3)\) 枚举。

B

先假设所有的 \(c_i\) 都是正数,那肯定是按 \(a_i\) 降序来做。

但是有些是负数,但是可以归零 k 次。

假设有正有负,肯定是先把正数全部先加起来,否则负数按绝对值排序,绝对值小的优先加到序列里面。

最后会得到 n' 个负数,考虑到每个操作最后一次操作不会有贡献,相当于变成 n' 个负数,分成 k+1 组。

组内按绝对值升序排序。

使得每个组个数尽量平均,权值平均也能过。

C

转化问题:

\(c_0 + c_1 = l\)

\(c_0 - c_1 = k\)

l 的取值只有五种

考虑每个 l 都做一次即可。

D

考虑三种转移:

\(dp_i = max(dp_j) + len_i\)

\(dp_i = max(dp_j - r_j) + r_j\)

\(dp_i = max(f_j) + r_j\)

线段树维护即可

也可以考虑 set 维护一个上升序列,类似二分求上升子序列的思想。

E

式子有点别扭,不妨先把绝对值拆掉。

每个 \((i, j)\) 被多少个格子影响了,那我们可以到每个格子时再决定是否反转。

设计一个叫 \(l_{i, j}\) 表示左上角对此格子的影响。

\(r_{i, j}\) 表示右上角,\(c_{i, j}\) 表示正上方。

\(l_{i, j}\) 可以从 \(l_{i-1, j-1}\) 转移过来,其他同理,那么可以 \(O(1)\) 转移。

也可以考虑直接打反转标记,延迟下放。