2024ICPC 全国邀请赛（武汉）题解

2024 ICPC National Invitational Collegiate Programming Contest, Wuhan Site

B - Countless Me

Solution

显然，只能执行 $n$ 次操作是没用的条件

我们只需要把和 $s u m$ 分给 $n$ 个数，使得 $n$ 个数的或和最小即可

从高到低考虑每一位，假设此时枚举到第 $i$ 位

如果这一位可以不放 $1$ ，即后面的位能组成 $s u m$ ，则肯定不放

如果这一位要放 $1$ ，考虑放几个 $1$ ，显然，最大值 $m a x = min (n, \frac{s u m}{2^{i}})$

按照贪心的思想，放 $m a x$ 个 $1$ 即可

模拟此过程

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ll sum = 0; ll n = 0; cin >> n;
    ll ans = 0;
    for (int i = 1; i <= n; i++) { ll x; cin >> x; sum += x; }
    for (ll i = 30; i >= 0; i--) {
        if (((1ll << i) - 1) * n >= sum) continue;
        ll num = min(1ll * n, sum / (1ll << i));
        if (num == 0) continue;
        sum -= num * (1ll << i);
        ans |= 1ll <<  i;
    }
    cout << ans << '\n';
    return 0;
}

D - ICPC

Solution

定义 $g [i] [j]$ 表示从 $i$ 点出发，向右移动不超过 $j$ 次的和的最大值

定义 $f [i] [j]$ 表示从 $i$ 点出发，先向左走，然后向右走的最大值，显然只会发生一次调头

不妨设在向左走了 $l$ 步折返，那么 $f [i] [j] = {max}_{l = 0}^{i - 1} {g [i - l] [j - l]}$

显然这个用前缀最大值处理就好了

对于先向右走然后折返的情况，只需要把 $a$ 倒过来处理一次就好了

Code

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void calc(vector<ll> &a, vector<vector<ll> > &dp) {
    int n = a.size() - 1;
    vector<vector<ll> > g(n + 1, vector<ll>(n + 1, 0));
    for (int x = 1; x <= n; x++) {
        g[x][0] = a[x];
        for (int j = 1; j <= n; j++) {
            g[x][j] = g[x][j - 1];
            if (x + j <= n) g[x][j] += a[x + j];
        }
        
    }
    for (int s = 1; s <= n; s++)
        for (int j = 1; j <= 2 * n; j++)  {
            dp[s][j] = max(dp[s][j], max(dp[s - 1][j - 1], g[s][min(j, n)]));
        }
}   


int main() {
    int n; cin >> n;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<vector<ll> > dp(n + 1, vector<ll>(2 * n + 1, 0));
    calc(a, dp);
    reverse(a.begin() + 1, a.end());
    reverse(dp.begin() + 1, dp.end());
    calc(a, dp);
    reverse(dp.begin() + 1, dp.end());
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ll now = 0;
        for (int j = 1; j <= 2 * n; j++) 
            now ^= 1ll * j * dp[i][j];
        ans ^= (now + i);
    }
    cout << ans << '\n';
    return 0;
}

E - Boomerang

Solution

显然，我们先按照 $r$ 为根节点建树，对于每个时刻 $t i m$ ，谣言传播到 $d e p$ 小于等于 $t i m$ 的节点

我们在每个时刻辟谣时，只需要观察直径，从直径的中点开始辟谣

所以我们需要维护每个时刻树的直径

有一个比较显然的结论，我们按深度从小到大加点，设深度为 $x$ 的点在时刻 $x$ 加入，对于一个新加入的点，它肯定时新的直径的一端，另外一端是老直径的一段

所以我们只需要维护直径的两端，对于新加入的点，用 LCA 算出新直径，看是保留那一端

