2024ICPC上海-做题&补题记录

VP5题743罚时，银了

挺牢的，五题全是思维题，学了一堆算法一点用不上。

---

C - Conquer the Multiples

简单博弈论。

首先判断 $r$ 和 $2l$ 的大小，若 $2l > r$ ，则只能老老实实按顺序取，奇偶定胜负。否则，判断 $l$ 的奇偶性。若 $l$ 为偶，其倍数也是偶数，取其倍数是提前透支，即无效，故先手必然取 $l$ ，转为初始值为 $l+1$ （奇数）时先手的情况。若 $l$ 为奇，其倍数是偶数，取其倍数会提前取掉对手的未来的一次选项，则先手必胜。

#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

void solve() {
    i64 l, r;
    cin >> l >> r;
    if (r < 2 * l) {
        cout << ((r - l + 1) % 2 == 0 ? "Bob" : "Alice") << "\n";
        return;
    }
    if (l % 2 == 0) {
        if (2 * l + 2 > r) cout << ((r - l) % 2 != 0 ? "Bob" : "Alice") << "\n";
        else cout << "Bob\n";
    }
    else cout << "Alice\n";
}

signed main() {
    
    FIO;
    TESTS {
        solve();
    }

    return 0;
}

I - In Search of the Ultimate Artifact

每次选k个乘起来，则每次选最大的k个更优，则一直做范围内合并，直到某次合并时遇到0停止。

记得初值也要取模。白白WA了一发。

#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 1
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    for (int i = 0; i < n; ++i) cin >> p[i];
    ranges::sort(p, greater<int>());
    i64 res = p[0] % MOD;
    for (int l = 1, r = k - 1; r < n; l = r + 1, r += k - 1) {
        int ok = 1;
        for (int i = l; i <= r; ++i) {
            if (!p[i]) {
                ok = 0;
                break;
            }
        }
        if (!ok) break;
        for (int i = l; i <= r; ++i) {
            res = res * p[i] % MOD;
        }
    }
    cout << res << "\n";
}

signed main() {
    
    FIO;
    TESTS {
        solve();
    }

    return 0;
}

B - Basic Graph Algorithm

按照题意，显式维护dfs时的操作栈，当且仅当当前点与下个目标点不相邻，且当前点还有未遍历的邻居点时建边。

#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 3e5 + 10;
constexpr int MOD = 998244353;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<set<int>> e(n + 1);
    vector<int> d(n + 1), stk(n + 1), p(n + 1);
    int top = 0;
    for (int i = 0, u, v; i < m; ++i) {
        cin >> u >> v;
        e[u].insert(v);
        e[v].insert(u);
    }
    for (int i = 1; i <= n; ++i) cin >> p[i];
    for (int i = 1; i <= n; ++i) d[i] = e[i].size();
    stk[++top] = p[1];
    for (int v : e[p[1]]) d[v]--;
    vector<tuple<int, int>> ans;
    ans.reserve(n);
    for (int i = 2; i <= n; ++i) {
        while (top && d[stk[top]] == 0) {
            top--;
        }
        if (!top) {
            stk[++top] = p[i];
            for (int v : e[p[i]]) d[v]--;
            continue;
        }
        if (!e[stk[top]].contains(p[i])) {
            ans.push_back({stk[top], p[i]});   
        }
        for (int v : e[p[i]]) d[v]--;
        stk[++top] = p[i];
    }
    cout << ans.size() << "\n";
    for (auto [x, y] : ans) cout << x << " " << y << "\n";
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

G - Geometry Task

中位数没有什么好性质，考虑二分答案。根据答案值反向计算取到此答案需要的x值，分类讨论斜率为正、为负，特判为零情况。斜率负时自变量越小越容易取到大值，斜率正时自变量越大越容易取到大值，贪心一下，用双指针维护，统计能够取到答案值的点对数，$cnt \ge (n+1)/2$ 则合法。

#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 1e5 + 10;
constexpr int MOD = 998244353;

void solve() {
    int n;
    cin >> n;
    vector<i64> a(n), b(n), c(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];
    for (int i = 0; i < n; ++i) cin >> c[i];
    ranges::sort(c);
    auto check = [&](i64 y) -> bool {
        vector<i64> pos, neg;
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (!a[i]) {
                cnt += b[i] >= y;
                continue;
            }
            i64 x = (y - b[i]) / a[i];
            if (a[i] > 0) {
                x += a[i] * x + b[i] < y;
                pos.push_back(x);
            } else {
                x -= a[i] * x + b[i] < y;
                neg.push_back(x);
            }
        }
        ranges::sort(pos);
        ranges::sort(neg);
        int p1 = 0;
        for (int p2 = 0; p1 < n && p2 < neg.size(); ++p1) {
            while (p2 < neg.size() && neg[p2] < c[p1]) ++p2;
            if (p2 < neg.size()) {
                cnt++;
                p2++;
            }
        }
        for (int p2 = 0; p2 < pos.size(); ++p2) {
            while (p1 < n && c[p1] < pos[p2]) ++p1;
            if (p1 < n) {
                cnt++;
                p1++;
            }
        }
        return cnt >= (n + 1) / 2;
    };
    i64 lo = -2e18, hi = 2e18;
    while (lo < hi) {
        i64 mid = lo + hi + 1 >> 1;
        if (check(mid)) lo = mid;
        else hi = mid - 1;
    }
    cout << lo << "\n";
}

signed main() {
    
    FIO;
    TESTS {
        solve();
    }

    return 0;
}

D - Decrease and Swap

大力分讨。

末尾00必合法，分类讨论末尾01和1x情况。

#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> pre(n);
    pre[0] = s[0] - '0';
    for (int i = 1; i < n; ++i) {
        if (s[i] == '1') pre[i] = pre[i - 1] + 1;
        else pre[i] = max(0, pre[i - 1] - 1);
    }
    if (s[n - 2] == '0' && s[n - 1] == '0') {
        cout << "Yes\n";
        return;
    }
    if (n == 3) {
        cout << "No\n";
        return;
    }
    int ok = 0;
    if (s[n - 2] == '0' && s[n - 1] == '1') {
        ok = (pre[n - 3] >= 2 || n >= 5 && (pre[n - 4] >= 2 || pre[n - 3] >= 1 && pre[n - 5] >= 1));
    } else {
        ok = (pre[n - 4] >= 1 || n >= 5 && pre[n - 5] >= 1 && pre[n - 3] >= 1);
    }
    cout << (ok ? "Yes\n" : "No\n");
}

signed main() {
    
    FIO;
    TESTS {
        solve();
    }

    return 0;
}