2024ICPC网络赛第一场

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

#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);
	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];
	for (int j = 1; j <= n; j++)
		for (int i = j - 1; i >= 1; i--) c[i][j] += c[i + 1][j];
	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;
	return 2 * sumc > n * (n + 1) / 2;
}

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

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