2.4 序列判定

发表于 | 更新于 | 分类于 | 阅读次数：

实验任务

YellowStar 某天得到了一个长度为 \(n\) 的序列 \(a\)，他要判定这个序列的好坏。定义一个序列为好序列应当满足：它的所有连续子序列，至少包含了一个在该子序列中只出现一次的数字。否则这个序列为坏序列。请你帮他判定序列是不是好序列。

数据输入

输入的第一行为数字 \(T\)，表示有 \(T\) 组样例每组样例第输入的第 1 行为数字 \(n\ (1\leq n\leq 10^3)\)，表示序列长度。接下来 1 行包含 \(n\) 个数字，\(a_1,a_2,\cdots ,a_n\ (1 \leq a_i \leq 10^9)\)。

数据输出

对于每个样例，输出”Good”表示好序列，”Bad” 表示坏序列。(注意输出不包含引号)

输入示例 输出示例
3
5
6 2 3 2 6
5
6 2 3 4 5
5
1 2 1 2 1		 Good
Good
Bad

数据范围

\(80\%\)的得分点，\(n \leq 100\)；\(20\%\)的得分点，\(n \leq 1000\)。

源代码（分治）

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
#define maxn 1005
int mydata[maxn];
int mymap[maxn];
int pos[maxn];

//分治算法：最坏情况是n^2，平均情况是O(nlogn)
bool isGood(int left, int right){
    if (right - left < 2)
        return true;//长度不够的序列直接返回
    memset(mymap, 0, sizeof(mymap));
    int i, diffL, diffR;
    for (i = left; i < right; ++i)//标记每个数出现次数
        ++mymap[mydata[i]];
    int mid = (left + right) >> 1;
    for (diffL = mid - 1; diffL >= left; --diffL)
        if (mymap[mydata[diffL]] == 1)
            break;//左起最右
    for (diffR = mid; diffR < right; ++diffR)
        if (mymap[mydata[diffR]] == 1)
            break;//右起最左
    if (diffL == left - 1 && diffR == right)
        return false;//没有唯一数返回false
    //分治
    return isGood(left, diffL)
        && isGood(diffL + 1, diffR)
        && isGood(diffR + 1, right);
}

bool cmpData(const int a, const int b) { return mydata[a] < mydata[b]; }

//离散化
void preprocess(int n)
{//排序，压缩，再回排 --> 下标排序可以节省回排的时间！！！
    int i, temp = 0, count = 0;
    sort(pos, pos + n, cmpData);
    temp = mydata[pos[0]];
    mydata[pos[0]] = 0;
    for (i = 1; i < n; ++i){
        if (mydata[pos[i]] == temp)
            mydata[pos[i]] = count;
        else{
            temp = mydata[pos[i]];
            mydata[pos[i]] = ++count;
        }
    }
}

int main(){
    int T, n, i;
    scanf("%d", &T);
    while (T--){
        scanf("%d", &n);
        for (i = 0; i < n; ++i){
            scanf("%d", &mydata[i]);
            pos[i] = i;
        }
        preprocess(n);//预处理：将无意义的数据压缩到n，复杂度O(nlogn)
        printf("%s\n", isGood(0, n) ? "Good" : "Bad");//判断是否满足条件，复杂度O(nlogn)
    }
    return 0;
}

设计思路与复杂度分析

首先需要将数据离散化：题目要求找不同，并没有要求给出这个不同的数是谁，所以\(a_i\)的具体值就无意义了。另一方面\(Z_1:1\leq n\leq 10^3\)，\(Z_2:1\leq a_i\leq 10^9\)。由此，可以生成一个\(Z_1\)到\(Z_2\)的映射，使得可以使用数组来标记每一个数出现的次数。

然后使用分治策略：寻找一个串中最靠近中间的唯一数，如果不存在，则返回\(false\)。如果存在，则该串中包含当前数字的子串都满足要求，则可以直接判断左边和右边不包含当前字符的两个子串的所有子串是否满足条件。具体实现的时候还有一个可以优化的点是已经找出串中的两个唯一数，其实只要包含这两个数中的任一个的子串都是符合要求的。

复杂度分析：算法实现类似快排，平均时间复杂度\(O(nlogn)\)，最坏时间复杂度\(O(n^2)\)。

源代码（线段树）

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
const int maxn = 1005;
int a[maxn], v[maxn], L[maxn], R[maxn], last[maxn];
pii seg[maxn];

