首页 > 代码库 > 698C

698C

2024-09-13 12:57:06   214人阅读

Description 
n个视频，长度为k的缓存，每次询问，每个视频以pi的概率被选，如果不在缓存区则加入，如果缓存区满了，则最先进缓存的出来，问10^100次操作以后每个视频在缓存的概率 
Input 
第一行两个整数n和k，第二行n个数表示每个视频被选中的概率 
(1<=k<=n<=20,0<=pi<=1,sum(pi)=1) 
Output 
输出10^100次操作后每个视频在缓存中出现的概率 
Sample Input 
3 1 
0.3 0.2 0.5 
Sample Output 
0.3 0.2 0.5 

10^100次方说明这个缓存肯定是填满了，那么也就是说只有最后几个操作可以影响到缓存中存在东西的概率 那么问题就转化成了装满缓存后每个物品存在的概率 就是说只要我加满了k 就停止。那么这个东西我们可以装压dp dp[i]表示i集合出现的概率。那么怎么转移呢？dp[i | 1 << j] = dp[i] * p[j] / sum (sum = sigma(p[k]), k不属于i， j属于i） 为什么呢 因为如果缓存中已经存在了某些东西，那么我们加进去是无效的，又因为我们加了很多次，那么这些无效的操作可以忽视（不是很懂，自己yy的）所以我们要除去选中缓存中已有物品的概率，剩下的概率就是从没选中的东西中选j的概率。那么这个dp就很好理解了。统计答案时如果这个集合的元素个数=k那么每个元素出现的概率加上这个dp值 还需要注意几点，1.sum不能很小； 2.如果p=0 那么这个物品肯定不会选中，所以我们先统计一下p不等于0的元素，和k比较一下谁更小，更小的作为k。

想想这还是我第一次打cf的题目呢，当时觉得这是什么东西，现在好像有了一些的进步。

#include<bits/stdc++.h>
using namespace std;
const int N = 23;
const double eps = 1e-6;
int n, k, all;
double dp[1 << N], p[N], ans[N];
inline double getsum(int x)
{
    double ret = 0;
    for(int i = 0; i < n; ++i) if(x & (1 << i)) ret += p[i];
    return 1 - ret;
}
int main()
{
    scanf("%d%d", &n, &k); all = 1 << n; int m = 0;
    for(int i = 0; i < n; ++i) 
    {
        scanf("%lf", &p[i]); 
        if(fabs(p[i]) > eps) ++m; 
    }
    k = min(k, m);
    dp[0] = 1;    
    for(int i = 0; i < all; ++i)
    {
        double sum = getsum(i);
        for(int j = 0; j < n; ++j) if(!(i & (1 << j)))
            dp[i | (1 << j)] += dp[i] * p[j] / sum; 
    }
    for(int i = 0; i < all; ++i) if(__builtin_popcount(i) == k)
        for(int j = 0; j < n; ++j) if(i & (1 << j)) ans[j] += dp[i];
    for(int i = 0; i < n; ++i) printf("%.7f ", ans[i]);
    return 0;
}

 

698C


联系
我们