2026 牛客暑期多校 补题记录

第 1 场

概况

• Solved：A, C, E, F, G, J

补题

H

题意

Sol

一副手牌只需记 3 种牌的数量，用三元组表示：，。

这样的三元组有种。

Alice 和 Bob 的手牌组合只有种。

记表示还要进行轮，当前 Alice 的手牌为，Bob 的手牌为，双方都用最优策略时，Alice 的期望得分。

再记双方出牌为，补牌为，Alice 的得分为，于是便有转移：

发现每轮只需计算个状态，每个状态只要枚举种情况。

但最大有，怎么办？

注意到每一轮的得分增量会收敛，只需控制误差，就可作为长期平均每轮得分进行使用。

注

题解用了这样的结论：不可约、非周期的有限状态 MDP，值函数差分收敛到同一常数。
不知道这个结论怎么办？似乎只能凭直觉 Guess 了啊。

于是只需要计算个状态的 DP，对较小的，保存精确的。发现增量收敛后，对较大的直接线性外推即可。

先预处理，然后回答询问。

代码有亿点难写。

Code

std::vector<int> handId(64, -1); // 四进制表示牌组
std::vector<std::vector<int>> hand(10, std::vector<int>(3, 0)); // 牌组编号 -> 牌组计数

// nxtId[Id][play][draw]
int nxtId[10][3][3];

// nxt[state][Alice-play][Bob-play][Alice-draw][Bob-draw]
int nxt[100][3][3][3][3];

void solve(){
    #pragma region pre

    int tot = 0;
    
    for(int r = 0; r <= 3; ++r){
        for(int s = 0; r + s <= 3; ++s){
            int p = 3 - r - s;
            int code = r * 16 + s * 4 + p;
            handId[code] = tot++;
            hand[handId[code]] = {r, s, p};
        }
    }

    auto encode = [&](const std::vector<int>& H) -> int {
        return H[0] * 16 + H[1] * 4 + H[2];
    };

    memset(nxtId, -1, sizeof(nxtId));

    for(int id = 0; id < 10; ++id){
        for(int play = 0; play < 3; ++play){
            if(!hand[id][play]) continue;
            for(int draw = 0; draw < 3; ++draw){
                auto H = hand[id];
                --H[play], ++H[draw];
                nxtId[id][play][draw] = handId[encode(H)];
            }
        }
    }

    memset(nxt, -1, sizeof(nxt));

    for(int state = 0; state < 100; ++state){
        int aId = state / 10, bId = state % 10;
        
        for(int ap = 0; ap < 3; ++ap){
            if(!hand[aId][ap]) continue;
            for(int bp = 0; bp < 3; ++bp){
                if(!hand[bId][bp]) continue;
                for(int ad = 0; ad < 3; ++ad){
                    for(int bd = 0; bd < 3; ++bd){
                        int nA = nxtId[aId][ap][ad];
                        int nB = nxtId[bId][bp][bd];
                        nxt[state][ap][bp][ad][bd] = nA * 10 + nB;
                    }
                }
            }
        }
    }
    #pragma endregion

    auto score = [&](int a, int b) -> int {
        if(a == b) return 1;
        if(a == 0 and b == 1) return 3;
        if(a == 1 and b == 2) return 3;
        if(a == 2 and b == 0) return 3;
        return 0;
    };

    using ld = long double;
    const ld eps = 1e-14L;

    // rec[t][state] := f_t(state)
    const int MAXT = 20000;
    std::vector<std::vector<ld>> rec; rec.reserve(MAXT);
    std::vector<ld> pre(100), cur(100);
    rec.push_back(pre);

    int rounds = 0;
    ld L = 0, R = 0;

    while(rounds < MAXT){
        for(int state = 0; state < 100; ++state){
            int aId = state / 10, bId = state % 10;
            ld bestA = -1e100L;

            for(int ap = 0; ap < 3; ++ap){
                if(!hand[aId][ap]) continue;
                ld bestB = 1e100L;

                for(int bp = 0; bp < 3; ++bp){
                    if(!hand[bId][bp]) continue;
                    ld sum = 0.0L;

                    for(int ad = 0; ad < 3; ++ad){
                        for(int bd = 0; bd < 3; ++bd){
                            int ns = nxt[state][ap][bp][ad][bd];
                            sum += pre[ns];
                        }
                    }

                    ld val = score(ap, bp) + sum / 9.0L;
                    bestB = std::min(bestB, val);
                }

                bestA = std::max(bestA, bestB);
            }
            cur[state] = bestA;
        }

        ++rounds;
        rec.push_back(cur);
        ld low = 1e100L, high = -1e100L;
        for(int state = 0; state < 100; ++state){
            ld delta = cur[state] - pre[state];
            low = std::min(low, delta);
            high = std::max(high, delta);
        }
        L = low, R = high;
        pre.swap(cur);
        if(R - L <= eps) break;
    }

    ld inc = (L + R) / 2.0L;
    
    int T = read();

    auto card = [&](char c) -> int {
        switch(c){
            case 'R': return 0;
            case 'S': return 1;
            case 'P': return 2;
        } return -1;
    };

    auto encode_s = [&](const std::string& s) -> int {
        std::vector<int> H(3, 0);
        for(char c : s) ++H[card(c)];
        return encode(H);
    };

    while(T--){
        int k = read();
        std::string A, B; std::cin >> A >> B;
        int aId = handId[encode_s(A)], bId = handId[encode_s(B)];
        if(k <= rounds){
            printf("%.12Lf\n", rec[k][aId * 10 + bId]);
        }
        else{
        //    printf("%.12Lf\n", rec[MAXT][aId * 10 + bId] + inc * (k - MAXT));
            printf("%.12Lf\n", rec[rounds][aId * 10 + bId] + inc * (k - rounds));
        }
    }
}

