2024-09-082024-09-22Contest Notes

2024 CCPC 网络预选赛正式赛

The 2024 CCPC Online Contest

警钟敲烂

Problems	AC
A. 军训 I	分讨，弃疗
B. 军训 II	○
C. 种树	⊕
D. 编码器-解码器	○
E. 随机过程	○
F. 包子鸡蛋 III	多项式，弃疗
G. 疯狂星期四	⊕
H. 另一个游戏	弃疗
I. 找行李	⊕
J. 找最小	⊕
K. 取沙子游戏	○
L. 网络预选赛	○

B 结论

签到，队友写的。

C 贪心

好聪明的设计

一次操作最多拓展 $2$ 个点。

对于一个 $siz$ 大小的子树，且只有根节点被染色了，那么一共需要 $\lfloor \frac{siz}{2} \rfloor$ 次操作。

对子树根节点是否被染色讨论：

如果已经被染色了，那么这个子树对根节点的父亲的贡献有两种情况：用最少次数做完子树时，是否存在多余的、且对子树根节点的父亲有贡献的操作。
如果没有被染色，那就向上传递，直到遇到被染色的为止。

#include <bits/stdc++.h>
using i64 = long long;
#define int i64
#define pb push_back
#define ep emplace
#define eb emplace_back
using std::max, std::min, std::swap;
using std::cin, std::cout, std::string, std::vector;
int read(int x = 0, int f = 0, char ch = getchar()) {
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}

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

    vector<int> vis(n + 1);
    for (int i = 1; i <= m; i++) {
        vis[read()] = 1;
    }

    vector<vector<int>> g(n + 1);
    for (int i = 1; i < n; i++) {
        int u = read(), v = read();
        g[u].pb(v), g[v].pb(u);
    }

    int ans = 0;
    vector<int> siz(n + 1);

    std::function<void(int, int)> dfs = [&](int u, int fa) {
        for (auto v : g[u]) {
            if (v == fa) continue;
            dfs(v, u);
            siz[u] += siz[v];
        }

        siz[u] += !vis[u];

        if (vis[u]) {
            ans += (siz[u] + 1) / 2;
            if (siz[u] & 1) vis[fa] = 1;
            siz[u] = 0;
        }
    };

    for (int i = 1; i <= n; i++) {
        if (vis[i]) {
            dfs(i, 0);
            break;
        }
    }

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

signed main() {
    for (int T = read(); T--; solve());
    // solve();
    return 0;
}

D 区间 DP

队伍因为这道题浪费了巨大多时间，小齐代码可读性和鲁棒性差，导致最后帮忙一起调才出了这道题

我觉得比如小齐今天那个设边界值就很乱，会容易出错
然后状态继承的时候也不明显，所以今天就漏了状态继承，我后面才发现
我觉得不要写的能省则省
这样会很容易出错也不容易调

解法 1

考虑一个区间 dp，$dp[i][l][r]$ 代表经过 $i$ 轮后，$t[l]…t[r]$ 的出现次数。

#include <bits/stdc++.h>
using i64 = long long;
#define int i64
#define pb push_back
#define ep emplace
#define eb emplace_back
using std::max, std::min, std::swap;
using std::cin, std::cout, std::string, std::vector;
int read(int x = 0, int f = 0, char ch = getchar()) {
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}

