2024 ICPC 网络赛 第一场

The 2024 ICPC Asia East Continent Online Contest (I)

赛时榜单

Problems	AC
A. World Cup	○
B. Graph
C. Permutation Counting 4	⊕
D. Protection War
E. Random Dungeon
F. Make Max	○
G. The Median of the Median of the Median	○
H. Rainbow Bracket Sequence
I. Boxes
J. Rivals
K. AC Automation Chicken
L. Bull Farm	⊕
M. Find the Easiest Problem	○

M 签到

赛时脑瘫 + 没仔细读题。脑残把队伍名的 team 去掉了，实际上不一定以 team 开头，怒吃一发罚时。

void solve() {
    int n = read();
    std::set<std::string> st[26];
    for (int i = 1; i <= n; i++) {
        std::string s, sta;
        char t;
        cin >> s >> t >> sta;
        bool f = (sta == "accepted");
        if (f == 0) continue;
        st[t - 'A'].insert(s);
    }

    int res = 0;
    for (int i = 0; i < 26; i++) {
        if (st[i].size() > st[res].size()) res = i;
    }

    cout << char(res + 'A') << '\n';
}

F 单调栈

赛时第一反应竟然都不是单调栈而是 set / 链表。小齐直接化身指针仙人。如果用单调栈写的话应该能少不少罚时吧。

void solve() {
    int n = read();

    vector<int> a(n + 2);
    a[0] = a[n + 1] = 2e9;
    for (int i = 1; i <= n; i++) a[i] = read();

    i64 ans = 0;

    vector<int> stk {0};
    for (int i = 1; i <= n; i++) {
        while (!stk.empty() and 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() and a[stk.back()] < a[i]) {
            stk.pop_back();
        }
        if (a[stk.back()] != a[i]) ans += stk.back() - i - 1;
        stk.push_back(i);
    }

    cout << ans << '\n';
}

A 签到

赛时秒了，分别考虑作为 $A1$ 或者 $A2$ 出线，然后算下需要多少个队伍小于他就行了

void solve() {
    int a[32];
    for (int i = 0; i < 32; i++) {
        a[i] = read();
    }
    int cnt = 0;
    for (int i = 1; i < 32; i++) {
        if (a[i] < a[0]) {
            cnt++;
        }
    }

    int ans = 32;
    if (cnt >= 31) ans = 1;
    else if (cnt >= 27) ans = 2;
    else if (cnt >= 13) ans = 4;
    else if (cnt >= 6) ans = 8;
    else if (cnt >= 2) ans = 16;
    cout << ans << '\n';
}

C 思维 / 线性代数

很申必的一个题

解法一

赛后卧龙的做法，感觉很思维。

你考虑构造一些双射，让他们抵消掉。因为如果两个区间是一样的，那么他们可以交换，那么就是 $0$。所以就把区间之间的包含关系搞掉，拆开来，然后看是否有一样的区间。

比如有 $5$ 个区间分别是 $[1, 5], [1, 4], [4, 5], [5, 5], [1, 2]$。

你把 $[1, 5], [1, 4], [1, 2]$ 拆成 $[1, 2], [3, 4], [5, 5]$。然后和已有的 $[5, 5]$ 撞了，所以就是 $0$。

void solve() {
    int n = read();

    vector<vector<int>> vec(n + 1);
    for (int i = 1; i <= n; i++) {
        int L = read(), R = read();
        vec[L].eb(R);
    }

    for (int i = 1; i <= n; i++) {
        auto &a = vec[i];
        if (a.empty()) { puts("0"); return; }
        std::sort(a.begin(), a.end());

        int siz = a.size();
        for (int j = 0; j + 1 < siz; j++) {
            if (a[j] == a[j + 1]) { puts("0"); return; }
            vec[a[j] + 1].eb(a[j + 1]);
        }
    }

    puts("1");
}

解法二 行列式

待更。

G 中位数 trick

