网站建设交接函,高端网站建设的价格,网站对联广告代码,设计网站横幅CF1398F
Solution
我又来贡献暴力做法了。。。听说两只log不可能过1e6?
有一个显然的想法是#xff1a;
我们先预处理一个aia_iai表示第iii个位置的最长后缀长度#xff0c;满足该后缀中不同时存在0和1。
假设我们要求xixixi的答案#xff0c;那么一个位置jjj可以作…CF1398F
Solution
我又来贡献暴力做法了。。。听说两只log不可能过1e6?
有一个显然的想法是
我们先预处理一个aia_iai表示第iii个位置的最长后缀长度满足该后缀中不同时存在0和1。
假设我们要求xixixi的答案那么一个位置jjj可以作为一轮的结束点当且仅当aj≥ia_j\geq iaj≥i而一个结束位置序列p1p2...pkp_1p_2...p_kp1p2...pk合法当且仅当每一个pjp_jpj都是合法结束点并且相邻两个元素的差至少为iii保证不重合。
因此我们会贪心地从第一个满足aj≥ia_j\geq iaj≥i的jjj开始每次找一个最小的j′jj′满足j′≥jij\geq jij′≥ji且aj′≥ia_{j}\geq iaj′≥i然后从jjj跳到j′jj′最终的答案就是跳的步数。
这显然可以直接对aia_iai建区间线段树维护区间内的maxmaxmax线段树上二分求出j′jj′。
这个方法的时间复杂度为O(∑ansilogn)O(\sum ans_i\;\log n)O(∑ansilogn)而ansi≤⌊ni⌋ans_i\leq \lfloor\frac{n}{i}\rflooransi≤⌊in⌋因此总时间复杂度O(nlnnlogn)O(n\ln n\log n)O(nlnnlogn)注意常数即可。
PS别用偷懒用set维护常数起飞实测接近线段树的三倍。
Code
char st[MAXN];
int mx[MAXN 2], a[MAXN];
void build(int x, int l, int r) {if (l r) { mx[x] a[l]; return; }int mid (l r) 1;build(x 1, l, mid);build(x 1 | 1, mid 1, r);mx[x] max(mx[x 1], mx[x 1 | 1]);
}
int query(int x, int l, int r, int L, int y) {if (mx[x] y) return -1;if (l r) return l;int mid (l r) 1;if (L mid) return query(x 1 | 1, mid 1, r, L, y);else {int t query(x 1, l, mid, L, y);if (t ! -1) return t;return query(x 1 | 1, mid 1, r, mid 1, y);}
}
signed main() {
#ifndef ONLINE_JUDGEfreopen(a.in, r, stdin);
#endifint n, cnt0 0, cnt1 0;read(n), reads(st);for (int i 1, l 1; i n ; i) {auto add [](char x, int y) {if (x 0) cnt0 y; if (x 1) cnt1 y;};add(st[i], 1);while (cnt0 cnt1) add(st[l ], -1);a[i] i - l 1;}build(1, 1, n);for (int i 1; i n ; i) {int cnt 0, r 1;for (; r n ;) {r query(1, 1, n, r, i);if (r -1) break;r i; cnt;}print(cnt), putc( );}return 0;
}
Update 4.5 23:30
上面的代码跑了1890ms1890ms1890ms我们觉得它不够优秀于是冷静分析一下它慢在哪里发现全1的数据就可以把它卡满这是为什么呢这是因为我们在长长的没有0的段里面做了很多次query这其实是不必要的我们同样可以预处理以每个位置开始的最长段。这样就可以O(1)O(1)O(1)计算整个段的贡献。
我们提交后发现它只跑了249ms249ms249ms
理性分析一下它的时间复杂度相当于整个序列被01分割为若干段跳到一个段就可以O(1)O(1)O(1)计算答案并且O(logn)O(\log n)O(logn)跳到下一个段这样每一段会有O(len)O(len)O(len)次贡献因为每一个长度大于iii的段才可能产生贡献每次贡献为O(logn)O(\log n)O(logn)因此总时间复杂度为O(nlogn)O(n\log n)O(nlogn)
Updated code
//线段树部分同上
signed main() {
#ifndef ONLINE_JUDGEfreopen(a.in, r, stdin);
#endifint n, cnt0 0, cnt1 0;read(n), reads(st);for (int i 1, l 1; i n ; i) {auto add [](char x, int y) {if (x 0) cnt0 y; if (x 1) cnt1 y;};add(st[i], 1);while (cnt0 cnt1) add(st[l ], -1);a[i] i - l 1;}cnt0 0, cnt1 0;for (int i n, r n; i 1 ; -- i) {auto add [](char x, int y) {if (x 0) cnt0 y; if (x 1) cnt1 y;};add(st[i], 1);while (cnt0 cnt1) add(st[r --], -1);b[i] r - i;}build(1, 1, n);for (int i 1; i n ; i) {int cnt 0, r 1;for (; r n ;) {r query(1, 1, n, r, i);if (r -1) break;int p b[r] / i;cnt p 1, r i * (p 1);}print(cnt), putc( );}return 0;
}