template <class T>
constexpr T power(T a, i64 b) { T res {1}; for (; b; b /= 2, a *= a) if (b % 2) res *= a; return res; }
constexpr i64 mul(i64 a, i64 b, i64 p) { i64 res = a * b - (i64)(1.L * a * b / p) * p; res %= p; if (res < 0) res += p; return res; }
template <i64 P>
struct MInt {
    i64 x;
    constexpr MInt() : x {0} {}
    constexpr MInt(i64 x) : x {norm(x % getMod())} {}
    static i64 Mod;
    constexpr static i64 getMod() { return P > 0 ? P : Mod; }
    constexpr static void setMod(i64 Mod_) { Mod = Mod_; }
    constexpr i64 norm(i64 x) const { if (x < 0) x += getMod(); if (x >= getMod()) x -= getMod(); return x; }
    constexpr i64 val() const { return x; }
    constexpr MInt operator-() const { MInt res; res.x = norm(getMod() - x); return res; }
    constexpr MInt inv() const { return power(*this, getMod() - 2); }
    constexpr MInt &operator*=(MInt rhs) & { if (getMod() < (1ULL << 31)) x = x * rhs.x % int(getMod()); else x = mul(x, rhs.x, getMod()); return *this; }
    constexpr MInt &operator+=(MInt rhs) & { x = norm(x + rhs.x); return *this; }
    constexpr MInt &operator-=(MInt rhs) & { x = norm(x - rhs.x); return *this; }
    constexpr MInt &operator/=(MInt rhs) & { return *this *= rhs.inv(); }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) { MInt res = lhs; res *= rhs; return res; }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) { MInt res = lhs; res += rhs; return res; }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) { MInt res = lhs; res -= rhs; return res; }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) { MInt res = lhs; res /= rhs; return res; }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) { i64 v; is >> v; a = MInt(v); return is; }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) { return os << a.val(); }
    friend constexpr bool operator==(MInt lhs, MInt rhs) { return lhs.val() == rhs.val(); }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) { return lhs.val() != rhs.val(); }
    friend constexpr bool operator<(MInt lhs, MInt rhs) { return lhs.val() < rhs.val(); }
};
template <>
i64 MInt<0>::Mod = 998244353;
constexpr int P = 998244353;
using Z = MInt<P>;

const int N = 1e2 + 5;
Z dp[N][N][N];

void solve() {
    string s, t;
    cin >> s >> t;

    int n = s.size();
    int m = t.size();

    s = ' ' + s;
    t = ' ' + t;

    for (int i = 0; i <= n; i++) {
        for (int l = 1; l <= m + 1; l++) {
            for (int r = 0; r < l; r++) {
                dp[i][l][r] = 1;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int l = 1; l <= m; l++) {
            for (int r = l; r <= m; r++) {

                for (int k = l - 1; k <= r; k++) {
                    dp[i][l][r] += dp[i - 1][l][k] * dp[i - 1][k + 1][r];
                }

                for (int k = l - 1; k < r; k++) {
                    if (s[i] == t[k + 1]) {
                        dp[i][l][r] += dp[i - 1][l][k] * dp[i - 1][k + 2][r];
                    }
                }

                // cout << l << " " << r << " " << dp[i][l][r] << '\n';
            }
        }
    }

    cout << dp[n][1][m];
}

/*
a
aba
abaaaba

a
aba
abacaba
abacabadabacaba
*/

signed main() {
    // for (int T = read(); T--; solve());
    solve();
    return 0;
}

解法 2

看题解好像有一种很赛艇的矩阵做法！

E 期望

一开始假式子确实浪费不少时间，我们沟通太烂了，经常不能互相确认做法的正确性

对于 Trie 第 i 层的某个节点，其不出现的概率是 $(1 - \frac{1}{26^{i}})^n$

其出现的概率就是 $1-(1 - \frac{1}{26^{i}})^n$

这一层总共有 $26^i$ 个点，每个点是否出现的概率都是相同的。

答案就是

$$
\sum_{i = 0}^{m}[1-(1 - \frac{1}{26^{i}})^n]26^i
$$

#include <bits/stdc++.h>
using i64 = long long;
#define int i64
#define pb push_back
#define ep emplace
#define eb emplace_back
using std::max, std::min, std::swap;
using std::cin, std::cout, std::string, std::vector;
int read(int x = 0, int f = 0, char ch = getchar()) {
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}

template <class T>
constexpr T pow(T a, i64 b) { T res {1}; for (; b; b /= 2, a *= a) if (b % 2) res *= a; return res; }
constexpr i64 mul(i64 a, i64 b, i64 p) { i64 res = a * b - (i64)(1.L * a * b / p) * p; res %= p; if (res < 0) res += p; return res; }
template <i64 P>
struct MInt {
    i64 x;
    constexpr MInt() : x {0} {}
    constexpr MInt(i64 x) : x {norm(x % getMod())} {}
    static i64 Mod;
    constexpr static i64 getMod() { return P > 0 ? P : Mod; }
    constexpr static void setMod(i64 Mod_) { Mod = Mod_; }
    constexpr i64 norm(i64 x) const { if (x < 0) x += getMod(); if (x >= getMod()) x -= getMod(); return x; }
    constexpr i64 val() const { return x; }
    constexpr MInt operator-() const { MInt res; res.x = norm(getMod() - x); return res; }
    constexpr MInt inv() const { return pow(*this, getMod() - 2); }
    constexpr MInt &operator*=(MInt rhs) & { if (getMod() < (1ULL << 31)) x = x * rhs.x % int(getMod()); else x = mul(x, rhs.x, getMod()); return *this; }
    constexpr MInt &operator+=(MInt rhs) & { x = norm(x + rhs.x); return *this; }
    constexpr MInt &operator-=(MInt rhs) & { x = norm(x - rhs.x); return *this; }
    constexpr MInt &operator/=(MInt rhs) & { return *this *= rhs.inv(); }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) { MInt res = lhs; res *= rhs; return res; }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) { MInt res = lhs; res += rhs; return res; }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) { MInt res = lhs; res -= rhs; return res; }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) { MInt res = lhs; res /= rhs; return res; }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) { i64 v; is >> v; a = MInt(v); return is; }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) { return os << a.val(); }
    friend constexpr bool operator==(MInt lhs, MInt rhs) { return lhs.val() == rhs.val(); }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) { return lhs.val() != rhs.val(); }
    friend constexpr bool operator<(MInt lhs, MInt rhs) { return lhs.val() < rhs.val(); }
};
template <>
i64 MInt<0>::Mod = 998244353;
constexpr int P = 998244353;
using Z = MInt<P>;