第 2 场

概况

• Solved：B, G, L, M, N

补题

H

题意

Sol

赛时没怎么看这个题，补题的时候，看了一眼就想到了一个简单做法…

首先，的 popcount 为奇和为偶的数是相同的，且数量均为偶数。能够配对的两个数，其 popcount 的奇偶性是一样的，因此，当被删去的和的 popcount 奇偶性不同时，一定不存在构造方案。

反之必然存在吗？

先考虑不删和的构造方案。一个很简单的做法就是，钦定配对的数的高位全部相同，只有低位各不同，也就是把和进行配对。

然后删掉和。如果，那再好不过了，它们本来就是一对，不会对其它配对产生影响，但一般情况下和不会是一对，假设删前和配对的数是，和配对的数是，并记所有能配对的数对为，则我们需要寻找一条路径，使得，其中，的含义是，能和的一个数配对，剩下的数能和的一个数配对…最后剩下的数能和配对。

为了让和配对，我们可以翻转的低位的其中一位，再任意翻转的任意一高位。重复这一过程，直到走到为止。记，，只要不断翻转差异的位，这样的路径也就构造出来了。

赛时被其它题打爆了，这么简单的构造没场切，属实可惜。

Code

void solve(){
    int n = read(), a = read(), b = read();
    #define popcount __builtin_popcount
    int pa = popcount(a), pb = popcount(b);
    if((pa & 1) ^ (pb & 1)) return puts("No"), void();

    puts("Yes");

    std::vector<bool> vis(1 << n);
    vis[a] = vis[b] = true;

    if((a >> 2) ^ (b >> 2)){
        std::vector<int> w;
        int cur = a >> 2;
        w.push_back(cur);

        for(int i = 0; i <= n - 3; ++i){
            if(((a >> 2) ^ (b >> 2)) >> i & 1){
                cur ^= 1 << i;
                w.push_back(cur);
            }
        }

        int m = w.size() - 1;
        int pre = a ^ 3;

        for(int i = 1; i <= m; ++i){
            int v;
            if(i == m) v = b ^ 3;
            else{
                if((popcount(w[i]) & 1) ^ (pa & 1)) v = w[i] << 2 | 1;
                else v = w[i] << 2;
            }

            printf("%d %d\n", pre, v);
            vis[pre] = vis[v] = true;
            pre = v ^ 3;
        }
    }

    for(int i = 0; i < (1 << n); ++i){
        if(vis[i]) continue;
        printf("%d %d\n", i, i ^ 3);
        vis[i] = vis[i ^ 3] = true;
    }
}

