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