ICPC 2024 网络赛(I)

M. Find the Easiest Problem

题目大意

给定所有的提交记录，找到通过队伍最多且字典序最小的题目。

解题思路

按题意模拟即可

代码实现

#include <bits/stdc++.h>using i64 = long long;int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);int tt;std::cin >> tt;while (tt--) {int n;std::cin >> n;std::map<std::string, std::set<std::string>> mp;for (int i = 0; i < n; i++) {std::string s1, s2, s3;std::cin >> s1 >> s2 >> s3;if (s3 == "accepted") {mp[s2].insert(s1);}}std::string ans;for (auto [x, y] : mp) {if (ans.empty() || y.size() > mp[ans].size() || y.size() == mp[ans].size() && x < ans) {ans = x;}}std::cout << ans << "\n";}
}

A. World Cup

题目大意

给定所有队伍的能力值，问题目规定的赛制下第一支队伍能取得的最好名次是多少

解题思路

根据赛制暴力打表即可

代码实现

#include <bits/stdc++.h>using i64 = long long;int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);int tt;std::cin >> tt;while (tt--) {int cnt = 0;std::vector<int> a(32);for (int i = 0; i < 23; i++) {std::cin >> a[i];if (a[i] <= a[0]) {cnt++;}}if (cnt == 32) {std::cout << 1 << "\n";} else if (cnt >= 28) {std::cout << 2 << "\n";} else if (cnt >= 14) {std::cout << 4 << "\n";} else if (cnt >= 7) {std::cout << 8 << "\n";} else if (cnt >= 3) {std::cout << 16 << "\n";} else {std::cout << 32 << "\n";}}
}

F. Make Max

题目大意

给定一个数组，每次可以选择一个子数组让这个子数组的所有元素变成子数组中的最大值，每次操作必须要让数组产生变化，问最多能操作多少次

解题思路

单调栈维护每个位置左右两侧第一个大于等于这个数的位置，特判一下相等的时候

代码实现

#include <bits/stdc++.h>using i64 = long long;int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);int tt;std::cin >> tt;while (tt--) {i64 n, ans = 0;std::cin >> n;std::vector<i64> a(n + 2, INT_MAX), stk = {0};for (int i = 1; i <= n; i++) {std::cin >> a[i];}for (int i = 1; i <= n; i++) {while (!stk.empty() && a[stk.back()] < a[i]) {stk.pop_back();}ans += i - stk.back() - 1;stk.push_back(i);}stk = {n + 1};for (int i = n; i >= 1; i--) {while (!stk.empty() && a[stk.back()] < a[i]) {stk.pop_back();}if (a[stk.back()] != a[i]) {ans += stk.back() - i - 1;}stk.push_back(i);}std::cout << ans << "\n";}
}

G. The Median of the Median of the Median

题目大意

给定一个数组a，设a的所有子数组的中位数为b，设b的所有子数组的中位数为c，求c的中位数

解题思路

二分答案，先用一维前缀和来维护b，再如法炮制，用二维前缀和压缩b来维护c

代码实现

#include <bits/stdc++.h>using i64 = long long;int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);int n;std::cin >> n;std::vector<int> a(n + 1);for (int i = 1; i <= n; i++) {std::cin >> a[i];}auto check = [&](int x) -> bool {std::vector<int> pre(n + 1);for (int i = 1; i <= n; i++) {pre[i] = pre[i - 1] + (a[i] >= x);}std::vector<std::vector<int>> b(n + 1, std::vector<int>(n + 1)), c(n + 1, std::vector<int>(n + 1));for (int i = 1; i <= n; i++) {for (int j = i; j <= n; j++) {c[i][j] = b[i][j] = 2 * (pre[j] - pre[i - 1]) > j - i + 1;}}for (int i = 1; i <= n; i++) {for (int j = i + 1; j <= n; j++) {c[i][j] += c[i][j - 1];}}for (int j = 1; j <= n; j++) {for (int i = j - 1; i >= 1; i--) {c[i][j] += c[i + 1][j];}}int cnt = 0;for (int i = 1; i <= n; i++) {for (int j = i; j <= n; j++) {cnt += 2 * c[i][j] > (j - i + 1) * (j - i + 2) / 2;}}return 2 * cnt > n * (n + 1) / 2;};int l = 1, r = 1e9, ans = -1;while (l <= r) {int mid = (l + r) / 2;if (check(mid)) {ans = mid;l = mid + 1;} else {r = mid - 1;}}std::cout << ans << "\n";
}

C. Permutation Counting 4

题目大意

给定n个范围区间[l, r]，问对于长度为n的全排列，有多少个排列满足$l_i\le p_i\le r_i$，答案对2取模

解题思路

相当于构造一个 $n\times n$ 的01矩阵 $A$（第i行第j列表示能否把位置i设为数字j）
$$A_{i,j}=\{\begin{array}{ll}1,& j\in [l_i,r_i]\\ 0,& j\notin [l_i,r_i]\end{array}$$
求perm(A)，在模2意义下等价于求det(A)，只需要看是否线性无关即可，问题等价于l-1和r连边，最后是不是一棵树，并查集判断即可

代码实现

#include <bits/stdc++.h>using i64 = long long;class DSU {public:int cnt;std::vector<int> fa, rank, siz;DSU(int n) : cnt(n), fa(n + 1), rank(n + 1), siz(n + 1, 1) {for (int i = 1; i <= n; i++) {fa[i] = i;}}int find(int x) {if (fa[x] != x) {fa[x] = find(fa[x]);}return fa[x];}void merge(int x, int y) {int X = find(x), Y = find(y);if (X != Y) {if (rank[X] >= rank[Y]) {fa[Y] = X;siz[X] += siz[Y];if (rank[X] == rank[Y]) {rank[X]++;}} else {fa[X] = Y;siz[Y] += siz[X];}cnt--;}}int size() {return cnt;}int count(int x) {return siz[find(x)];}
};int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);int tt;std::cin >> tt;while (tt--) {int n, f = 1;std::cin >> n;DSU dsu(n);for (int i = 0; i < n; i++) {int u, v;std::cin >> u >> v;if (dsu.find(u - 1) == dsu.find(v)) {f = 0;} else {dsu.merge(u - 1, v);}}std::cout << f << "\n";}
}