F

题意

Sol

赛时只知道这大概率是一个的树形 DP，但是实在不会推式子。

赛后学习了一下题解，也是终于搞懂了这道题。

首先，如果固定根节点的权值为，则子树中任意顶点的值可以表示为。因此问题等价于给边定向，使得所有顶点相对于根的偏移量的极差最小。

极差只与相对值有关，根节点的权值直接置零来做。

观察（数据范围）发现最大极差是有上界的，这个上界是。

题解是这样证明的：

注

直接对根节点赋值，接下来从根节点出发进行搜索，每个新搜索到的点一定能在区间内找到一个可行的权值。

这个证明有点短，应该再补上一句，当根节点时，其子节点的两个选值与，必有一个也属于区间。

然后是 DP 状态设计，可以借鉴类似于背包的那种状态设计。令表示在以为根的子树中，令的权值为（根节点的权值可以任取，这里为方便说明，直接取了），且子树内所有顶点权值不小于的条件下，子树内顶点权值的最大值的最小可能值。其中。因为本身的权值为，所以。

注意，这个是单调的，随的增大而减小，这个性质转移的时候会用到。

这个状态设计很妙，当实际的最小值为时，最大值最小就是，于是答案就是。

状态设计出来后，转移就不难了。考虑的一个孩子，边权为。由于有的约束，因此= 0 时，只能取或。分讨一下。

Case #1：

要把子树转移给，首先要把子树的权值平移一下，因为此时的权值是，而数组是在根节点为下定义的。

子树内部所枚举的最小值，在的语境下对应，同理最大值对应，所以实际最值分别为和。

所以对于子树内部的每个，对子树的贡献是。应取最小的贡献转移给子树。这时我们惊奇地发现，根据的单调性，贡献的最小值在为最大值时取到。

是有约束的。如果我们希望整个子树的最小值大于等于，必须有。于是。

注意，这种情况需要才能取。

Case #2：

和上面是类似的，此时子树的实际最值分别为和。最小值要大于等于，其中天然满足，只需与。

同上，由单调性，子树最小点权的最大值和最大点权的最小值都在最大时取到。此时的点权最小值为，点权最大值为，后者即是贡献。

对所有的，都能取这种情况。

合并就是两种情况取，时间复杂度。

Code

void solve(){
    int n = read();
    struct Edge {int v, w;};
    std::vector<std::vector<Edge>> adj(n + 1);
    int W = 0;
    for(int i = 1; i < n; ++i){
        int u = read(), v = read(), w = read();
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        W = max(W, w);
    }
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(W << 1, 0));

    auto dfs = [&](auto&& self, int x, int p) -> void {
        for(auto& [y, w] : adj[x]){
            if(y == p) continue;
            self(self, y, x);
            for(int i = 0; i < (W << 1); ++i){
                ll tmp = INT_MAX;
                if(i >= w) tmp = min(tmp, max(0, dp[y][i - w] - w));
                tmp = min(tmp, dp[y][min(i + w, 2 * W - 1)] + w);
                dp[x][i] = max(dp[x][i], tmp);
            }
        }
    }; dfs(dfs, 1, 0);

    for(int u = 1; u <= n; ++u){
        ll ans = INT_MAX;
        for(int i = 0; i < (W << 1); ++i) ans = min(ans, dp[u][i] + i);
        printf("%d ", ans);
    } puts("");
}

第 3 场

概况

• Solved：A, B, F, G, J, K, L

补题

B

虽然队友赛时 Guess 出了结论，但我觉得这题需要补。

题意

Sol

首先，若或，概率为，这是平凡的。只需考虑的情形。

令，表示中奖次数。

小明在次购买中中奖次，组合数为。但是，喝到瓶的过程中，小明的钱不能小于或等于。这就是此题难点。

