浙江龙网

  1. 首页 > 生活百科 > >

Div. 3 Codeforces Round #828 A-F( 二 )

生活百科

F题解知识点：枚举，双指针，数学 。
尝试从小到大枚举 \(x \in [1,n]\) ，计算满足 \(med(l,r) < mex(l,r) = x\) 的段的个数（ \(x = 0\) 显然没有满足的） 。
首先 ， 对于一段 \([l,r]\) 满足 \(mex(l,r) = x\) 一定包括了 \([0,x-1]\) 的数字 。因此 ， 当且仅当段长度 \(r-l+1 \leq 2x\) 才满足中位数 \(med(l,r)<mex(l,r) = x\)，否则必然包括 \(>x\) 的数字 。
假设要求 \(mex(l,r) = x\)  ， 先得到满足 \(mex(l,r) = x\) 的最小段 \([l,r]\)  ， 随后找到 \(x+1\) 的位置 \(pos\) （假设 \(pos\) 在 \([l,r]\) 外，在里面就不存在这个 \(mex\) 了qwq） 。
不妨设 \(pos>r\) ，只要不包括 \(pos\) 这个位置，其他从 \([l,r]\) 扩展的段的 \(mex\) 一定是 \(x\)，因此可以枚举 \([r,pos)\) 的每个位置作为右端点 \(i\)，找到最远左端点 \(j = \max(1,i-2x+1)\)，随后每次可以得到 \(\max(0,l-i+1)\) 个合法段 。同理可以求 \(pos<l\) 的情况 。
我们可以从 \(mex(l,r) = 1\) 开始枚举 ， 显然 \(l = pos[0],r = pos[0]\)。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;int p[200007], pos[200007];bool solve() {int n;cin >> n;for (int i = 0;i <= n;i++) pos[i] = 0;for (int i = 1;i <= n;i++) cin >> p[i], pos[p[i]] = i;int l = pos[0], r = pos[0];ll ans = 0;for (int x = 1;x <= n;x++) {if (l <= pos[x] && pos[x] <= r) continue;//目标mex被之前的mex段包括了 ， 说明这个mex不会出现int len = 2 * x;//一个mex>med段的最长长度是2mexif (pos[x] > r) {//段mex在右侧for (int i = r;i < pos[x];i++) {int j = max(1, i - len + 1);//长度限制内，左端点可以到哪ans += max(0, l - j + 1);}}else {for (int i = l;i > pos[x];i--) {int j = min(n, i + len - 1);ans += max(0, j - r + 1);}}l = min(pos[x], l);r = max(pos[x], r);}cout << ans << '\n';return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}

推荐阅读


上一篇：原神圣显之钥升级突破材料是什么

下一篇：Arctic 基于 Hive 的流批一体实践