CSP202109-4 收集卡牌

题意

给出$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;
   }