const Z inv26 = Z(26).inv();

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

    Z ans[2] = {1, 1};

    for (int i = 1, now = 1; i <= m; i++) {
        now = min(now * 26, n);
        ans[0] += now;
    }

    Z a = 26, b = inv26;
    for (int i = 1; i <= m; i++) {
        ans[1] += a * (1 - pow(1 - b, n));
        a *= 26, b *= inv26;
    }

    cout << ans[0] << ' ' << ans[1];
}

signed main() {
    // for (int T = read(); T--; solve());
    solve();
    return 0;
}

G 最大流

首先你可以算出来主角的最大花费 $c$，每个人最大花费就是 $\min(a_i, c - 1)$

问题转化为一个是否存在合法解的问题

根据以上信息跑个最大流：

源点向每个菜品连容量为菜品费用的边
菜品向食用的两个人连容量为菜品费用的边
每个人向汇点连容量为每个人最大花费的边

存在合法解当且仅当最大流等于菜品总费用

#include <bits/stdc++.h>
using i64 = long long;
#define int i64
#define pb push_back
#define ep emplace
#define eb emplace_back
using std::max, std::min, std::swap;
using std::cin, std::cout, std::cerr, std::string, std::vector;
int read(int x = 0, int f = 0, char ch = getchar()) {
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}

constexpr int inf = 1E9;
template<class T>
struct MaxFlow {
    struct _Edge {
        int to;
        T cap;
        _Edge(int to, T cap) : to(to), cap(cap) {}
    };
    
    int n;
    std::vector<_Edge> e;
    std::vector<std::vector<int>> g;
    std::vector<int> cur, h;
    
    MaxFlow() {}
    MaxFlow(int n) {
        init(n);
    }
    
    void init(int n) {
        this->n = n;
        e.clear();
        g.assign(n, {});
        cur.resize(n);
        h.resize(n);
    }
    
    bool bfs(int s, int t) {
        h.assign(n, -1);
        std::queue<int> que;
        h[s] = 0;
        que.push(s);
        while (!que.empty()) {
            const int u = que.front();
            que.pop();
            for (int i : g[u]) {
                auto [v, c] = e[i];
                if (c > 0 && h[v] == -1) {
                    h[v] = h[u] + 1;
                    if (v == t) {
                        return true;
                    }
                    que.push(v);
                }
            }
        }
        return false;
    }
    
