【CF 1798E】Multitest Generator

题目描述

定义一个序列为 test 仅当序列的第一个元素为这个序列剩下元素的长度。

定义一个序列为 multitest 仅当该序列的第一个数为能够将剩下元素组成的序列拆成的 test 的个数。

定义一次修改操作可以将序列中任意元素修改为任意一个非负整数。

定义函数 $f(A)$ 为将序列修改为 multitest 的最少操作次数。

给定一个长度为 $n$ 的序列 ${a_n}$，输出 $f([a_i, a_{i+1},\dots ,a_n])$ 当 $i\in [1,n-1]$ 的值。

$2\le n\le 300000$，$1\le a_i\le 300000$。

算法分析

一开始想错了，还以为是特别水那种 DP。

构造一种方案：将第一个元素修改为 $1$，第二个元素修改为 $n-2$，因此对于任意序列，最少操作次数不会超过 $2$。

分类讨论：

什么情况下 $f(A)$ 的值为 $0$：定义 $f[i][0]$ 为以下标 $i$ 起始的后缀不进行任何修改操作将序列分成的块数，若不能拆分为若干个 test 则值为 $0$，转移很好设计。$f[i+1][0]=a_i$ 时 $f([a_i,a_{i+1},\dots , a_n])$ 的值为 $0$。什么情况下 $f(A)$ 的值为 $1$：唯一一次修改会发生在两种位置。

第一种是在 multitest 的开始，即 $f[i+1][0]\neq a_i$ 时 $f([a_i,a_{i+1},\dots , a_n])$ 的值为 $1$。

第二种是在 multitest 中某个 test 的开头，这时定义 $f[i][1]$ 为以下标 $i$ 起始的后缀进行一次修改操作将序列分成的「最大」块数。为什么取最大呢？考虑转移时，要么修改过从 $f[i+a_i+1][1]$ 转移，要么没有修改过从 $f[j][0]$ 转移，这里的 $j$ 可以是 $[i+1,n]$ 中的任何值（对应将该数修改为 $[0,n-i-1]$，其实也可以修改为 $n-i$，这种情况用分成的 $1$ 块来更新 $f[i][1]$）。如果可以将序列分成 $b$ 块，则它一定能够分成 $a(a\le b)$ 块，因为我们可以考虑改变这一次修改的位置和值，从而将序列尾部的多个块合并。所以，在 $f[i+1][1]\ge a_i$ 时 $f([a_i,a_{i+1},\dots , a_n])$ 的值为 $1$。

（可能会感到疑惑，按照上面这种转移会不会包含把 $a_i$ 修改为 $a_i$ 的情况。确实会这样，不过不影响结果，因为这样符合题目要求而且我们要取的是最大值。）

其它情况下 $f(A)$ 的值为 $2$。

时间复杂度为 $O(n)$。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

#include <cstdio>
#include <algorithm>
#define N 300005
int a[N], f[N][2], ans[N];
int main() {
    int t; scanf("%d", &t);
    while(t--) {
        int n; scanf("%d", &n);
        for(int i = 1; i <= n; ++i) scanf("%d", a + i);
        if(a[n] == 0) { f[n][0] = 1; f[n][1] = 0; }
        else { f[n][0] = 0; f[n][1] = 1; }
        int mxf0 = f[n][0];
        for(int i = n - 1; i >= 1; --i) {
            if(i + a[i] + 1 == n + 1) {
                f[i][0] = 1;
            }
            else if(i + a[i] + 1 <= n && f[i + a[i] + 1][0] > 0) {
                f[i][0] = f[i + a[i] + 1][0] + 1;
            }
            else f[i][0] = 0;

            f[i][1] = mxf0 + 1;
            if(i + a[i] + 1 > n + 1) f[i][1] = std::max(f[i][1], 1);
            else if(i + a[i] + 1 <= n && f[i + a[i] + 1][1] > 0) {
                f[i][1] = std::max(f[i][1], f[i + a[i] + 1][1] + 1);
            }

            if(f[i + 1][0] > 0) {
                if(f[i + 1][0] == a[i]) ans[i] = 0;
                else ans[i] = 1;
            }
            else if(f[i + 1][1] >= a[i]) ans[i] = 1;
            else ans[i] = 2;

            mxf0 = std::max(mxf0, f[i][0]);
        }
        for(int i = 1; i < n; ++i) printf("%d%c", ans[i], (i ^ (n - 1)) ? ' ' : '\n');
    }
    return 0;
}

• 上一篇
• 下一篇