Martian148's blog
martian148
2024-08-04
目录

ICPC2024 武汉邀请赛

# ICPC2024 武汉邀请赛

2024 ICPC National Invitational Collegiate Programming Contest, Wuhan Site (opens new window)

# B - Countless Me

# Solution

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

我们只需要把和 sumsum 分给 nn 个数，使得 nn 个数的或和最小即可

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

如果这一位可以不放 11，即后面的位能组成 sumsum，则肯定不放

如果这一位要放 11，考虑放几个 11，显然，最大值 max=min⁡(n,sum2i)max=\min(n,\frac{sum}{2^i})

按照贪心的思想，放 maxmax 个 11 即可

模拟此过程

# 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# D - ICPC

# Solution

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

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

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

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

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

# 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

# E - Boomerang

# Solution

显然，我们先按照 rr 为根节点建树，对于每个时刻 timtim，谣言传播到 depdep 小于等于 timtim 的节点

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

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

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

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

求出每个时刻的直径后，对于每个 k=ik=i，我们用二分找一个时刻 t′t' 使得，k(t′−t0)k(t'-t0) 能覆盖整个 k′k' 的直径

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

# 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() {
    // freopen ("E.in", "r", stdin);
    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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

# F - Custom-Made Clothes

# Solution

交互题

我把题转化成求方阵中第 kk 小的数 xx

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

image.png

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

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

具体假设此时询问，(x,y)(x,y) 是否小于等于 midmid，如果返回 11，则 y+1y+1，否则 x−1x-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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# I - Cyclic Apple Strings

# Solution

签到题，只需要输出除了 11 的连通块的个数 −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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# K - Party Games

# Solution

观察 ⊕i=1ni\oplus_{i=1}^n i

当 imod4=1i\ mod\ 4 = 1 时，⊕i=1ni=1\oplus_{i=1}^n i=1 ，显然先手必胜

当 imod4=2i\ mod\ 4 = 2 时，⊕i=1ni=n+1\oplus_{i=1}^n i=n+1 ，无论先手拿 11 还是 nn，后手拿另外一个，异或和位 00，先手必败

当 imod4=3i\ mod\ 4 = 3 时，⊕i=1ni=0\oplus_{i=1}^n i=0 ，显然先手必胜

当 imod4=0i\ mod\ 4 = 0 时，⊕i=1ni=n\oplus_{i=1}^n i=n ，先手拿走 nn 让异或和为 00，先手必胜

# 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# M - Merge

# Solution

考虑到奇数 + 偶数 = 奇数

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

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

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

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

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

# 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
上次更新: 2024/10/30, 18:42:16
ICPC2023 合肥区域赛
ICPC2024 江西省赛

← ICPC2024 江西省赛→

最近更新
01
逻辑学
12-13
02
中华传统文化
12-12
03
欧拉回路
11-14
更多文章>
Theme by Vdoing | Copyright © 2024-2024 Martian148 | MIT License