vp链接：https://qoj.ac/contest/1794
A. World Cup
最终答案与中国队能力值的排名有关，具体每个情况手推一下，用 if else 即可通过。
#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(false); cin.tie(0);int t, a[40];cin >> t;while (t--) {int num = 0;for (int i = 0; i < 32; i++) {cin >> a[i];if (a[i] <= a[0]) num++;}if (num == 32) puts("1");else if (num >= 28) puts("2");else if (num >= 14) puts("4");else if (num >= 7) puts("8");else if (num >= 3) puts("16");else puts("32");}return 0;
}F. Make Max
每一个数都能更新左右比它小的数，直到遇到一个大于等于它的数为止。从小到大一个个更新，更新次数一定最多，但在计算结果的时候只需要计算数量，不用考虑计算顺序。
利用单调栈求出每一个 左边第一个大于等于它的数的位置
和右边第一个大于等于它的数的位置
。
计算结果的时候要注意，如果 ，即
与左边第一个大于等于它的数相等的时候，只需要记右边小于它的数的个数，不然会跟前面的算重；其余情况都要加上左右小于它的数的个数。
#include <bits/stdc++.h>
using namespace std;const int N = 2e5 + 10;
int n, a[N], lef[N], rig[N];
stack<int> s;inline int read() {int x = 0, f = 1; char c = getchar();while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f;
}int main () {int t = read();while (t--) {n = read();for (int i = 1; i <= n; i++) a[i] = read();for (int i = 1; i <= n; i++) {if (s.empty() || a[i] < a[s.top()]) s.push(i);else {while (!s.empty() && a[i] >= a[s.top()]) {rig[s.top()] = i;s.pop();}s.push(i);}}while (!s.empty()) rig[s.top()] = n + 1, s.pop();for (int i = n; i; i--) {if (s.empty() || a[i] < a[s.top()]) s.push(i);else {while (!s.empty() && a[i] >= a[s.top()]) {lef[s.top()] = i;s.pop();}s.push(i);}}while (!s.empty()) lef[s.top()] = 0, s.pop();long long ans = 0LL;for (int i = 1; i <= n; i++) {if (!lef[i] || a[lef[i]] != a[i]) ans += rig[i] - lef[i] - 2;else ans += rig[i] - i - 1;}printf("%lld\n", ans);}return 0;
}G. The Median of the Median of the Median
总体思路：先二分最终的中位数，再判断实际中位数是否大于等于二分的中位数
利用 suma 数组记录 a[i] 大于等于二分的中位数 x 的数量的前缀和。
记录 a 数组该区间内的中位数是否大于等于 x（如果 a 数组该区间内的中位数是大于等于 x的，那么至少有一半，即
个 a 要大于等于 x）。
同样记录对应区间内的中位数是否大于等于 x 且原理与 b 相同。
最后判断 c 数组中是否有超过一半的数是大于等于二分的中位数的。
c 数组的前缀和处理（根据样例 1 举例说明）：1 3 1 7
| b | 1 | 2 | 3 | 4 |
| 1 | 1 | 1 | 1 | 1 |
| 2 | 3 | 1 | 3 | |
| 3 | 1 | 1 | ||
| 4 | 7 |
| c | 1 | 2 | 3 | 4 |
| 1 | 1 | 1 | 1 | 1 |
| 2 | 3 | 1 | 1 | |
| 3 | 1 | 1 | ||
| 4 | 7 |
以上是按照定义，b，c 数组对应区间内的中位数，两个数组存有数据的部分都类似于一个倒三角形。
可以发现原定义的 是
这个倒三角区域内所有的数中位数，这个倒三角正好是以 （i，j）为右上角的倒三角。所以代码中 c 数组的每一个
记录的是：在原定义的 b 数组中，以（i，j）为右上角的倒三角区域内，大于等于二分的中位数x的数量。
#include <bits/stdc++.h>
using namespace std;const int N = 2010;
int n, suma[N], a[N], b[N][N], c[N][N];inline int read() {int x = 0, f = 1; char c = getchar();while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f;
}bool check(int x) {for (int i = 1; i <= n; i++) suma[i] = suma[i - 1] + (a[i] >= x);// 记录大于等于 x 的 a[i] 的数量for (int i = 1; i <= n; i++)for (int j = i; j <= n; j++)c[i][j] = b[i][j] = (2 * (suma[j] - suma[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];// 统计 b 数组倒三角左边区域大于等于 x 的数量for (int j = 1; j <= n; j++)for (int i = j - 1; i >= 1; i--) c[i][j] += c[i + 1][j];// 统计 b 数组倒三角下面区域大于等于 x 的数量int sumc = 0;for (int i = 1; i <= n; i++)for (int j = i; j <= n; j++)sumc += (2 * c[i][j]) > (j - i + 1) * (j - i + 2) / 2;// (j - i + 1) * (j - i + 2) / 2 是对应区间内 b 数量的一半return 2 * sumc > n * (n + 1) / 2; // n * (n + 1) / 2 就是 c 数量的一半
}int main() {n = read();for (int i = 1; i <= n; i++) a[i] = read();int l = 0, r = 1e9 + 1;while (l <= r) {int mid = l + r >> 1;if (check(mid)) l = mid;else r = mid;} // 二分中位数printf("%d\n", l);return 0;
}M. Find The Easiest Problem
用 set 记录每一个题目通过的队伍的名字，最后比较队伍数量。
#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(false); cin.tie(0);int t, n;string team, status;char prob;cin >> t;while (t--) {cin >> n;set<string> st[30];for (int i = 1; i <= n; i++) {cin >> team >> prob >> status;if (status == "accepted") st[prob - 'A'].insert(team);}int idx = 0;for (int i = 1; i <= 'Z' - 'A'; i++) {if (st[idx].size() < st[i].size()) idx = i;}printf("%c\n", 'A' + idx);}return 0;
}