struct SegmentTree {
#define ls ((t)<<1)
#define rs ((t)<<1|1)
    int count[maxn << 2];
    void build(int t, int l, int r) {
        count[t] = 0;
        if (l < r) {
            int z = (l + r) >> 1;
            build(ls, l, z), build(rs, z + 1, r);
        }
    }
    void update(int t, int l, int r, int L, int R, int V) {
        if (L <= l && r <= R) {count[t] += V;return;}
        int z = (l + r) >> 1;
        if (R <= z) {update(ls, l, z, L, R, V);}
        else if (L > z) {update(rs, z + 1, r, L, R, V);}
        else {
            update(ls, l, z, L, R, V);
            update(rs, z + 1, r, L, R, V);
        }
    }
    int query(int t, int l, int r, int L, int R) {
        if (count[t] > 0) return r - l + 1;
        if (l == r) return 0;
        int z = (l + r) >> 1;
        if (R <= z) return query(ls, l, z, L, R);
        if (L > z) return query(rs, z + 1, r, L, R);
        return query(ls, l, z, L, R) + query(rs, z + 1, r, L, R);
    }
} tree;

bool cmp(const pii &a, const pii &b) {
    return a.fi < b.fi;
}

bool solve(int n) {
    int seg_index = 0, i;
    tree.build(1, 0, n - 1);
    for(i=0;i<n;++i) {
        while (seg_index < n && seg[seg_index].fi == i) {
            //覆盖所有p（i被p的左区间覆盖）的右区间
            int pos = seg[seg_index++].se;
            tree.update(1, 0, n - 1, pos, R[pos] - 1, 1);
        }
        //如果[i,n-1]没有全部被覆盖，说明存在包含左端点i的坏序列
        int len = tree.query(1, 0, n - 1, i, n - 1);
        if (len < n - i) return false;
        //删除中点为i的右区间的贡献[i,R[i]-1]，因为下一步已经不包含i了
        tree.update(1, 0, n - 1, i, R[i] - 1, -1);
    }
    return true;
}

int main() {
    int T, n, m, i;
    scanf("%d", &T);
    for (int cas = 0; cas < T; ++cas) {
        scanf("%d", &n);
        for (i = 0; i<n; ++i) scanf("%d", a + i), v[i] = a[i];
        // compress
        sort(v, v + n);
        m = unique(v, v + n) - v;
        for (i = 0; i<n; ++i) a[i] = lower_bound(v, v + m, a[i]) - v;
        // get L[i] - same value with max index at the left of i
        for (i = 0; i<m; ++i) last[i] = -1;
        for (i = 0; i<n; ++i) L[i] = last[a[i]], last[a[i]] = i;
        // get R[i] - same value with min index at the right of i
        for (i = 0; i<m; ++i) last[i] = n;
        for (i = n-1; i>=0; --i) R[i] = last[a[i]], last[a[i]] = i;
        // get left intervals
        for (i = 0; i<n; ++i) seg[i] = mp(L[i] + 1, i);
        sort(seg, seg + n, cmp);
        puts(solve(n) ? "Good" : "Bad");
    }
    return 0;
}

设计思路与复杂度分析

此代码使用了线段树，线段树其实也是分治，时间复杂度为\(O(nlogn)\)。现分析如下（至于线段树的知识自己参考互联网资料）。

预处理阶段： 1. 将数据离散化，思想与分治一致，活用STL使得代码更简洁； 2. 获取每一个中点的最大影响区间的左端点\(L[i]:i\)左边的与\(a[i]\)相同的下标最大的数； 3. 获取每一个中点的最大影响区间的右端点\(R[i]:i\)右边的与\(a[i]\)相同的下标最小的数； 4. 获取每一个左区间并按左端点排序（知道了左区间其右区间可以迅速查找到），注意前两步获取的区间端点是无效的，此步骤左区间左端点已经是有效的了。此时左区间为闭区间间，而右区间为左闭右开区间。按左区间排序的目的是一会儿要由左向右以左端点为基准扫描。

区间覆盖阶段：

设当前扫描到第i个位置，第\(i-1\)个数\(a[i-1]\) 作为左端点的最大影响区间是\([p,R[p]-1]\)（\(p\)为该左区间的右端点）。也就是他能保证任何\([l,r]\ (p\leq l\leq r\leq R[p]-1)\) 的序列是合法的。每次我们考虑\(i\ (0\leq i < n)\) 的所有影响区间与在\(i\)之前加入的影响区间一起能 否完全覆盖\([i,n-1]\)这个大区间（能覆盖\([i,n-1]\)这个大区间说明如下区间都是好的：\([i,i+1],[i,i+2],\cdots ,[i,n-1]\)，其中右端点为\([i,p-1]\) 的区间的合法性由中点为\(i\) 的区间保证，他们可能在之前就被覆盖了。），如果能则说明所有以\(i\) 为起点的子序列都是满足条件的，这样我们就可以\(++i\) 然后重复之前的步骤，否则说明以\(i\) 为起点的子序列中存在坏序列，直接结束退出。

但是当\(i\)往右移动的时候，某一次加入的以\(i\) 为中点的覆盖会失效（因为以后的区间已经不包含\(i\)），所以需要在\(i\)右移之前将该区间清除掉。一定会存在这个区间，它是在第\(i\)个点作为中点（左区间为\((l,i)\ (l\leq i)\)，右区间为\((i,R[i]-1)\)）的时候覆盖进来的。

0%