分治
找到第一个唯一的字符。再递归找它左边和右边的部分。
找到一个唯一的字符，则说明只要包含该字符的子串一定是non-boring的，则只需要再验证其左边和右边的子串。
再来考虑从哪里开始找这唯一的子串，如果从头开始找，则最坏的复杂度为O(n2) ，必然不行。所以考虑从两边往中间找，或者从中间往两边找。则复杂度为O(nlogn)。
不过有个问题，我从中间往两边找还是超时了，改成两边往中间找AC。是因为数据问题吗？复杂度应该是一样的啊。
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
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int t, n;
int a[maxn], p1[maxn], p2[maxn];
map<int, int>mp;
bool solve(int L, int R) {
if (L >= R)return true;
int tmp = -1;
int i = L, j = R;
while (i<=j) {
if (p1[i]<L&&p2[i]>R) {
tmp = i;
break;
}
if (p1[j]<L&&p2[j]>R) {
tmp = j;
break;
}
i++; j--;
}
if (i > j)return false;
return solve(L, tmp - 1) && solve(tmp + 1, R);
}
int main() {
scanf("%d", &t);
while (t--) {
mp.clear();
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
for (int i = 1; i <= n; i++) {
if (!mp.count(a[i])) p1[i] = -1;
else p1[i] = mp[a[i]];
mp[a[i]] = i;
}
mp.clear();
for (int i = n; i >= 1; i--) {
if (!mp.count(a[i])) p2[i] = INF;
else p2[i] = mp[a[i]];
mp[a[i]] = i;
}
if (solve(1, n))printf("non-boring\n");
else printf("boring\n");
}
return 0;
}
|
