【代码源每日一题Div1】好序列/BZOJ4059「启发式分治」
admin
2024-02-10 13:29:02

好序列

题目描述：

给你一个数组a，问是否满足他的每个子区间[l,r]满足，至少存在一个元素x仅出现了一次

思路：

很有意思的一道题，直观上很玄学，实际上很科学

我们可以处理出来每个数字a[i]上一次出现的位置计作pre[i]，和下一次出现的位置nex[i]，显然对于(pre[i], nex[i])的区间，每个子区间的pre[i]，i<=r<=nex[i]，都是满足至少存在一个元素仅出现一次

所以我们可以考虑分治，对于区间[l,r]，找到一个x,满足pre[x]&&nex[x]>r,则我们需要去计算区间[l,x-1]和[x+1,r]，如果这两个区间都符合条件，则这个整个的区间[l,r]是符合条件的，这就是一个简单的分治过程

但是如果直接让x从l枚举到r，则会超时，原因是如果每次的x都是在区间的最右边，那你每次都会遍历整个区间，而且下一个的区间长度是len-1,就会导致你的时间复杂度是 O(n2)O(n^2)O(n2)

我们可以考虑启发式分治，很玄学又非常科学

即我们从左边和右边同时进行枚举计算，这样每次的时间复杂度是最差的时候是x在最数组中间遇到，但是，有意思的是，在数组最中间的时候，你去dfs的两个区间的长度变成了原来的 12\frac{1}{2}21​,所以如果每次都是最坏情况，最多进行log(n)次递归就结束了

所以时间复杂度总体上来说是O(nlogn)

具体证明不太会，只是一个感性和理性结合理解出来的想法

#include
using namespace std;
#define int long long
#define endl '\n'
#define io ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define m_p(a, b) make_pair(a, b)typedef long long ll;
typedef pair pii;#define MAX 1000050int n, m, x;
int tr[MAX];
int pre[MAX];
int nex[MAX];bool split(int l, int r){if(l>=r)return 1;for(int L=l, R=r; L<=R;++L,--R){if(pre[L]r)return split(l, L-1)&&split(L+1,r);if(pre[R]r)return split(R+1, r)&&split(l, R-1);}return false;
}void work(){cin >> n;for(int i = 1; i <= n; ++i)cin>>tr[i];for(int i = 1; i <= n; ++i)pre[i]=-1, nex[i]=n+1;mapmp;for(int i = 1; i <= n; ++i){pre[i] = mp[tr[i]];nex[mp[tr[i]]] = i;mp[tr[i]] = i;}if(split(1,n))cout<<"non-boring\n";else cout<<"boring\n";
}signed main(){io;int t;cin>>t;while(t--)work();return 0;
}

上一篇：和“缷磨杀驴”的意思相近的成语有哪些

下一篇：形容老师对同学好的词语

相关内容

热门资讯

微软重组高层加速AI突围 AIPress.com.cn报道 12月30日消息，据英国《金融时报》报道，纳德拉今年对微软高级管理...
精测电子股价跌1.01%，嘉实... 12月30日，精测电子跌1.01%，截至发稿，报84.63元/股，成交5.73亿元，换手率2.93%...
国力电子股价跌1.01%，兴证... 12月30日，国力电子跌1.01%，截至发稿，报60.68元/股，成交4098.42万元，换手率0....
机器人50ETF(159559... 截至2025年12月30日 13:55，国证机器人产业指数强势上涨4.46%，成分股步科股份20cm...
华发股份股价跌1.18%，银华... 12月30日，华发股份跌1.18%，截至发稿，报4.19元/股，成交7790.53万元，换手率0.6...