题解：ABC470E Concentration

xingtiankai2023 · 2026-08-09 09:20:27 · 题解

思路

考虑最优策略是怎么样的。

• 第一步：翻开一张未知的牌，设数字为 X。
  • 若 X 已经出现过，则第二步直接翻已知的牌，得分 +1，生命不变。
  • 若 X 尚未出现过，则进入第二步。
• 第二步：翻开一张未知的牌，设数字为 Y。
  • 若 Y = X，得分 +1，生命不变。
  • 若 Y 已经出现过，生命 -1，若生命值不为 0，则继续翻这两张数字为 Y 的牌，得分 +1。
  • 若 Y 尚未出现过，生命 -1。

根据上述策略，设 dp_{i,j,k,0/1} 为已经翻开了 i 张牌，其中配对了 j 组，剩余生命值为 k，下一回合要进行第一步/第二步的概率。则当前未翻开牌的个数为 2n-i，已翻开但未配对的牌的个数为 i-2j，初始 dp_{0,0,L,0}=1，其余为 0，由上述策略可以列出转移式。

• 若 k > 1，dp_{i + 1,j + 1,k - 1,0}\gets dp_{i + 1,j + 1,k - 1,0}+dp_{i,j,k,1}\times\frac{i-2j-1}{2n-i}。
• 若 k = 1，dp_{i + 1,j,k - 1,0}\gets dp_{i + 1,j,k - 1,0}+dp_{i,j,k,1}\times\frac{i-2j-1}{2n-i}。

由对称性可知，总分的期望等于平均牌的面值乘以期望配对的次数，设 ave=\frac{1}{n}\sum a_i。则

时间复杂度：O(n^2L)。

代码

#include<iostream>
using namespace std;
#define ld long double
int read() {
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
const int N = 210;
int n,m;
int a[N];
ld dp[2 * N][N][N][2],ave;
int main() {
    n = read(),m = read();
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        ave += a[i];
    }
    ave /= n;
    dp[0][0][m][0] = 1;
    ld ans = 0;
    for (int i = 0; i < 2 * n; i++) {
        for (int j = 0; 2 * j <= i; j++) {
            for (int k = 1; k <= m; k++) {
                dp[i + 1][j + 1][k][0] += dp[i][j][k][0] * (i - 2 * j) / (2 * n - i);
                dp[i + 1][j][k][1] += dp[i][j][k][0] * (2 * n - i - (i - 2 * j)) / (2 * n - i);
                dp[i + 1][j + 1][k][0] += dp[i][j][k][1] / (2 * n - i);
                if (k > 1) {
                    dp[i + 1][j + 1][k - 1][0] += dp[i][j][k][1] * (i - 2 * j - 1) / (2 * n - i);
                }
                else {
                    dp[i + 1][j][k - 1][0] += dp[i][j][k][1] * (i - 2 * j - 1) / (2 * n - i);
                }
                dp[i + 1][j][k - 1][0] += dp[i][j][k][1] * (2 * n - i - (i - 2 * j)) / (2 * n - i);
            }
        }
    }
    for (int i = 1; i <= 2 * n; i++) {
        for (int j = 1; 2 * j <= i; j++) {
            ans += dp[i][j][0][0] * j * ave;
        }
    }
    for (int j = 1; j <= n; j++) {
        for (int k = 1; k <= m; k++) {
            ans += dp[2 * n][j][k][0] * j * ave;
        }
    }
    printf("%.15Lf\n",ans);
    return 0;
}