【NOI六连测】[D3T1] 炉石

题目传送门:http://pan.baidu.com/s/1nvKqStz
离线版数据:http://paste.ubuntu.com/18386939/
数据传送门:http://pan.baidu.com/s/1i5fN2IT

首先,没玩过炉石的同学表示很受伤:考试的时候一直以为95颗星就算赢
其次,不会概率DP or 高斯消元的同学表示很受伤:因为要爆零啊!QAQ
好吧,高斯消元不会,所以来说一说lcr用的模拟吧:
设arr[i][j]表示走了k步后,位于当前有i颗星,已经连胜j场这个状态的概率
于是转移一下,再加上P>0.48保证了最多的步数就是1000多的样子
所以我们暴力转移1e5次的样子,基本上其他地方的DP值就为0了。
然后就是NOIP的模拟题水平的代码就可以了! *★,°*:.☆\( ̄▽ ̄)/$:*.°★*
哎,概率太弱不对,是完全不会
迟早是要找个时间好好学一学啊!

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 100;
const int T = 100000;

double win,lose,arr[MAXN][4],tmp[MAXN][4],ans;
int n;

int main(){
	freopen("hearthstone.in","r",stdin);
	freopen("hearthstone.out","w",stdout);
	scanf("%d%lf",&n,&win);
	lose = 1 - win;
	arr[96-n][0] = 1;
	for (int k=1;k<=T;k++){
		for (int i=0;i<=10;i++){
			tmp[i][0] += arr[i][0]*lose;
			tmp[i][0] += arr[i][1]*lose;
			tmp[i][0] += arr[i][2]*lose;
			tmp[i][0] += arr[i][3]*lose;
			tmp[i+1][1] += arr[i][0]*win;
			tmp[i+1][2] += arr[i][1]*win;
			tmp[i+2][3] += arr[i][2]*win;
			tmp[i+2][3] += arr[i][3]*win;
		}
		for (int i=11;i<=70;i++){
			tmp[i-1][0] += arr[i][0]*lose;
			tmp[i-1][0] += arr[i][1]*lose;
			tmp[i-1][0] += arr[i][2]*lose;
			tmp[i-1][0] += arr[i][3]*lose;
			tmp[i+1][1] += arr[i][0]*win;
			tmp[i+1][2] += arr[i][1]*win;
			tmp[i+2][3] += arr[i][2]*win;
			tmp[i+2][3] += arr[i][3]*win;
		}
		for (int i=71;i<=95;i++){
			tmp[i-1][0] += arr[i][0]*lose;
			tmp[i-1][0] += arr[i][1]*lose;
			tmp[i-1][0] += arr[i][2]*lose;
			tmp[i-1][0] += arr[i][3]*lose;
			tmp[i+1][1] += arr[i][0]*win;
			tmp[i+1][2] += arr[i][1]*win;
			tmp[i+1][3] += arr[i][2]*win;
			tmp[i+1][3] += arr[i][3]*win;
		}
		ans += (tmp[96][0]+tmp[96][1]+tmp[96][2]+tmp[96][3])*k; 
		memcpy(arr,tmp,sizeof(tmp));
		memset(tmp,0,sizeof(tmp));
	}
	printf("%.2lf\n",ans);
	return 0;
} 

22 thoughts to “【NOI六连测】[D3T1] 炉石”

  1. I’m really enjoying the design and layout of your site. It’s a very easy on the eyes which makes it much
    more pleasant for me to come here and visit more often.
    Did you hire out a developer to create your theme? Superb work!

  2. Sweet blog! I found it while surfing around on Yahoo News.
    Do you have any tips on how to get listed in Yahoo News?
    I’ve been trying for a while but I never seem to get there!
    Thanks

  3. great submit, very informative. I’m wondering why the opposite specialists of this sector
    don’t notice this. You must proceed your writing.
    I am sure, you have a huge readers’ base already!

  4. Hi my friend! I want to say that this post is awesome, nice written and come with approximately all vital infos.
    I’d like to peer more posts like this .

  5. Sweet blog! I found it while searching on Yahoo News.
    Do you have any suggestions on how to get listed in Yahoo
    News? I’ve been trying for a while but I never seem to get there!
    Many thanks

  6. I was very pleased to discover this page. I wanted to thank you for ones time for
    this particularly wonderful read!! I definitely liked every part of it and i also have
    you bookmarked to see new things in your website.

  7. Spot on with this write-up, I absolutely believe that this website needs far more attention. I’ll probably be returning to read through more, thanks for
    the info!

  8. Good day very cool site!! Guy .. Excellent .. Superb ..
    I will bookmark your website and take the feeds additionally?
    I am happy to seek out a lot of useful information here in the submit, we’d like work
    out extra techniques on this regard, thanks for sharing.
    . . . . .

  9. Hi! I know this is somewhat off topic but I was
    wondering if you knew where I could find a captcha plugin for
    my comment form? I’m using the same blog platform as yours and I’m having trouble finding one?

    Thanks a lot!

  10. continuously i used to read smaller articles or
    reviews that also clear their motive, and that is also happening with this article which I am
    reading here.

  11. Thanks for some other magnificent article. The
    place else could anybody get that kind of info in such a perfect
    manner of writing? I’ve a presentation next week,
    and I am at the look for such information.

Leave a Reply to quest bars cheap Cancel reply

Your email address will not be published. Required fields are marked *