唐完了，最后十几分钟我突然会了，直接上机 rush。不知道为什么调不对。赛后仔细想了一下发现 check 区间和得要 $>= 1$ 而不是 $>= 0$。因为偶数的时候最坏其实是 $(+1) + (+1) = 2$。

void solve() {
    int n = read();

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) a[i] = read();

    vector<vector<int>> b(n + 1, vector<int>(n + 1));

    for (int i = 1; i <= n; i++) {
        std::priority_queue<int> G, L;
        for (int j = i; j <= n; j++) {
            
            if (G.empty() or a[j] <= G.top()) {
                G.push(a[j]);
            } else {
                L.push(-a[j]);
            }

            if (G.size() > (j - i + 2) / 2) {
                L.push(-G.top());
                G.pop();
            } else if (G.size() < (j - i + 2) / 2) {
                G.push(-L.top());
                L.pop();
            }

            b[i][j] = G.top();
        }
    }

    auto judge = [&](int lim) {
        vector<vector<int>> c(n + 2, vector<int>(n + 2));

        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                int k = 1;
                if (b[i][j] < lim) k = -1;

                c[1][j] += k;
                c[i + 1][j] -= k;
            }
        }
        int res = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                c[i][j] += c[i - 1][j] + c[i][j - 1] - c[i - 1][j - 1];

                if (i > j) continue;

                if (c[i][j] >= 1) res++;
                else res--;
            }
        }
        return res >= 1;
    };

    int res = 0;
    for (int L = 1, R = 1e9; L <= R; ) {
        int mid = L + R >> 1;
        if (judge(mid)) res = mid, L = mid + 1;
        else R = mid - 1;
    }
    cout << res;
}

L bitset

首先可以将询问离线，按 $c$ 排序，依次加边。

一个序列合法只能是一个没有重复的排列或者只有一个数出现了两次。

考虑空位的移动，每个询问等价于空格能否从 $a$ 移动到 $b$。

如果是一个排列，那么对于每个 $i$，如果空格在 $i$，空格就能移动到 $p_i$。

如果是一个数出现了两次的情况，设 $p_x = p_y$，那么空格只能从 $x$ 或 $y$ 移动到那个没出现的位置。

用 $bitset$ 维护可达性即可。

最多 $O(n^2)$ 条边。加一条边的复杂度是 $O(\frac{n^2}{\omega})$。

但是实际跑不到那么多，因为在加边的时候有记忆化。

void solve() {
    int n = read(), l = read(), q = read();

    vector g(n + 1, std::bitset<2005>());
    for (int i = 1; i <= n; i++) g[i][i] = 1;

    vector t(l + 1, vector<int>(n + 1));
    for (int i = 1; i <= l; i++) {
        for (int j = 1; j <= n; j++) {
            t[i][j] = input();
        }
    }

    vector<int> ans(q);
    vector qry(l + 1, vector<std::array<int, 3>>());
    for (int i = 0; i < q; i++) {
        int a = input(), b = input(), c = input();
        qry[c].pb({a, b, i});
    }

    auto add = [&](int a, int b) {
        if (g[a][b]) return;

        for (int i = 1; i <= n; i++) {
            if (g[i][a]) {
                g[i] |= g[b];
            }
        }
    };

    auto go = [&](const auto &p) {
        vector<int> buk(n + 1);
        int f = 0;
        for (int i = 1; i <= n; i++) {
            if (!buk[p[i]]) buk[p[i]] = 1;
            else if (f) return;
            else f = p[i];
        }

        if (!f) {
            for (int i = 1; i <= n; i++) {
                add(i, p[i]);
            }
        } else {
            int x = 0;
            for (int i = 1; i <= n; i++) {
                if (!buk[i]) x = i;
            }

            for (int i = 1; i <= n; i++) {
                if (p[i] == f) {
                    add(i, x);
                }
            }
        }
    };

    for (int i = 0; i <= l; i++) {
        go(t[i]); 

        for (auto [a, b, idx] : qry[i]) {
            ans[idx] = g[a][b];
        }
    }

    for (int x : ans) cout << x;
    puts("");
}