    T dfs(int u, int t, T f) {
        if (u == t) {
            return f;
        }
        auto r = f;
        for (int &i = cur[u]; i < int(g[u].size()); ++i) {
            const int j = g[u][i];
            auto [v, c] = e[j];
            if (c > 0 && h[v] == h[u] + 1) {
                auto a = dfs(v, t, std::min(r, c));
                e[j].cap -= a;
                e[j ^ 1].cap += a;
                r -= a;
                if (r == 0) {
                    return f;
                }
            }
        }
        return f - r;
    }
    void addEdge(int u, int v, T c) {
        g[u].push_back(e.size());
        e.emplace_back(v, c);
        g[v].push_back(e.size());
        e.emplace_back(u, 0);
    }
    T flow(int s, int t) {
        T ans = 0;
        while (bfs(s, t)) {
            cur.assign(n, 0);
            ans += dfs(s, t, std::numeric_limits<T>::max());
        }
        return ans;
    }
    
    std::vector<bool> minCut() {
        std::vector<bool> c(n);
        for (int i = 0; i < n; i++) {
            c[i] = (h[i] != -1);
        }
        return c;
    }
    
    struct Edge {
        int from;
        int to;
        T cap;
        T flow;
    };
    std::vector<Edge> edges() {
        std::vector<Edge> a;
        for (int i = 0; i < e.size(); i += 2) {
            Edge x;
            x.from = e[i + 1].to;
            x.to = e[i].to;
            x.cap = e[i].cap + e[i + 1].cap;
            x.flow = e[i + 1].cap;
            a.push_back(x);
        }
        return a;
    }
};

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

    int s = n + m + 1, t = s + 1;
    MaxFlow<int> g(t + 1);

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

    int c = 0;
    int tot = 0;
    for (int i = 1; i <= m; i++) {
        int x = read(), y = read(), w = read();

        g.addEdge(s, n + i, w);
        g.addEdge(n + i, x, w);
        g.addEdge(n + i, y, w);

        tot += w;
        if (x == 1 or y == 1) c += w;
    }

    c = min(c + v[1], a[1]);
    bool flag = 1;
    g.addEdge(1, t, c - v[1]);
    for (int i = 2; i <= n; i++) {
        a[i] = min(a[i], c - 1);
        if (a[i] < v[i]) {
            flag = 0;
            break;
        }

        g.addEdge(i, t, a[i] - v[i]);
    }

    if (!flag or g.flow(s, t) != tot) {
        cout << "NO\n";
    } else {
        cout << "YES\n";
    }
}

signed main() {
    // for (int T = read(); T--; solve());
    solve();
    return 0;
}

I DP

赛时学弟队出了这题，短暂尝试了跟榜但是没什么想法，此时队友 E 有思路就去冲 E 了。可惜就差 1 分钟。

考虑尝试对每个可能的答案算出方案数，然后求和。发现不太好做。

常见套路：恰好转换成至少至多

设 $g(d)$ 表示答案大于等于 $d$ 的方案数，则 $ans = \sum_{d = 0}^{500}{d \times (g(d) - g(d + 1))}$

将行李和人排序，枚举 $d$。

如果 $a_i + d <= b_j$，那么 $a_i$ 这个行李就可以被 $b_j$ 这个人拿。且 $b_j$ 能拿的行李一定是 $b_{j + 1}$ 能拿行李的子集。

即然 $d$ 确定了，每个人可以拿的行李数量 $sum[i]$ 可以直接 $O(n^2)$ 统计出来。

$dp_{i, j}$ 表示前 $i$ 个人，拿了 $j$ 个行李的方案数。当前这个人不拿，就是 $dp_{i - 1, j}$。拿了，就是 $dp_{i - 1, j - 1}$ 乘上当前可选择的行李数量 $sum[i] - (j - 1)$

时间复杂度 $O(n^3)$

#include <bits/stdc++.h>
using i64 = long long;
#define int i64
#define pb push_back
#define ep emplace
#define eb emplace_back
using std::max, std::min, std::swap;
using std::cin, std::cout, std::cerr,std::string, std::vector;
int read(int x = 0, int f = 0, char ch = getchar()) {
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}

