CSP202109-4 收集卡牌

@Pelom  July 4, 2022
题解 

题意

给出$n$种卡牌，获得每种的概率为$p_i$，重复获得的卡牌会转化为一枚硬币，$k$枚硬币可以兑换一张没有获得的卡牌，求抽到所有卡牌的期望次数
数据范围：$1\le n\le 16,1\le k\le 5,p\ge\frac{1}{10000},\sum_{i=1}^n p_i=1$

题解

  1. $20\%$数据
    深度优先搜索
    需要维护的状态量有

    • $cst$：当前抽卡次数
    • $pr$：到当前状态的概率
    • $stt$：当前持卡状态，以二进制状态压缩表示
    • $cnt$：当前持有硬币数

    若当前状态为$(cst,pr,stt,cnt)$，向下一状态的转移有

    1. 记持有卡牌数为$tot$，当持有硬币数$cnt\ge (n-tot)\times k$时，搜索结束，对答案贡献$cst\times pr$

    2. 否则，继续抽卡，记抽到的卡牌是$i$

      • 若抽到已获得的卡牌，即$stt\&(1<<i)=1$时，向$(cst+1,pr\times p_i,stt,cnt+1)$状态转移
      • 若抽到未获得的卡牌，即$stt\&(1<<i)=0$时，向$(cst+1,pr\times p_i,stt|(1<<i),cnt)$状态转移

    根据抽屉原理，最多抽取$k(n-1)+1$次
    时间复杂度为$O(n^{k(n-1)+1})$

  2. $20\%$数据
    递归
    与深度优先搜索相似，只不过是考虑一个状态能从哪几个后继状态转移而来，先递归到终点，再逐渐返回更新，相比正推，只需要维护两个量

    • $stt$：当前持卡状态，以二进制状态压缩表示
    • $cnt$：当前持有硬币数

    若当前状态为$(stt,cnt)$，向下一状态的转移有

    1. 记持有卡牌数为$tot$，当持有硬币数$cnt\ge (n-tot)\times k$时，搜索结束，返回$0$

    2. 否则，继续抽卡，记抽到的卡牌是$i$，最后返回所有的期望和$+1$

      • 若抽到已获得的卡牌，即$stt\&(1<<i)=1$时，向$(stt,cnt+1)$状态转移
      • 若抽到未获得的卡牌，即$stt\&(1<<i)=0$时，向$(stt|(1<<i),cnt)$状态转移

    时间复杂度为$O(n^{k(n-1)+1})$

  3. $100\%$数据
    记忆化搜索
    对于深度优先搜索算法，显然有大量重复计算的部分
    当目前持有卡牌状态和持有金币数量确定的时候，在消除到达该状态的概率的影响后，对最终答案的贡献是一定的
    用数组$f[stt][cnt]$记录消除概率影响前的贡献
    持有卡牌的状态共$2^n$种，持有硬币数量共$nk$种
    时间复杂度为$O(2^n\cdot nk)$
    代码

    #include<iostream>
#include<cstdio>
using namespace std;
const int N=16;
int n,k;
double p[N],f[1<<N][90];
double dfs(int cst,double pr,int stt,int cnt){
    if(f[stt][cnt]!=0)
        return f[stt][cnt]*pr;
    int tot=0;
    for(int i=0;i<n;i++)
        if(stt&(1<<i))
            tot++;
    if((n-tot)*k<=cnt){
        f[stt][cnt]=cst;
        return cst*pr;
    }
    double res=0;
    for(int i=0;i<n;i++)
        if(stt&(1<<i))
            res+=dfs(cst+1,pr*p[i],stt,cnt+1);
        else res+=dfs(cst+1,pr*p[i],stt|(1<<i),cnt);
    f[stt][cnt]=res/pr;
    return res;
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
        scanf("%lf",&p[i]);
    printf("%.10lf\n",dfs(0,1,0,0));
    return 0;
}

  4. $100\%$数据
    记忆化搜索
    同样用记忆化搜索减少重复计算，优化递归算法
    当目前持有卡牌情况和持有金币数量确定的时候，期望步数是确定的
    用$f[stt][cnt]$记录期望抽卡数
    时间复杂度为$O(2^n\cdot nk)$
    代码

    #include<iostream>
#include<cstdio>
using namespace std;
const int N=16;
int n,k;
double p[N],f[1<<N][90];
double dfs(int stt,int cnt){
    if(f[stt][cnt]>=0)
        return f[stt][cnt];
    int tot=0;
    for(int i=0;i<n;i++)
        if(stt&(1<<i))
            tot++;
    if((n-tot)*k<=cnt)
        return f[stt][cnt]=0;
    double res=0;
    for(int i=0;i<n;i++)
        if(stt&(1<<i))
            res+=p[i]*dfs(stt,cnt+1);
        else res+=p[i]*dfs(stt|(1<<i),cnt);
    return f[stt][cnt]=res+1;
}
int main(){
    memset(f,0xfe,sizeof(f));
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
        scanf("%lf",&p[i]);
    printf("%.10lf\n",dfs(0,0));
    return 0;
}

添加新评论