AT_abc404_f [ABC404F] Lost and Pound 题解

· · 题解

upd on 2025.11.14 根据要求删除部分“喵”语气词。

你们的喵喵又来啦！

上次我写了一篇紫题题解，今天来写 ABC 404 F 的题解啦！

首先评价一下这个题目，嗯非常的不错啊，但是一眼看上去很难的感觉。一做发现其实并不难的喵，大家千万不要怕呀。

好的咱们来说下题意喵。

小 B 有 n 个按钮，其中有一个按钮是特殊按钮，其他 n-1 个按钮都是普通按钮。在视觉上是无法区分特殊按钮与普通按钮的！当然，小 B 是清楚的啦。

现在要进行 t 轮游戏喵。每一轮游戏开始前，小 B 都会将这 n 个按钮打乱排成一排。小 A 需要按下 m 次按钮，他可以选择任何一个按钮并按下。一个按钮当然是可以在一轮中被按下多次的啦。

当这所有 t 轮游戏结束以后，小 B 会告诉小 A 他一共按下了多少次特殊按钮呀。小 A 想知道，他在所有 t 轮游戏结束后，按下特殊按钮的次数至少为 k 的概率。误差不能超过 10^{-6} 次方，不然会被判为错误答案喵！

接下来就是思路部分啦。有点长但很详细，大家要认真阅读哦。

这个题目一看就是概率 DP，是吧？那不就好办了吗，直接朝着这个方向去思考嘛！

在本题中正着整是不大好弄的，因此我们反过来喵。咱们定义 dp_{i,j} 表示当前游戏进行到第 i 轮，距离按下特殊按钮 k 次还剩 j 次时的概率。当然了，咱把所有 j<0 的都要缩减到 j=0 的范围内，是吧？说是这么说，其实上却是把所有 j>k 的都缩减到了 j=k 的范围内呢！初始化 dp_{0,k}=1，最终答案也非常明了了吧，就是 dp_{t,0}！

好的喵，接下来一步就是状态转移了。这一步是最最重要的。

注意到按钮都是被小 B 乱序排列的，那我们在按下按钮的时候不妨假设只按下前 len 个按钮，后面 n-len 个按钮碰都不碰，这样是可以的，对吧？然后我们设第 i 个按钮按下了 a_i 次，也没问题吧？为了方便，咱们保证 a_i \ge a_{i+1}，还是 OK 的是吧？

好的叽里呱啦一大串终于是定下了分配喵。那么我们就根据每一种分配方法，来计算对应的概率就可以啦。

这样说也太模糊了吧！怎么计算概率？嘿嘿，你说到重点上来了！其实上很简单的，首先咱们有 \frac{n-len}{n} 的概率是本轮没有按下特殊按钮的对吧，因为这个特殊按钮在后面那些本轮没有按到的按钮里面嘛！那这一部分就要用这个概率乘上 dp_{i-1,j} 对吧。接下来就是那些在前面范围内的啦，也很简单的喵，枚举 u 从 1 \sim len，又有 \frac{1}{n} 的概率是要乘上 dp_{i-1,\min(k,j+a_u)}。为什么应该都清楚吧，因为我们这次按下了这个特殊按钮 a_u 次呀！至于为什么要和 k 取 \min，那是因为前面咱们说了所有 j > k 都要压缩进 j=k 的位置嘛！

那这样是不是就完成了？好像不对，有一步还没讲清楚！哪一步？就是拆分的那一步啦！我们的 a 到底是咋整出来的？这也是个问题呀，对吧！别急，你听我说喵。

我们可以用一个 vector 类型的 vector（人类智慧做法哈哈），取名叫 fp（哈哈分配的拼音哈），然后让它来存储每一种分配方法。具体怎么存，怎么算？很简单，整个递归，一开始跑初始化，一个一个算就行了。具体来说，递归函数传上两个参数 sum 和 lst ，sum 表示当前还能分配多少次，lst 表示上个数分配了多少次。如果当前 sum=0，那么我们判断一下当前所存储的这种分配方法的长度是不是没有超过 n ，因为超过 n 就非法了。如果是符合要求的答案就扔到 fp 里去喵！接下来就是递归环节了，枚举 i=1 \sim \min(sum,lst)（当然实际实现中用的是倒序枚举），这个 i 就是本次所选取的次数啦！把它存进状态数组，继续递归就行了。记得回溯的时候要把这个玩意儿从状态数组里扔出去哦，要不然状态数组就全乱了喵！

这样，咱们就结束了本题。是不是还挺简单的喵？

最后我亮一个代码吧。是对照上面的思路来的。当然啦保证对的喵，不信看提交记录嘛！当然请各位不要抄袭我的代码，多谢！

#include<bits/stdc++.h>
using namespace std;
int n,t,m,k;double dp[35][35];
vector<int> now;vector<vector<int>> fp;
void Init_Makefp(int sum,int lst){
    if(!sum){
        if(now.size()<=n)
            fp.push_back(now);
        return;
    }
    for(int i=min(sum,lst);i>0;i--){
        now.push_back(i);
        Init_Makefp(sum-i,i);
        now.pop_back();
    }
    return;
}
int main(){
    cin>>n>>t>>m>>k;
    Init_Makefp(m,m);dp[0][k]=1.0;
    for(int i=1;i<=t;i++)
        for(int j=0;j<=k;j++)
            for(auto s:fp){
                double ans=dp[i-1][j]*(n-s.size());
                for(int u:s)ans+=dp[i-1][min(k,j+u)];
                dp[i][j]=max(dp[i][j],ans/n);
            }
    printf("%.10lf",dp[t][0]);
    return 0;
}

既然都看到这里了，还麻烦你给可爱的喵喵留下一个小小的赞吧，万分感谢喵！