template <class T>
constexpr T power(T a, i64 b) { T res {1}; for (; b; b /= 2, a *= a) if (b % 2) res *= a; return res; }
constexpr i64 mul(i64 a, i64 b, i64 p) { i64 res = a * b - (i64)(1.L * a * b / p) * p; res %= p; if (res < 0) res += p; return res; }
template <i64 P>
struct MInt {
    i64 x;
    constexpr MInt() : x {0} {}
    constexpr MInt(i64 x) : x {norm(x % getMod())} {}
    static i64 Mod;
    constexpr static i64 getMod() { return P > 0 ? P : Mod; }
    constexpr static void setMod(i64 Mod_) { Mod = Mod_; }
    constexpr i64 norm(i64 x) const { if (x < 0) x += getMod(); if (x >= getMod()) x -= getMod(); return x; }
    constexpr i64 val() const { return x; }
    constexpr MInt operator-() const { MInt res; res.x = norm(getMod() - x); return res; }
    constexpr MInt inv() const { return power(*this, getMod() - 2); }
    constexpr MInt &operator*=(MInt rhs) & { if (getMod() < (1ULL << 31)) x = x * rhs.x % int(getMod()); else x = mul(x, rhs.x, getMod()); return *this; }
    constexpr MInt &operator+=(MInt rhs) & { x = norm(x + rhs.x); return *this; }
    constexpr MInt &operator-=(MInt rhs) & { x = norm(x - rhs.x); return *this; }
    constexpr MInt &operator/=(MInt rhs) & { return *this *= rhs.inv(); }
    friend constexpr MInt operator*(MInt lhs, MInt rhs) { MInt res = lhs; res *= rhs; return res; }
    friend constexpr MInt operator+(MInt lhs, MInt rhs) { MInt res = lhs; res += rhs; return res; }
    friend constexpr MInt operator-(MInt lhs, MInt rhs) { MInt res = lhs; res -= rhs; return res; }
    friend constexpr MInt operator/(MInt lhs, MInt rhs) { MInt res = lhs; res /= rhs; return res; }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a) { i64 v; is >> v; a = MInt(v); return is; }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) { return os << a.val(); }
    friend constexpr bool operator==(MInt lhs, MInt rhs) { return lhs.val() == rhs.val(); }
    friend constexpr bool operator!=(MInt lhs, MInt rhs) { return lhs.val() != rhs.val(); }
    friend constexpr bool operator<(MInt lhs, MInt rhs) { return lhs.val() < rhs.val(); }
};
template <>
i64 MInt<0>::Mod = 998244353;
constexpr int P = 998244353;
using Z = MInt<P>;

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

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

    std::sort(a.begin() + 1, a.end());
    std::sort(b.begin() + 1, b.end());

    Z ans = 0;
    vector<Z> g(505);
    for (int d = 0; d <= 500; d++) {

        vector<int> sum(m + 1);
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (b[i] - a[j] >= d) {
                    sum[i]++;
                }
            }
        }

        vector f(m + 1, vector<Z>(n + 1));
        f[0][0] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j <= min(n, sum[i]); j++) {

                f[i][j] += f[i - 1][j];
                if (j >= 1) {
                    f[i][j] += f[i - 1][j - 1] * (sum[i] - (j - 1));
                }
            }
            // for (int j = 0; j <= min(n, sum[i]); j++) {
            //     cerr << i << "-" << j << " " << f[i][j] << '\n';
            // }
        }

        for (int j = 0; j <= n; j++) {
            g[d] += f[n][j];
        }
    }

    for (int d = 0; d + 1 <= 500; d++) ans += (g[d] - g[d + 1]) * d;

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

/*

*/

signed main() {
    // for (int T = read(); T--; solve());
    solve();
    return 0;
}

J 线性基

3 个人 2 个完全不会线性基。我没想到要线性基，唉硬实力太烂了。

一开始还把题目读假了，以为是任意换 $a_i$ 和 $b_j$。后来发现只有 $a_i$ 和 $b_i$ 可以换。

