「WyOJ Round 1」持 · 山海为肩

Pigsyy · 2025-03-31 13:35:49 · 题解

Solution

算法标签： 动态规划。

考虑三进制状压，令 0 表示出石头，1 表示出布，2 表示出剪刀。令 f_{i,j,k} 表示对于出招方式 j，前 i 轮获胜 - 失败等于 k 且 i+1\sim m 轮强制钦定与 j 出招方式一样。转移分讨第 i 轮对局情况（令 x 为第 i 轮出的方式）：

1. 获胜：第 i 轮高适只能出 (x+2)\bmod 3，所以从对应的 f_{i-1,j-3^ix+3^i(x+2)\bmod 3,k-1} 转移而来，因为这样强制钦定第 i 位是 (x+2)\bmod 3，从而保证获胜。
2. 平局：第 i 轮高适只能出 x，所以从 f_{i-1,j,k} 转移而来。
3. 失败：第 i 轮高适只能出 (x+1)\bmod 3，所以从对应的 f_{i-1,j-3^ix+3^i(x+1)\bmod 3,k+1} 转移而来。

时间复杂度：O(3^m m^2)。

Code

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

const double eps = 1e-10;

int n, m;
int pw[13];
double dp[2][531441][25];

int get(string x) {
    if (x == "rock") return 0;
    else if (x == "paper") return 1;
    else return 2;
}

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    cin >> n >> m;
    pw[0] = 1;
    for (int i = 1; i <= m; i ++)
        pw[i] = pw[i - 1] * 3;

    for (int i = 1; i <= n; i ++) {
        string out;
        double p;
        cin >> p;
        int mask = 0;
        for (int j = 0; j < m; j ++)
            cin >> out, mask += pw[j] * get(out);
        dp[0][mask][m] += p;
    }

    for (int j = 1; j <= m; j ++)
        for (int i = 0; i < pw[m]; i ++)
            for (int k = 0; k <= 2 * m; k ++) {
                dp[j & 1][i][k] = dp[(j - 1) & 1][i][k]; // 第 j 轮平局
                int out = i / pw[j - 1] % 3;
                // 第 j 轮获胜
                if (k) dp[j & 1][i][k] += dp[(j - 1) & 1][i - out * pw[j - 1] + (out + 2) % 3 * pw[j - 1]][k - 1];
                // 第 j 轮失败
                if (k + 1 < 2 * m) dp[j & 1][i][k] += dp[(j - 1) & 1][i - out * pw[j - 1] + (out + 1) % 3 * pw[j - 1]][k + 1];
            }

    double res = -1;
    int mask;
    vector<pair<string, int>> ord;
    for (int i = 0; i < pw[m]; i ++) {
        string temp;
        for (int j = 0; j < m; j ++)
            temp += char((i / pw[j] % 3) + '0');
        ord.push_back({temp, i});
    }
    sort(ord.begin(), ord.end());

    for (auto [t, i] : ord) {
        double sum = 0;
        for (int j = m; j <= 2 * m; j ++)
            sum += dp[m & 1][i][j];
        if (sum > res + eps)
            res = sum, mask = i;
    }

    printf("%.6lf\n", res);
    for (int i = 0; i < m; i ++)
        if (mask / pw[i] % 3 == 0) printf("rock ");
        else if (mask / pw[i] % 3 == 1) printf("paper ");
        else printf("scissors ");
    printf("\n");

    return 0;
}