求出每个时刻的直径后，对于每个 $k = i$ ，我们用二分找一个时刻 $t^{'}$ 使得， $k (t^{'} - t 0)$ 能覆盖整个 $k^{'}$ 的直径

当然这里用双指针也是可以的，因为 $k$ 增加时，答案肯定递减

Code

#include <bits/stdc++.h>
using namespace std;

vector<vector<int> > g;
vector<int> dep;
vector<array<int, 20> > fa;

int n, rt, t0;
int max_dep;

void dfs(int u, int f, int dp) {
    max_dep = max(max_dep, dep[u] = dp);
    fa[u][0] = f;
    for (int i = 1; i < 20; i++)
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (auto &v : g[u]) {
        if (v == f) continue;
        dfs(v, u, dp + 1);
    }
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 19; i >= 0; i--)
        if (dep[x] - (1 << i) >= dep[y])
            x = fa[x][i];
    if (x == y) return x;
    for (int i = 19; i >= 0; i--)
        if (fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}

int dis(int x, int y) { return dep[x] + dep[y] - 2 * dep[lca(x, y)]; }

int main() {
    cin >> n;
    g.assign(n + 1, vector<int>());
    dep.resize(n + 1); fa.resize(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cin >> rt >> t0;
    dfs(rt, 0, 0);
    vector<int> id (n + 1);
    for (int i = 1; i <= n; i++) id[i] = i;
    auto cmp = [&](int x, int y) {return dep[x] < dep[y];};
    sort (id.begin() + 1, id.end(), cmp);
    int pos = 2, max_tim = 2 * n;
    vector<int> log_dep (max_tim + 1);
    int d1 = rt, d2 = rt;
    auto insert = [&] (int x) {
        int d1_x = dis(d1, x), d2_x = dis(d2, x);
        if (d1_x > d2_x) { d2 = x; return d1_x; }
        else { d1 = x; return d2_x; }
    };

    for (int i = 1; i <= max_dep; i++) {
        while (pos <= n && dep[id[pos]] == i)
            log_dep[i] = max(log_dep[i], insert(id[pos++]));
    }
    for (int i = max_dep + 1; i <= max_tim; i++)
        log_dep[i] = log_dep[i - 1];
    for (int k = 1; k <= n; k++) {
        auto check = [&] (int t) {
            int l = log_dep[t] / 2 + (log_dep[t] & 1);
            if (1ll * k * (t - t0) >= 1ll * l) return true;
            return false;
        };
        int l = t0 - 1, r = max_tim;
        while (l + 1 < r) {
            int mid = (l + r) >> 1;
            if (check(mid)) r = mid;
            else l = mid;
        }
        cout << r << ' ';
    }
    return 0;
}

F - Custom-Made Clothes

Solution

交互题

我把题转化成求方阵中第 $k$ 小的数 $x$

显然开始时二分答案，二分 $m i d$ ，然后去 check 在 $m i d$ 在方阵中有多少小于等于 $m i d$ 的

显然，小于等于 $m i d$ 的区域肯定是在左上角的某块区域，而有一条折的分界线

我们只需要得到这条分界线就可以得到小于等于 $m i d$ 的个数了

具体假设此时询问， $(x, y)$ 是否小于等于 $m i d$ ，如果返回 $1$ ，则 $y + 1$ ，否则 $x - 1$

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k; cin >> n >> k;
    int l = 0, r = n * n; k = n * n - k + 1;

    auto check = [&](int x) {
        int res = 0;
        int pos_x = n, pos_y = 1;
        while (pos_x >= 1 && pos_y <= n) {
            cout << "? " << pos_x << " " << pos_y << " " << x << endl;
            int rely; cin >> rely;
            if (rely == 1) {
                res += pos_x;
                pos_y++;
            }
            else {
                pos_x--;
            }
        }
        return res;
    };

    while (l + 1 < r) {
        int mid = (l + r) / 2;
        if (check(mid) >= k) r = mid;
        else l = mid;   
    }
    cout << "! " << r << endl;
    return 0;
}

I - Cyclic Apple Strings

Solution

签到题，只需要输出除了 $1$ 的连通块的个数 $- 1$

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s; cin >> s;
    s = " " + s;
    int lst_0 = -1;
    for (int i = 1; i < s.size(); i++) 
        if (s[i] == '0')
            lst_0 = i;
    int ans = 0;
    for (int i = 1; i <= lst_0; i++) 
        if (s[i] == '1' && s[i - 1] != '1') 
            ans += 1;
    cout << ans << endl;
    return 0;
}

