题目
思路
1.主要思路:如果有一个只出现一次的元素A[p],那么所有包含此元素的所有连续子序列都满足不无聊。那么只需分治判断A[0~p-1]和A[p+1~n]是否不无聊即可。
2.分治方向的选择:(上界分析)
- 从左往右找:最坏情况是唯一元素恰好在最右边。
- 从右往左找:最坏情况是唯一元素恰好在最左边。
-
从两头往中间找(中途相遇法):最坏情况是唯一元素恰好在最中间。
(此处其实有点类似快排的方法)
代码
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <map>
using namespace std;
const int maxn = 200000+10000;
int n, A[maxn], myprev[maxn], mynext[maxn];
map<int, int> cur;
void init(){
cur.clear();
for (int i = 0; i<n; i++){
if (!cur.count(A[i]))
cur[A[i]] = -1;
myprev[i] = cur[A[i]];
cur[A[i]] = i;
}
cur.clear();
for (int i = n-1; i>=0; i--){
if (!cur.count(A[i])){
cur[A[i]] = -1;
}
mynext[i] = cur[A[i]];
cur[A[i]] = i;
}
}
bool solve(int L, int R){
//printf("%d %d\n",L,R);
if (L == R-1 || L>=R) return true;
int i = L, j = R-1; //[i.j]
while(i<=j){
if (!(myprev[i] >= L && myprev[i] < R) && !(mynext[i] >= L && mynext[i] < R) && i<=j)
return solve(L,i) && solve(i+1,R);
i++;
if (!(myprev[j] >= L && myprev[j] < R) && !(mynext[j] >= L && mynext[j] < R) && i<=j)
return solve(L,j) && solve(j+1,R);
j--;
}
return false;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&n); // scanf的输入效率???
for(int i = 0; i<n; i++)
scanf("%d",&A[i]);
init();
if (solve(0,n)) printf("non-boring\n");
else printf("boring\n");
}
return 0;
}