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}。
现在给你一个最短覆盖前缀数组，判断是否存在某个串符合条件，如果存在则给出一组解。
第一行一个整数 t 表示数据组数。
每组数据两行，第一行为一个整数 n 表示最短覆盖前缀数组长度，也即原串长。
第二行 n 个整数表示最短覆盖前缀数组。
Output
每组数据输出一行或两行。如果存在一个满足条件的串，先输出一行“Yes”，第二行输出 n 个整数表示一组合法解。否则只需输出一行“No”。
chuan.inchuan.out4
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 7Yes
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的位置
甩出三个结论：
- ans[i]=i或ans[next[i]] （首先不可能小于ans[next[i]],如果大于ans[next[i]]是否可以？挖个坑。。。）
- a[1…ans[i]] == a[i-ans[i]+1…i]
- 按照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
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
| #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;
}
|