填坑系列(p.248)
比较神
从两端枚举
最坏复杂度就成O(nlogn)了
1 #include<cstdio> 2 #include<cstdlib> 3 #include<algorithm> 4 #include<iostream> 5 #include<cstring> 6 #include<string> 7 8 using namespace std; 9 10 void setIO(const string& a) { 11 freopen((a + ".in").c_str(), "r", stdin); 12 freopen((a + ".out").c_str(), "w", stdout); 13 } 14 15 template<typename Q> void read(Q& x) { 16 static char c; 17 static bool f; 18 for(f = 0; c = getchar(), !isdigit(c); ) if(c == '-') f = 1; 19 for(x = 0; isdigit(c); c = getchar()) x = x * 10 + c - '0'; 20 if(f) x = -x; 21 } 22 template<typename Q> Q read() { 23 static Q x; read(x); 24 return x; 25 } 26 27 const int N = 200000 + 10; 28 29 int a[N], lp[N], rp[N]; 30 31 #include<map> 32 map<int, int> cur; 33 34 bool unique(int p, int l, int r) { 35 return lp[p] < l && rp[p] > r; 36 } 37 38 bool check(int L, int R) { 39 if(L >= R) return 1; 40 for(int k = 0; L + k <= R - k; k++) { 41 if(unique(L + k, L, R)) return check(L, L + k - 1) && check(L + k + 1, R); 42 if(unique(R - k, L, R)) return check(L, R - k - 1) && check(R - k + 1, R); 43 } 44 return 0; 45 } 46 47 int main() { 48 #ifdef DEBUG 49 freopen("in.txt", "r", stdin); 50 freopen("out.txt", "w", stdout); 51 #endif 52 53 int T = read<int>(); 54 while(T--) { 55 int n = read<int>(); 56 cur.clear(); 57 for(int i = 1; i <= n; i++) { 58 read(a[i]); 59 if(cur.count(a[i])) lp[i] = cur[a[i]]; 60 else lp[i] = 0; 61 cur[a[i]] = i; 62 } 63 cur.clear(); 64 for(int i = n; i >= 1; i--) { 65 if(cur.count(a[i])) rp[i] = cur[a[i]]; 66 else rp[i] = n + 1; 67 cur[a[i]] = i; 68 } 69 puts(check(1, n) ? "non-boring" : "boring"); 70 } 71 72 return 0; 73 }