专栏文章

题解：AT_arc207_c [ARC207C] Combine to Make Non-decreasing

ZZnPdCo
AT_arc207_c题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@minnvn39
此快照首次捕获于
2025/12/02 05:28
3 个月前
此快照最后确认于
2025/12/02 05:28
3 个月前
查看原文
来点简单好写做法。
考虑维护 gig_i 表示 1∼i1\sim i 的最多段数，fif_i 表示在将 1∼i1\sim i 划分为最多段的情况下，最后一段最小能是多少。
从小到大扫描 ii，设 tjt_{j} 表示 ajor⁡aj+1or⁡⋯or⁡aia_j\operatorname{or}a_{j+1}\operatorname{or}\cdots\operatorname{or} a_i 的值。这个可以每次将 jj 从大到小枚举暴力更新直到 tjt_j 的值不变，那么此时比 jj 更前的 tjt_j 显然也不会变了，因为一个数最多只能被更新 log⁡A\log A 次，所以均摊下来暴力的复杂度是正确的。
我们现在要划分一个段 [x,i][x,i]，转移就是 fi←tx,gi←gx−1+1f_i\gets t_x,g_i\gets g_{x-1}+1。考虑贪心找到这个 xx，显然是选择一个最大的转移点 xx 满足 fx−1≤txf_{x-1}\le t_x 是最优的，因为 gxg_x 具有单调性，xx 越大，gg 越大，同时 txt_x 越小，所以贪心是对的。
xx 可以在每次更新 tjt_j 时去更新，所以复杂度也是对的。
综上，复杂度 O(nlog⁡A)O(n\log A)。
CPP
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 200010;
int n, a[N], f[N], g[N], t[N];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int x = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j >= 1; j--) {
            if ((t[j] | a[i]) == t[j]) break;
            t[j] |= a[i];
            if (f[j - 1] <= t[j]) x = max(x, j);
        }
        f[i] = t[x];
        g[i] = g[x - 1] + 1;
    }
    cout << g[n] << endl;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...