「题解」2024 ICPC 网络赛第二场

好困，写几个签到吧。

A. Gambling on Choosing Regionals

给定 $k$ 个赛站，每个赛站同一所学校最多派 $c_i$ 队。给出 $n$ 个队伍的实力 $w_i$ 和学校 $S_i$，问对于每个队伍，最劣情况下的最优名次。

不难看出 $c_i$ 越小我们可以达到的排名就越高，因此我们只考虑 $c_i$ 最小的赛站。然后以 $w_i$ 排序从大到小模拟一下情况即可。

Code

 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
#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    vector<int> c(k);
    for (auto &x : c)
        cin >> x;
    int p = *min_element(c.begin(), c.end());
    struct Team {
        int idx;
        int w;
        string s;
        bool operator<(const Team &o) const { return w > o.w; }
    };
    vector<Team> vec(n);
    unordered_map<string, int> ump;
    for (int i = 0; auto &[idx, w, s] : vec) {
        idx = i++;
        cin >> w >> s;
        if (not ump.contains(s))
            ump[s] = 0;
    }
    sort(vec.begin(), vec.end());
    vector<int> ans(n);
    int cur = 0;
    for (auto [idx, w, s] : vec) {
        if (ump[s] < p) {
            cur++;
            ump[s]++;
        }
        ans[idx] = cur;
    }

    for (int i = 0; i < n; i++) {
        cout << ans[i] << "\n";
    }

    return 0;
}

F. Tourist

给定初始分值 $1500$ 和 $n$ 个比赛分值变化，问多少场能上 $4000$。

显然模拟即可。

Code

 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
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
void solve() {
    i64 cur = 1500;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        cur += x;
        if (cur >= 4000) {
            cout << i << "\n";
            return;
        }
    }
    cout << "-1\n";
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1;
    while (T--)
        solve();
    return 0;
}

G. Game

Alice 和 Bob 在玩游戏，对于每一句游戏，Alice 有 $p_0$ 的概率获胜，Bob 有 $p_1$ 的概率获胜，剩下的 $1-p_0-p_1$ 的概率是平局，平局什么都不会发生。若赢家的筹码数量大于等于输家的筹码数量，则赢家获胜，游戏结束；否则输家失去与赢家当前筹码数量相等的筹码，游戏继续。问 Alice 最终获胜的概率。

不难发现因为平局什么都不做，所以实际上 Alice 赢的概率为 $p_0/(p_0+p_1)$，我们记为 $a_0$，同样的，Bob 赢的概率记为 $a_1$。然后我们不难发现答案 $f(x,y,a,b)=0$ 当 $x=0$，否则为 $a^{\lfloor y/x \rfloor}\times(1-f(y\bmod x, x, b,a))$

这里之所以能这么操作，是因为我们这里的操作本质上就是计算 Alice 需要赢的次数以及 Bob 需要输的次数，然后我们不难发现后者其实就是 $1$ 减去 Bob 赢的次数（这里的 Bob 是要能满足 Alice 赢的约束的，$a^{\lfloor y/x \rfloor}$ 的意思就是 Alice 赢了 $\lfloor y/x \rfloor$ 次的概率，因为只有 $\lfloor y/x \rfloor=0$ 我们才能以 Alice 赢的姿态结束游戏，在这种姿态下，Bob 被输的只剩 $y\bmod x$ 个筹码了，这里我们就可以交换二者来简略计算）。因此我们搞一个类似于辗转相除的递归解决即可。

Code

 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
#include <bits/stdc++.h>
using namespace std;

#define int long long
constexpr int MOD = 998244353;

int fpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1)
            (res *= a) %= MOD;
        (a *= a) %= MOD;
        b >>= 1;
    }
    return res % MOD;
}

int inv(int x) { return fpow(x, MOD - 2); }

