覆盖的串 chuan

Description

我们称一个字符串 A 覆盖了一个字符串 B 当且仅当对于 B 中的每一个字符,都有一个包含它的和 A 相同的子串。例如,A={1,2,1}覆盖了 B={1,2,1,2,1,1,2,1}。
所谓的最短覆盖子串,指的是覆盖该串的最短子串。例如 B 的最短覆盖子串为 A,长度为 3。
最短覆盖前缀数组指的是对于一个串的每一个前缀,它们的最短覆盖子串长度按顺序组成的数组。例如 B 的最短覆盖前缀数组为{1,2,3,2,3,6,7,3}。
现在给你一个最短覆盖前缀数组,判断是否存在某个串符合条件,如果存在则给出一组解。

Input

第一行一个整数 t 表示数据组数。
每组数据两行,第一行为一个整数 n 表示最短覆盖前缀数组长度,也即原串长。
第二行 n 个整数表示最短覆盖前缀数组。

Output

每组数据输出一行或两行。如果存在一个满足条件的串,先输出一行“Yes”,第二行输出 n 个整数表示一组合法解。否则只需输出一行“No”。

Sample Input and Output

chuan.in chuan.out
4
8
1 2 3 2 3 6 7 3
5
1 1 1 1 1
3
1 2 2
7
1 2 3 4 5 6 7
Yes
1 2 1 2 1 1 2 1
Yes
1 1 1 1 1
No
Yes
7 6 5 4 3 2 1

HINT

对于 30%的数据满足若有解必存在一组只包含两个以内不同字符的解,n<=15;
对于 70%的数据满足所有数据的 n 之和不超过 5,000;
对于 100%的数据满足所有数据的 n 之和不超过 500,000 且t<=10。

Source

AHSDFZ 集训 day4 t2

Solution

貌似是结论题。

我们令a表示原串,ans[i]表示最短覆盖前缀数组第i个的值,b表示给出的ans,next[i]表示原串KMP的next,last[i]表示此前最后一次ans为i的位置

甩出三个结论:

  1. ans[i]=i或ans[next[i]] (首先不可能小于ans[next[i]],如果大于ans[next[i]]是否可以?挖个坑。。。
  2. a[1…ans[i]] == a[i-ans[i]+1…i]
  3. 按照2方法强行构造出的解决方案c如果不符合b就是无解,否则解为c

对于第一个结论我们有:如果i – lst[c[nex[i]]] > c[nex[i]]则ans[i]=i否则为ans[next[i]]

对于第二个结论:区间相等,我们可以rmq+并查集搞。并查集开log个,每个f(i,j)维护从i开始跳2^j步相当于右边的从第f(i,j)个地方开始跳2^j步的串。

这样原先是暴力合并并查集,现在是倍增地合并了。

所以第二个就解决了,第三个我们O(n)扫一遍判一下就好了。

总复杂度\(O(n \log n \alpha (n) )\)

Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <functional>
#include <map>
#include <queue>
#include <set>
//#define OJ
#define PROB "chuan"
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int INF = 1000000007;
const int maxn = 500005;

//struct edge_T {int to, next;} edge[maxn<<1];


int nex[maxn], f[20][maxn], a[maxn], b[maxn], c[maxn], lst[maxn];

int n, T[maxn], l1, l2, r1, r2;

int Find(int k, int x) {
    if (f[k][x] == x) return x;
    return f[k][x] = Find(k, f[k][x]);
}

inline int getint() {
    int r = 0; bool b = true; char c = getchar();
    while ('0' > c || c > '9') {if (c == '-') b = false; c = getchar();}
    while ('0' <= c && c <= '9') {r = r * 10 + (c - '0'); c = getchar();}
    if (b) return r;
    return -r;
}

void mer(int k, int x, int y) {
    int a = Find(k, x), b = Find(k, y);
    if (a != b) {
        f[k][a] = b;
        if ((--k) >= 0) {
            mer(k, x, y);
            mer(k, x+(1<<k), y+(1<<k));
        }
    }
}

void MERGE() {
    for (int i = 0; i < 20; ++i)
        for (int j = 1; j <= n; ++j)
            f[i][j] = j;
    for (int i = 1; i <= n; ++i) {
        l1 = 1;
        r1 = a[i];
        l2 = i-a[i]+1;
        r2 = i;
        int x = T[r1-l1+1];
        mer(x, l1, l2);
        mer(x, r1-(1<<x)+1, r2-(1<<x)+1);
    }
    for (int i = 1; i <= n; ++i) b[i] = Find(0, i);
}

bool CHECK() {
    int p = 0;
    nex[1]=0;
    for (int i = 2; i <= n; ++i) {
        while (p && b[p+1] != b[i]) p = nex[p];
        if (b[p+1] == b[i]) ++p;
        nex[i] = p;
    }
    for (int i = 1; i <= n; ++i) lst[i] = 0;
    for (int i = 1; i <= n; ++i) {
        if (nex[i] == 0) {c[i] = i; lst[i] = i;}
        else if (i - lst[c[nex[i]]] > c[nex[i]]) {c[i] = i; lst[i] = i;}
        else {c[i] = c[nex[i]]; lst[c[nex[i]]] = i;}
    }
    for (int i=1;i<=n;++i)if(c[i]!=a[i])return false;
        return true;
}

int main() {
#ifndef OJ
    freopen(PROB".in", "r", stdin);
    freopen(PROB".out", "w", stdout);
#endif
    T[0] = -1;
    for (int i = 1; i <= 500000; ++i) T[i]=T[i>>1]+1;

    int T = getint();
    while(T--) {
        n = getint();
        for (int i = 1; i <= n; ++i) a[i] = getint();
        MERGE();
        if (CHECK()) {
            puts("Yes");
            for (int i = 1; i <= n; ++i) printf("%d ", b[i]);
            putchar('\n');
        } else puts("No");
    }

    fclose(stdin);
    fclose(stdout);

    return 0;
}
Show Comments