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));
        }
    }
}