那就很简单了，令 $c_i = a_i \oplus b_i$，交换意味着 $fa$ 和 $fb$ 都 $\oplus$ 上 $c_i$。

对于这 $O(n)$ 个 $c_i$，扔进线性基，然后用线性基贪心就做完了。

唐唐唐唐唐唐唐唐唐唐唐唐唐唐唐唐唐唐唐唐唐唐唐唐唐唐唐唐唐唐唐

#include <bits/stdc++.h>
using i64 = long long;
#define int i64
#define pb push_back
#define ep emplace
#define eb emplace_back
using std::max, std::min, std::swap;
using std::cin, std::cout, std::string, std::vector;
int read(int x = 0, int f = 0, char ch = getchar()) {
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}

struct Basis {
    int num_zero;
    std::vector<int> b;
    Basis() {}
    Basis(int n) { b.resize(n); std::fill(b.begin(), b.end(), 0); }
    bool add(int x) {
        for (int i = 62; i >= 0; i--) {
            if (x >> i & 1) {
                if (b[i]) {
                    x ^= b[i];
                } else {
                    b[i] = x;
                    return true;
                }
            }
        }
        num_zero++;
        return false;
    }
};

void solve() {
    int n = read();
    Basis bas(63);

    int fa = 0, fb = 0;
    vector<int> a(n), b(n);
    for (auto &x : a) x = read(), fa ^= x;
    for (auto &x : b) x = read(), fb ^= x;

    for (int i = 0; i < n; i++) bas.add(a[i] ^ b[i]);

    // cout << fa << " " << fb << '\n';

    for (int i = 62; i >= 0; i--) {
        if (max(fa ^ bas.b[i], fb ^ bas.b[i]) < max(fa, fb)) {
            fa ^= bas.b[i];
            fb ^= bas.b[i];
        }
    }

    cout << max(fa, fb) << "\n";
}

signed main() {
    for (int T = read(); T--; solve());
    // solve();
    return 0;
}

K 博弈

赛时思路不够 clean，导致浪费了点时间。

首先，奇数的情况是显然的。偶数的情况呢，想要 A 必胜，是否只需要在做完第一步之后完全复刻 B 的操作就行了？

对于一个 $n$，如果其 $lowbit \le k$，那么 A 第一步只需要取走 $lowbit$，随后完全复刻 B 的操作即可。

如果其 $lowbit > k$，那么无论 A 第一步怎么取，都会让 $lowbit$ 变成 $\le k$ 的状态，B 拿到这个状态就必胜。

#include <bits/stdc++.h>
using i64 = long long;
#define int i64
#define pb push_back
#define ep emplace
#define eb emplace_back
using std::max, std::min, std::swap;
using std::cin, std::cout, std::string, std::vector;
int read(int x = 0, int f = 0, char ch = getchar()) {
    while (ch < 48 or 57 < ch) f = ch == 45, ch = getchar();
    while(48 <= ch and ch <= 57) x = x * 10 + ch - 48, ch = getchar();
    return f ? -x : x;
}

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

    if ((n & (-n)) <= k) {
        puts("Alice");
    } else {
        puts("Bob");
    }
}

signed main() {
    for (int T = read(); T--; solve());
    // solve();
    return 0;
}

L 签到

签到题，代码就不放了

2024 CCPC 网络预选赛正式赛

https://tosakaucw.github.io/2024-ccpc-网络预选赛-正式赛/

Author

TosakaUCW

Posted on

2024-09-08

Updated on

2024-09-22

Licensed under

#XCPC

2024 CCPC 网络预选赛正式赛

B 结论

C 贪心

D 区间 DP

解法 1

解法 2

E 期望

G 最大流

I DP

J 线性基

K 博弈

L 签到

Author

Posted on

Updated on

Licensed under

Comments

Catalogue

2024 CCPC 网络预选赛 正式赛

B 结论

C 贪心

D 区间 DP

解法 1

解法 2

E 期望

G 最大流

I DP

J 线性基

K 博弈

L 签到

Author

Posted on

Updated on

Licensed under

Comments

Catalogue

2024 CCPC 网络预选赛正式赛