ABC392题解

A

算法标签: 模拟

在这里插入图片描述

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int w[3];for (int i = 0; i < 3; ++i) cin >> w[i];sort(w, w + 3);if (w[0] * w[1] == w[2]) cout << "Yes" << "\n";else cout << "No";return 0;
}

B

算法标签: 哈希表

在这里插入图片描述

#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_set>
#include <vector>using namespace std;const int N = 1010;int range, n, w[N];int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);unordered_set<int> s;cin >> range >> n;for (int i = 0; i < n; ++i) {int val;cin >> val;s.insert(val);}vector<int> res;for (int i = 1; i <= range; ++i) {if (!s.count(i)) res.push_back(i);}cout << res.size() << "\n";for (int val : res) cout << val << " ";cout << "\n";return 0;
}

C

算法标签: 模拟

在这里插入图片描述

#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_set>
#include <vector>using namespace std;const int N = 3e5 + 10;int n;
int p[N], q[N];
int pos[N];int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n;for (int i = 1; i <= n; ++i) cin >> p[i];for (int i = 1; i <= n; ++i) {cin >> q[i];pos[q[i]] = i;}for (int i = 1; i <= n; ++i) {int per = pos[i];int see = p[per];cout << q[see] << " ";}cout << "\n";return 0;
}

D

算法标签: 桶计数, 模拟

在这里插入图片描述

*精度不够的错误案例

而且没说两个骰子只有一个点数相等, 下面做法有遗漏情况

#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_set>
#include <vector>using namespace std;const int N = 110, M = 1e5 + 10;
const double EPS = 1e-20;int n;
int cnt[N];
// 记录每个骰子 每个数字出现的概率
double w[N][M];int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n;for (int i = 1; i <= n; ++i) {cin >> cnt[i];for (int j = 1; j <= cnt[i]; ++j) {int val;cin >> val;w[i][val] += 1.0 / cnt[i];}}// 枚举点数double res = 0;for (int i = 1; i < M; ++i) {vector<double> nums;for (int j = 1; j <= n; ++j) {if (w[j][i] > EPS) nums.push_back(w[j][i]);}sort(nums.begin(), nums.end(), greater<double>());if (nums.size() < 2) continue;double tmp = nums[0] * nums[1];res = max(res, tmp);}printf("%lf\n", res);return 0;
}

正确解法

#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_set>
#include <vector>using namespace std;typedef long double LD;
const int N = 110, M = 1e5 + 10;
const double EPS = 1e-20;int n;
int cnt[N];
int w[N][M];int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n;for (int i = 1; i <= n; ++i) {cin >> cnt[i];for (int j = 1; j <= cnt[i]; ++j) {int val;cin >> val;w[i][val]++;}}LD res = 0;for (int i = 1; i < n; ++i) {for (int j = i + 1; j <= n; ++j) {LD curr = 0;for (int k = 1; k < M; ++k) {curr +=( (LD) w[i][k] / cnt[i]) * ((LD) w[j][k] / cnt[j]);}res = max(res, curr);}}printf("%.15Lf\n", res);return 0;
}

E

算法标签: $D S U$ , 并查集

在这里插入图片描述

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>using namespace std;typedef pair<int, int> PII;
const int N = 2e5 + 10, M = 4e5 + 10;int n, m;
int p[N];
int vers[M];
bool vis[M];int find(int u) {if (p[u] != u) p[u] = find(p[u]);return p[u];
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> m;for (int i = 1; i <= n; ++i) p[i] = i;for (int i = 1; i <= m; ++i) {int u, v;cin >> u >> v;int fa1 = find(u);int fa2 = find(v);if (fa1 != fa2) p[fa2] = fa1;else {vis[i] = true;vers[i] = u;}}int res = 0;for (int i = 1; i <= n; ++i) {if (p[i] == i) res++;}cout << res - 1 << "\n";int k = 1;for (int i = 1; i <= n; ++i) {if (!vis[i]) continue;while (k <= n && find(k) == find(vers[i])) k++;if (k > n) break;int fa1 = find(k);int fa2 = find(vers[i]);p[fa1] = fa2;cout << i << " " << vers[i] << " " << k << "\n";}return 0;
}

F

算法标签: 树状数组, $F e n w i c k - T ree$ , $BST$

在这里插入图片描述

思路

如果正着做, 插入不好操作, 平衡树操作, 如果倒着做, 插入第 $n$ 个数, 所在位置 $p_{n - 1}$ , 初始化树状数组每个位置 $1$ , 如果这个位置被占用将其改为 $0$ , 寻找从左往右的第 $p_{n - 1}$ 个空格, 也就是找 $p_{n - 1}$ 就是找前缀和等于 $p_{n - 1}$ 的位置, 时间复杂度 $O(n\log ^ 2n)$

树状数组写法

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 5e5 + 10;int n, w[N];
int tr[N], res[N];int lowbit(int val) {return val & -val;
}void add(int u, int val) {for (int i = u; i <= n; i += lowbit(i)) tr[i] += val;
}int query(int u) {int res = 0;for (int i = u; i; i -= lowbit(i)) res += tr[i];return res;
}int find(int val) {int l = 1, r = n;while (l < r) {int mid = l + r >> 1;if (query(mid) >= val) r = mid;else l = mid + 1;}return l;
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n;for (int i = 1; i <= n; ++i) cin >> w[i];for (int i = 1; i <= n; ++i) add(i, 1);for (int i = n; i >= 1; --i) {int pos = find(w[i]);res[pos] = i;add(pos, -1);}for (int i = 1; i <= n; ++i) cout << res[i] << " ";cout << "\n";return 0;
}

线段树写法

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 5e5 + 10;int n, w[N];
struct Node {int l, r;int sum;
} tr[N << 2];
int res[N];void push_up(int u) {tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}void build(int u, int l, int r) {if (l == r) {tr[u] = {l, r, 1};return;}tr[u] = {l, r};int mid = l + r >> 1;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);push_up(u);
}void update(int u, int pos, int val) {if (tr[u].l == tr[u].r) {tr[u].sum += val;return;}int mid = tr[u].l + tr[u].r >> 1;if (pos <= mid) update(u << 1, pos, val);if (pos > mid) update(u << 1 | 1, pos, val);push_up(u);
}// 查询和为val的起始位置
int query(int u, int k) {if (tr[u].l == tr[u].r) return tr[u].l;if (tr[u << 1].sum < k) return query(u << 1 | 1, k - tr[u << 1].sum);else return query(u << 1, k);
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n;for (int i = 1; i <= n; ++i) cin >> w[i];build(1, 1, n);for (int i = n; i >= 1; --i) {// 找到第w[i]个未被赋值的位置int pos = query(1, w[i]);res[pos] = i;update(1, pos, -1);}for (int i = 1; i <= n; ++i) cout << res[i] << " ";cout << "\n";return 0;
}