加载中…
个人资料
Wideas
Wideas
  • 博客等级:
  • 博客积分:0
  • 博客访问:11,923
  • 关注人气:24
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

北京网络赛赛后总结及K题题解

(2011-09-18 21:50:32)
标签:

北京

题目

概率

格子

杂谈

题目地址:

看完题目很容易想到直接将期望计算方法为 ∑p[step]*step,p[step]表示走step步的概率。如果这么做的话状态过多,处理困难。

在思考这道问题的时候,可以先看一下问题:
n道题目,每道题目有一个AC率,求AC题数的期望。(ans = ∑Pi,任意两道题目不相关)

最后,每到一个格子,无论是从先前是那个格子过来,都相当于多走一步,所以最终答案为∑p[i][j]。

设p[i][j]为走到状态为j的第i个格子的概率。从p[i][j]推导p[i + step][k]的概率很容易计算,只要从第i步不能走到[i + 1,i + step - 1]中任意一个位置即可,具体概率还要由i、j确定。

赛后总结:开场卡了G题,队员间交流不流畅,K题最后半小时没写完有些遗憾。


附上代码:
#include<iostream>
using namespace std;

const int maxn = 2000 + 10;
double p[maxn * 2][4];
double ans[maxn * 2][4];
double f[maxn * 2][15];
int n, a, b;

void init() {
    memset(p, 0, sizeof (p));
    memset(f, 0, sizeof (f));

    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 4; j++)
            cin >> p[i][j];
    p[0][3] = 1;
    for (int i = 1; i <= n; i++)
        for (int k = 0; k < 15; k++)
            for (int l = 0; l < 4; l++)
                if ((k >> l)& 1) f[i][k] += p[i][l];
    for (int i = n + 1; i < maxn * 2; i++) p[i][3] = 1;
}

void solve() {
    memset(ans, 0, sizeof (ans));
    ans[0][3] = 1;
    double P;
    for (int i = 0; i <= n; i++)
        for (int j = 1; j < 4; j++) {
            P = 1.0;
            for (int step = a; step <= b; step++) {
                for (int k = 1; k < 4; k++) {
                    if (j != k || (j == k && k == 3))
                        ans[i + step][k] += ans[i][j] * P * p[i + step][k];
                }
                if (j == 1) P = P * f[i + step ][3];
                if (j == 2) P = P * f[i + step ][5];
                if (j == 3) P = P * f[i + step ][1];
            }
        }
    double cnt = 0;
    for (int i = 1; i <= n + b; i++) 
        for (int j = 0; j < 4; j++)
            cnt += ans[i][j];
    printf("%.8lf\n", cnt);
}

int main() {
    int T;
    cin >> T;
    for (int i = 1; i <= T; i++) {
        init();
        solve();
    }
    return 0;
}

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
后一篇:1000米
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

    后一篇 >1000米
      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有