考虑一个折线图，如果中奖就向上走步，否则向下走步。这里的关键性质就是，向下走的步长严格等于。如果要从走到，它绝不可能错过之中的任何一个整数。不妨设折线图是无限延展的，且每经过一个长为的周期，总高度就下降。

我们可以定义一种特殊的点：在这个点之前的所有时刻，折线图的高度都严格大于这个点的高度。（可以理解为“历史最低点”）。

任意长为的周期，必然产生个这种点。（第一次到达、第一次到达、、第一次到达的这个时刻）。

前面提到，折线图每经过一个长为的周期，总高度就下降。一个长度为的序列，一共能进行种循环移位，序列里的每个点都能作为起点。合法的起点要满足，从它开始走步，最后一步必须是它这一段的 “历史最低点”。

在无限图像中，什么样的起点能满足这个条件？很显然，只能是 “历史最低点” 之后的那个点。

于是，在所有长为的循环移位中，合法序列的比例为。

这个结果和无关，相当 Amazing 啊。

由于总的排列数为，因此原题中所有合法的排列数为，这样就做完了。

赛时觉得这个和 Catalan 数很像，但它的步长不是和，而是和，有点像推广形式，但不会呀。这种题能过一车，肯定有结论，事实也确实如此。

Raney引理

对于的整数序列，其所有循环位移中恰有一个所有非空前缀和都为正。

（《具体数学》里有讲这个引理，但我怎么可能学过…）

为方便和引理形式对应，我们反转一下赚钱和亏钱的符号，得到一个长度为的整数序列，序列总和为，序列的每个元素最大不超过。记的前缀和序列为

要求有多少序列，满足所有的非空前缀和严格大于。

因为序列的总和是，且每次最多向上走，则必然存在个点，满足：

于是划分出个子序列，且它们的和均为。由 Raney 引理知，分别对这些子序列做循环移位，满足非空前缀和都为正的序列是唯一的。

于是，在的个循环移位中，合法序列数为（这个子序列起点的循环移位）。

此题的本质相当于发现以下引理（名字是我编的）：

广义循环引理

长度为的整数序列，总和，且每个元素最大不超过。

则在的个循环移位中，恰有个移位满足所有的非空前缀和严格大于。

综上，本题答案即为

Bonus

P6672 [清华集训 2016] 你的生命已如风中残烛

题意：已知长为的非负整数序列满足，求使得的排列数。

看到前缀和，尝试转化成 Raney 引理的形式。

每次打牌，手牌变化量要么为（特殊牌），要么为（普通牌），。

手牌数永远不能等于，即前缀变化量必须始终。

总和为，前缀和大于等于，而 Raney 引理的形式不一样？还需要转化。

考虑人为添加一个虚拟终点，在的最后加一个，则的总和为，且到达最后一步前，前缀和严格大于。这等价于在牌堆的最后放一张普通牌。

然后就可以用 Raney 引理了。

把这张牌看作彼此不同的牌，总共有种排列方式。

序列长度，初始资金，总变化量，每次最多往下掉，和多校的题的形式完全等价了。对于每个排列的种循环移位，只有种合法序列，占比。

因此，在这张牌的所有排列中，合法排列总数为。

由于我们加入了虚拟牌，且虚拟牌和普通牌等价，我们还需求出最后一张牌是普通牌的概率，这显然是。

于是，本题最终答案为

第 4 场

概况

• Solved：B, C, D, I

F 题被卡常了，大无语。

补题

咕咕咕

第 5 场

概况

• Solved：C, E, I, K, L, N

补题

咕咕咕

第 6 场

概况

• Solved：D, F, G, H, I

补题

咕咕咕

第 7 场

概况

• Solved：A, D, G, K, L

补题

咕咕咕

第 8 场

概况

• Solved：B, E, F, G, H, I, K, M

补题

咕咕咕

第 9 场

• Solved: B, D, H, I

补题

咕咕咕

第 10 场

• Solved: A, B, E, J, K, L

补题

咕咕咕