UVa 1608 - Non-boring sequences

链接：

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4483

题意：

如果一个序列的任意连续子序列中至少有一个只出现一次的元素，则称这个序列是不无聊（non-boring）的。
输入一个n（n≤200000）个元素的序列A（各个元素均为1e9以内的非负整数），判断它是不是不无聊的。

分析：

在整个序列中找一个只出现一次的元素，如果不存在，则这个序列不是不无聊的；
如果找到一个只出现一次的元素A[k]，则只需检查A[1…k-1]和A[k+1…n]是否满足条件（分治）。
设长度为n的序列需要T(n)时间，则有T(n) = max{T(k-1) + T(n-k) + 找到唯一元素k的时间}。
如何找唯一元素？如果事先算出每个元素左边和右边最近的相同元素，
则可以在O(1)时间内判断在任意一个连续子序列中，某个元素是否唯一。
如果从左边找，最坏情况下唯一元素是最后一个元素，因此
T(n) = T(n-1) + O(n)≥T(n) = O(n*n)
从右往左找也一样，只不过最坏情况变成了“唯一元素是第一个元素”，但时间复杂度不变。
那么，从两边往中间找会怎样？此时T(n) = max{T(k) + T(n-k) + min(k,n-k)}，
而此时的最坏情况是唯一元素在中间的情况，它满足经典递推式T(n) = 2T(n/2) + O(n)，即T(n)=O(nlogn)。

代码：

 #include <cstdio>

 #include <map>

 using namespace std;

 const int UP =  + ;

 int a[UP], prior[UP], after[UP];

 inline bool check(int p, int L, int R){

     return prior[p] < L && after[p] > R;

 }

 bool judge(int L, int R){

     if(L >= R) return true;

     for(int d = ; L + d <= R - d; d++){

         if(check(L+d, L, R)) return judge(L, L+d-) && judge(L+d+, R);

         if(L + d == R - d) break;

         if(check(R-d, L, R)) return judge(R-d+, R) && judge(L, R-d-);

     }

     return false;

 }

 int main(){

     int T, n;

     scanf("%d", &T);

     while(T--){

         map<int,int> M;

         scanf("%d", &n);

         for(int i = ; i < n; i++){

             scanf("%d", &a[i]);

             prior[i] = M.count(a[i]) ? M[a[i]] : -;

             M[a[i]] = i;

         }

         M.clear();

         for(int i = n - ; i >= ; i--){

             after[i] = M.count(a[i]) ? M[a[i]] : n;

             M[a[i]] = i;

         }

         if(judge(, n-)) printf("non-boring\n");

         else printf("boring\n");

     }

     return ;

 }

巴特西

UVa 1608 - Non-boring sequences

最新文章

热门文章