首页 > 代码库 > Uva1608

Uva1608

2024-09-23 08:00:27   212人阅读

如果一个序列的所有子序列中均存在至少一个元素，这个元素在该子序列中只出现一次，则这个序列non-boring。

当一个序列[x,y]中没有元素只出现一次，那么该序列不符合要求，如果有的话，设为第i个元素，则 只要[x,i-1]和 [i+1,n] 符合要求，则该序列符合要求。

在O(N)的时间内预处理一个元素左右离它最近的相同元素的位置，即可在O(1)时间内查询是否这个元素在给定序列中只出现一次。

 1 #include <bits/stdc++.h> 2  3 using namespace std; 4  5 const int inf = 0x3f3f3f3f; 6  7 const int maxn = 200000; 8  9 int t;10 11 int a[maxn+10];12 13 int lef[maxn+10];14 15 int rgt[maxn+10];16 17 map<int, int> ml, mr;18 19 bool judge(int i, int x, int y){20         if(lef[i] < x && rgt[i] > y){21             //printf("%d %d %d\n",i,lef[i],rgt[i]);22             return 1;23         } else {24             return 0;25         }26 }27 28 bool dfs(int x, int y){29     if(x >= y){30         return 1;31     }32     if(x + 1  == y){33         return a[x] != a[y];34     }35     int res = 0;36     for(int i = x, j = y; i <= j ; ++i, --j){37                 if(judge(i, x, y)){38                 //    printf("dsadsa:%d %d %d\n",i,x,y);39                     res = dfs(x, i-1) && dfs(i+1, y);40                 } else if(judge(j, x, y)){41                 //    printf("AAAAAA:%d %d %d\n",j,x,y);42                     res = dfs(x,j-1) && dfs(j+1, y);43                 }44                 if(res == 1){45                     return 1;46                 }47     }48     return 0;49 }50 51 void init(){52     ml.clear();53     mr.clear();54 }55 56 int main(){57         scanf("%d",&t);58         while(t--){59             init();60             int n;61             scanf("%d",&n);62             for(int i = 1; i <= n; ++i){63                 scanf("%d",&a[i]);64                 lef[i] = 0;65                 rgt[i] = inf;66             }67 68             for(int i = 1, j = n; i <= n && j >= 1; ++i,--j){69                     int tmp = ml[a[i]];70                     int tmp1 = mr[a[j]];71                      if(tmp){72                         lef[i] = tmp;73                     }74                     ml[a[i]] = i;75                     if(tmp1){76                         rgt[j] = tmp1;77                     }78                     mr[a[j]] = j;79             }80 81             int ans = dfs(1,n);82             if(ans == 0){83                 printf("boring\n");84             } else {85                 printf("non-boring\n");86             }87             88         }89 }

 

Uva1608


联系
我们