void solve() {
    int x, y;
    cin >> x >> y;
    int a0, a1, b;
    cin >> a0 >> a1 >> b;
    b = inv(a0 + a1);
    a0 = b * a0 % MOD, a1 = b * a1 % MOD;
    cout << [](this auto self, int x, int y, int a, int b) -> int {
        if (x == 0)
            return 0;
        return fpow(a, y / x) * ((1 - self(y % x, x, b, a) + MOD) % MOD) % MOD;
    }(x, y, a0, a1) << "\n";
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

I. Strange Binary

给定一个数字 $n \in [0,2^{30})$，求数组 $a$ 满足 $a_i \in {-1,0,1}$ 使得 $\sum_0^{31}a_i\times2^i=n$。

不难发现这玩意和二进制有关系：我们首先设每一个 $a_i$ 为 $1$，根据我们在数电课上的常识，$a_{i-1} = -1$ 当且仅当 $n$ 在二进制下 $2^i$ 对应的位上为 $1$。然后我们不难发现对于 $4 \mid n$ 的情况，必然会有两个 $0$ 连续出现，这样我们就完成了这道题。

Code

 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
#include <bits/stdc++.h>
using namespace std;

#define int long long
void solve() {
    int n;
    cin >> n;
    if (n % 4 == 0) {
        cout << "NO\n";
        return;
    }
    cout << "YES\n";
    array<int, 32> a;
    a.fill(1);
    int x = (1ll << 32) - 1 - n;
    for (int i = 1; i < 32; i++) {
        if (((x >> i) & 1))
            a[i - 1] = -1;
    }
    if (n % 2 == 0)
        a[0] = 0;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 8; j++) {
            cout << a[8 * i + j] << " \n"[j == 7];
        }
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

J. Stacking of Goods

给定 $n$ 个谷子，第 $i$ 个谷子有参数 $w_i, v_i, c_i$，其中 $w_i$ 表示谷子的重量，$v_i$ 表示谷子的体积，$c_i$ 表示如果这个谷子上方的谷子重量为 $W_i$，其体积就能被压缩为 $v_i-c_i\times W$。

我们不难发现，如果 $j$ 在 $i$ 之前，我们想要交换 $i$ 和 $j$ 当且仅当 $c_i/w_i<c_j/w_j$，因为此时有被压缩量的变化值 $\Delta=[c_j(w_i+W)+c_iW]-[c_i(w_j+W)]+c_jW=c_jw_i-c_iw_j>0 \quad \blacksquare$

Code

 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
#include <bits/stdc++.h>
using namespace std;

#define int long long
struct Good {
    int w;
    int v;
    int c;
    bool operator<(const Good &o) const { return c * o.w < w * o.c; }
};
void solve() {
    int n;
    cin >> n;
    vector<Good> goods(n);
    for (auto &[w, v, c] : goods) {
        cin >> w >> v >> c;
    }
    sort(goods.begin(), goods.end());
    int sum = 0;
    int ans = 0;
    for (auto &[w, v, c] : goods) {
        ans += v - c * sum;
        sum += w;
    }
    cout << ans << "\n";
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1;
    while (T--)
        solve();
    return 0;
}

L. 502 Bad Gateway

题意略。

不难发现期望为 $(c-1)/2+t/c$，在 $\sqrt2t$ 处取等。

Code

 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
#include <bits/stdc++.h>
using namespace std;

#define int long long

struct Frac {
    int a, b;

    Frac(int _a, int _b) {
        int _g = gcd(_a, _b);
        a = _a / _g, b = _b / _g;
    }

    Frac operator+(const Frac &o) const {
        int _b = lcm(b, o.b);
        int _a = _b / b * a + _b / o.b * o.a;
        return {_a, _b};
    }

    bool operator<(const Frac &o) const { return a * o.b < o.a * b; }
};

void solve() {
    int n;
    cin >> n;
    Frac ans(1e9, 1);
    int v = sqrt(2 * n);
    for (int i = 0; i <= 1; i++) {
        if (v + i > 0) {
            int x = v + i;
            Frac t = Frac(x + 1, 2) + Frac(n, x) + Frac(-1, 1);
            if (t < ans)
                ans = t;
        }
    }
    cout << ans.a << " " << ans.b << "\n";
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

好困，睡觉。

傻逼舍友在打三角洲。