GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版实现方式是找到序列中只存在一个的元素如果找不到说明不符合条件。假设找到的元素为i则递归计算 1到i-1 和 i1到n两个子序列如果两个子序列都满足条件则序列本身满足条件。为什么这样做可以实现我们把整个序列分成三种情况1到i-1的子序列i1到n的子序列以及穿过i的子序列。通过上面的例子可知穿过i的子序列有i作为只存在一个的元素因此肯定符合条件。只需要前两个子序列都符合条件即可。然后就是优化这个方法1. 找到序列中只存在一个的元素对于单个元素可以预先计算出两个表prevArr和nextArr分别代表上一个与下一个值相同元素的位置。计算方式可以通过预先设置一个map辅助。这样求单个元素是否在子序列中是唯一的可以通过O(1)的时间复杂度得出。2. 如果从序列头到序列尾依次查找只存在一个的元素还是会超时。假设每次都查找到最后一个元素才成功则 需要时间的递归公式为T(n) n T(n-1) O(n) T(n-1) 这样最后时间复杂度最高为O(n^2)。但如果从头尾两侧同时遍历则最坏只需要遍历到序列中间就能找到且这个最坏时间可以将序列分成平均的两半。T(n) n/2 n/2 2T(n/2) O(n) T(n/2)这样最后的时间复杂度为O(nlogn)。AC代码#include stdio.h #include map #define MAXN 200005 using namespace std; int arr[MAXN]; int prevArr[MAXN]; int nextArr[MAXN]; int n; mapint, int mp; void init() { int i, j, k; mp.clear(); for (i 1; i n; i) { if (!mp[arr[i]]) prevArr[i] 0; else prevArr[i] mp[arr[i]]; mp[arr[i]] i; } mp.clear(); for (i n; i 1; --i) { if (!mp[arr[i]]) nextArr[i] n 10; else nextArr[i] mp[arr[i]]; mp[arr[i]] i; } } bool computed(int beg, int end) { if (beg end) return true; int i, endi (end - beg) / 2 1; for (i 0; i endi; i) { if (prevArr[beg i] beg nextArr[beg i] end) return computed(beg, beg i - 1) computed(beg i 1, end); if (prevArr[end - i] beg nextArr[end - i] end) return computed(beg, end - i - 1) computed(end - i 1, end); } return false; } int main() { int t, i, j; scanf(%d, t); while (t--) { scanf(%d, n); for (i 1; i n; i) scanf(%d, arr[i]); init(); if (computed(1, n)) printf(non-boring\n); else printf(boring\n); } return 0; }
