经验总结

  1. 首页 > 生活 > >

XXI Open Cup, Grand Prix of Belarus 2020-2021 Winter Petrozavodsk Camp, Belarusian SU Contest 题解( 三 )

生活百科


Solution队友：线段树+分治因为本题中删除一个数后会改变相邻关系，所以某一段区间的最大值可以把该区间剩余的数删完的 。那么把当前区间的最大值挑出来加入答案后，会分成左右两个小区间，其各自的区间最大值也是有可能留到最后的，因此可以用分治加线段树维护区间最值来做这题 。
\([1，2，5，3，2]\)，对于这组数来说，最终留下的数一定是5，因为在取出最大值5后，分成了 \([1, 2]\)和$ [3,2]$ 两个区间，但是我们发现两个区间的最大值2和3只能成长到3和4，也就是\([3，5，4]\)，所以无法留到最后 。从这里我们可以发现，对于每个分出来的区间，都会有一个区间下限，如果该区间的最大值在成长之后达不到这个下限，那么这个区间就是无法产生“胜者”的 。
【XXI Open Cup, Grand Prix of Belarus 2020-2021 Winter Petrozavodsk Camp, Belarusian SU Contest题解】接下来考虑如何获得每个区间的下限 。我们用三元组\({L, R, V}\)来表示\([L, R]\)这段区间的下限值为\(V\)，假设该区间最大值的下标为\(M\)，那对于左区间的下限\(V_1\)来说，不仅要“打败"\(a_M\), 还要在删完右区间后达到\(V\), 只有这样才能继续往大的区间吃 。即\(V_1 = Max(a_M,V+M-R-1)\) 。
Codeint n, a[maxn], maxx[maxn * 4];vector ans;void build(int id, int l, int r) {if (l == r) {maxx[id] = l;} else {build(ls, l, mid);build(rs, mid + 1, r);if (a[maxx[ls]] > a[maxx[rs]])maxx[id] = maxx[ls];elsemaxx[id] = maxx[rs];}}int query(int id, int l, int r, int ql, int qr) {if (ql <= l && qr >= r) return maxx[id];if (qr <= mid)return query(ls, l, mid, ql, qr);else if (ql > mid)return query(rs, mid + 1, r, ql, qr);else {int res1 = query(ls, l, mid, ql, mid);int res2 = query(rs, mid + 1, r, mid + 1, qr);if(a[res1] > a[res2]) return res1;else return res2;}}void solve(int l, int r, int maxx) {int pos = query(1, 1, n, l, r);if(a[pos] + r - l < maxx) return;ans.push_back(pos);if(l <= pos - 1) solve(l, pos - 1, max(a[pos], maxx + pos - 1 - r));if(pos + 1 <= r) solve(pos + 1, r, max(a[pos], maxx + l - pos - 1));}int main() {ios;cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];build(1, 1, n);solve(1, n, 0);cout << ans.size() << endl;sort(ans.begin(), ans.end());for (int i : ans) cout << i << " ";}

经验总结扩展阅读


上一篇：爬山作文

下一篇：工作7年收集到的git命令