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;}

推薦閱讀