K - Party Games

Solution

观察 $\oplus_{i = 1}^{n} i$

当 $i m o d 4 = 1$ 时， $\oplus_{i = 1}^{n} i = 1$ ，显然先手必胜

当 $i m o d 4 = 2$ 时， $\oplus_{i = 1}^{n} i = n + 1$ ，无论先手拿 $1$ 还是 $n$ ，后手拿另外一个，异或和位 $0$ ，先手必败

当 $i m o d 4 = 3$ 时， $\oplus_{i = 1}^{n} i = 0$ ，显然先手必胜

当 $i m o d 4 = 0$ 时， $\oplus_{i = 1}^{n} i = n$ ，先手拿走 $n$ 让异或和为 $0$ ，先手必胜

Code

#include <bits/stdc++.h>
using namespace std;
void solve() {
    int n; cin >> n;
    int x = n % 4;
    if (x == 0 || x == 1) puts("Fluttershy");
    else puts("Pinkie Pie");
}
int main() {
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

M - Merge

Solution

考虑到奇数 + 偶数 = 奇数

也就是说，偶数最多只会被加一次

所以考虑从偶数入手，假设当前最大的偶数是 $x$

那么需要判断是否可以组成 $2 x + 1$ 或者 $2 x - 1$

判断一个数 $v$ 是否可以被组成

如果当前有 $v$ ，则可以直接组成
如果当前无 $v$ 且 $v$ 为奇数，则递归查询 $v / 2$ 和 $v - v / 2$
若当前无 $v$ ，且 $v$ 为偶数，则不能得到 $v$

Code

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
map<ll, int> mp;

stack<ll> need;

bool check(ll x) { //验证 x 是否能组成
    bool flg = 0;
    if (mp.count(x) && mp[x] > 0) {
        mp[x] -= 1;
        need.push(x);
        return 1;
    }
    else if (x & 1) {
        if (check(x / 2) && check(x - x / 2)) {
            return 1;
        }
    }
    return 0;
}

int main() {
    freopen ("M.in", "r", stdin);
    freopen ("M.out", "w", stdout); 
    int n; cin >> n;
    vector<ll> a(n + 1, 0);
    vector<ll> ans;
    priority_queue<ll> pq_odd, pq_even;
    for (int i = 1; i <= n; i++) {
        cin >> a[i], mp[a[i]] += 1;
        if (a[i] % 2 == 1) pq_odd.push(a[i]);
        else pq_even.push(a[i]);
    }

    while (!pq_even.empty()) {
        ll x = pq_even.top(); pq_even.pop(); if (mp[x] <= 0) continue;

        while (!pq_odd.empty() && pq_odd.top() > x + 1) {
            if (mp[pq_odd.top()] > 0) {
                mp[pq_odd.top()]--;
                ans.push_back(pq_odd.top());
                continue;
            }
            pq_odd.pop();
        }

        if (check(2 * x + 1)) {
            mp[x * 2 + 1] += 1;
            while (!need.empty())
                need.pop();
            pq_odd.push(x * 2 + 1);
        }
        else {
            while (!need.empty()) {
                mp[need.top()] += 1;
                need.pop();
            }
            if (check(2 * x - 1)) {
                while (!need.empty())
                    need.pop();
                mp[x * 2 - 1] += 1;
                pq_odd.push(x * 2 - 1);
            }
            else {
                while (!need.empty()) {
                    mp[need.top()] += 1;
                    need.pop();
                }
                mp[x] -= 1;
                ans.push_back(x);
            }
        }
        
    }

    while (!pq_odd.empty()) {
        if (mp[pq_odd.top()] <= 0) {
            pq_odd.pop();
            continue;
        }
        ans.push_back(pq_odd.top());
        mp[pq_odd.top()] -= 1;
        pq_odd.pop();
    }

    cout << ans.size() << endl;
    sort (ans.begin(), ans.end(), greater<ll>());
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << " \n"[i == ans.size() - 1];
    return 0;
}