经验总结

  1. 首页 > 生活 > >

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

生活百科


时间复杂度 \(O(10^5)\)
空间复杂度 \(O(10^5)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;int cnt;bool vis[100007];int prime[100007];void euler_screen(int n) {for (int i = 2;i <= n;i++) {if (!vis[i]) prime[++cnt] = i;for (int j = 1;j <= cnt && i * prime[j] <= n;j++) {vis[i * prime[j]] = 1;if (i % prime[j] == 0) break;}}}int a, b, c, d;vector<pair<int, int>> fd;ll val;vector<int> af;void dfs(int step, ll mul) {if (mul > c) return;if (step == fd.size()) {if (val / mul <= d) af.push_back(mul);return;}for (int i = 0;i <= fd[step].second;i++) {dfs(step + 1, mul);mul *= fd[step].first;}}bool solve() {cin >> a >> b >> c >> d;map<int, int> mp;int tt = a;for (int i = 1;prime[i] * prime[i] <= tt;i++) {while (tt % prime[i] == 0) mp[prime[i]]++, tt /= prime[i];}if (tt > 1) mp[tt]++;tt = b;for (int i = 1;prime[i] * prime[i] <= tt;i++) {while (tt % prime[i] == 0) mp[prime[i]]++, tt /= prime[i];}if (tt > 1) mp[tt]++;fd.clear();for (auto [x, y] : mp) fd.push_back({ x,y });af.clear();val = 1LL * a * b;dfs(0, 1);int ansx = -1, ansy = -1;for (auto x : af) {int y = val / x;x = (a / x + 1) * x;y = (b / y + 1) * y;if (x <= c && y <= d) {ansx = x;ansy = y;break;}}cout << ansx << ' ' << ansy << '\n';return 1;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;euler_screen(100001);while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}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)\)
【Div. 3 Codeforces Round #828A-F】空间复杂度 \(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;}

经验总结扩展阅读


上一篇：2023年农历八月十二送葬吉日 2023年9月26日适合送葬吗

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