首页 > 代码库 > CodeForces 441E(Codeforces Round #252 (Div. 2))

CodeForces 441E(Codeforces Round #252 (Div. 2))

2024-07-12 06:19:46   240人阅读

思路：dp[i][now][mark][len]   i 表示当前第i 次now存的是后8位，mark为第9位为0还是1 len第九位往高位还有几位和第9位相等。  只存后8位的原因：操作只有200次每次都为加法的话后8位可以表示，如果为乘法第八位已知再加上第九位 和往前的长度已知，所以可以表示所有状态。

 所存在问题就是 10 1111 1111 此时加上1之后 会变成 11 0000 0000 但这样并处影响结果 如果之后操作都为加法，只有200次，他不可能影响到前面的1， 乘法相当于左移也不会影响。所以前面的1 不可能作为答案。

#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include <iostream>using namespace std;double d[210][260][2][260];int a[15];int main() {    int x, k, p, h = 0;    memset(d, 0, sizeof(d));    memset(a, 0, sizeof(a));    scanf("%d%d%d", &x, &k, &p);    while (x) {        a[h++] = x %2;        x /= 2;    }    int now = 0;    for (int i = 0; i < 8; ++i)        if (a[i])            now += (1 << i);    if (h < 9) {        d[0][now][0][0] = 1;    } else {        int cnt = 1;        for (int i = 9; i < h; ++i) {            if (a[i] != a[i - 1])                break;            cnt++;        }        d[0][now][a[8]][cnt] = 1;    }    for (int i = 0; i < k; ++i) {        for (int j = 0; j <= 255; ++j) {            for (int x = 0; x <= 250; ++x) {                if (j != 255) {                    d[i + 1][j + 1][0][x] += d[i][j][0][x] * (100 - p) / 100.0;                    d[i + 1][j + 1][1][x] += d[i][j][1][x] * (100 - p) / 100.0;                } else {                    d[i + 1][0][0][x] += d[i][j][1][x] * (100 - p) / 100.0;                    d[i + 1][0][1][1] += d[i][j][0][x] * (100 - p) / 100.0;                }                if (j & (1 << 7)) {                    d[i + 1][(j << 1) % 256][1][1] += d[i][j][0][x] * p / 100.0;                    d[i + 1][(j << 1) % 256][1][x + 1] += d[i][j][1][x] * p                            / 100.0;                } else {                    d[i + 1][(j << 1) % 256][0][1] += d[i][j][1][x] * p / 100.0;                    d[i + 1][(j << 1) % 256][0][x + 1] += d[i][j][0][x] * p                            / 100.0;                }            }        }    }    double sum=0;    for(int i=1;i<255;++i)    {        for(int j=0;j<2;++j)            for(int x=0;x<=250;++x)            {                int now=i;                int cnt=0;                while(now%2==0)                {                    cnt++;                    now/=2;                }                sum+=d[k][i][j][x]*cnt;            }    }    for(int x=0;x<=250;++x)        sum+=d[k][0][1][x]*8;    for(int x=0;x<=250;++x)        sum+=d[k][0][0][x]*(x+8);    printf("%.10lf\n",sum);    return 0;}
View Code


联系
我们