【Codeforces 453A】Little Pony and Expected Maximum

题目传送门:http://codeforces.com/problemset/problem/453/A

这个题目,为什么我又感觉很神QAQ
题解看这里:http://www.cnblogs.com/qscqesze/p/4411069.html

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdio>
#include<cmath>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

int n,m;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret*f;
}

int main(){
	m = read(); n = read(); 
	double p = 1.0 - pow((double)(m-1)/m,n), vout = 0;
	for (int i=1;i<=m;i++) vout += (pow((double)i/m,n)-pow((double)(i-1)/m,n))*i;
	printf("%.10lf\n",vout);
	return 0;
}

又一次看到这个图了,蜜汁喜欢QAQ
o_690e2a0828381f3056038f33a8014c086e06f030

【BZOJ 2318】[SPOJ 4060] game with probability Problem

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2318

网上绝大部分证明完全没有说清楚好吗? (╯‵□′)╯︵┻━┻
只有这一份题解才稍微正常一点:http://codeplay0314.coding.me/2015/07/10/BZOJ2318/
本地备份:http://oi.cyo.ng/wp-content/uploads/2016/08/12345687856456754.png
不过这一题的推式子还是很神的,有一定参考价值。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdio>
#include<cmath>
#include<bitset>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 1000+9;
const int LIM = 1000;

int n;
double f[N],g[N],p,q;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret*f;
}

int main(){
	int T=read(); while (T--) {
		n = min(read(), LIM); scanf("%lf%lf",&p,&q);
		f[0] = 0; g[0] = 1;
		for (int i=1;i<=n;i++) {
			if (f[i-1] > g[i-1]) p = 1 - p, q = 1 - q;
			f[i] = (p*g[i-1] + (1-p)*q*f[i-1]) / (1 - (1-p)*(1-q));
			g[i] = (q*f[i-1] + (1-q)*p*g[i-1]) / (1 - (1-p)*(1-q));
			if (f[i-1] > g[i-1]) p = 1 - p, q = 1 - q;	
		}
		printf("%.6lf\n",f[n]);
	}
	return 0;
}

值得一提的是,我最开始定义的g[i]为胜i个石子时,Bob先走,Bob的胜算是多少
这样写出来的方程是: \(\begin{array}{l}
{a_i} = \left\{ \begin{array}{l}
p(1 – {b_i}) + (1 – p)(1 – {b_{i – 1}}),{b_i} < {b_{i - 1}}\\ p(1 - {b_{i - 1}}) + (1 - p)(1 - {b_i}),{b_i} > {b_{i – 1}}
\end{array} \right.\\
{b_i} = \left\{ \begin{array}{l}
q(1 – {a_i}) + (1 – q)(1 – {a_{i – 1}}),{a_i} < {a_{i - 1}}\\ q(1 - {a_{i - 1}}) + (1 - q)(1 - {a_i}),{a_i} > {a_{i – 1}}
\end{array} \right.
\end{array}\)
但你会发现,这么推,推不出来QAQ
仔细想一想为什么,我觉得是f[i]与(1-f[i])混用了吧?

【Codeforces 442B】Andrey and Problem

题目传送门:http://codeforces.com/contest/442/problem/B
官方题解:http://codeforces.com/blog/entry/12739

此题真的是妙啊! 奥妙重重.jpg
考虑当前已经有一个集合了,不失望的概率是f,设g=Π(1-其中所有人的p)
如果考虑是否加入第i个人,不难得出必须满足一下等式:
\(f \cdot (1 – p) + g \cdot p > f\)
化简得到,如果有优化的可能,则 g > f
然后来比较人选i和人选j
如果i优于j,则有以下不等式:
\(f \cdot (1 – {p_i}) + g \cdot {p_i} > f \cdot (1 – {p_j}) + g \cdot {p_j}\)
化简得到\({p_i} > {p_j}\)
又因为加入顺序明显不影响答案,所以排序之后从大到小贪心即可

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdio>
#include<cmath>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 100+9;
const double EPS = 1e-8;

int n;
double p[N],f,g=1;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret*f;
}

int main(){
	n = read(); for (int i=1;i<=n;i++) scanf("%lf",&p[i]);
	sort(p+1,p+1+n); if (abs(p[n]-1) < EPS) {cout<<1; exit(0);}
	for (int i=n;i;i--) {
		double tmp = f*(1-p[i]) + g*p[i];
		if (tmp > f) f = tmp, g *= (1-p[i]);
		else break;
	} printf("%.10lf",f);
	return 0;
}

【BZOJ 1426】收集邮票

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1426

这货,我式子推得很奇怪QAQ
也不知道为什么是对的QAQ

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdio>
#include<cmath>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 10000+9;

int n;
double f[N],g[N];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret*f;
}

int main(){
	n = read(); f[n] = g[n] = 0;
	for (int i=n-1;~i;i--) f[i] = (double)n/(n-i) + f[i+1];
	for (int i=n-1;~i;i--) g[i] = f[i]*n/(n-i) + g[i+1];
	printf("%.2lf",g[0]);
	return 0;
}

【Codeforces 698C】LRU

题目传送门:http://codeforces.com/problemset/problem/698/C

这个题目嘛,貌似第一眼都会想到状压?然后内存就爆炸了。
比赛的时候果断弃疗…….

不过,这道题真的出得很好欸!做了以后有一种神清气爽的感觉!o(* ̄▽ ̄*)ブ
具体来说,就是倒着来考虑:一个一个往里加,直到装满
详见官方题解:http://codeforces.com/blog/entry/46148

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

const int MAXN = 2000000;
const double EPS = 1e-12;

int n,k,cnt[MAXN],tot;
double f[MAXN],p[MAXN],vout[MAXN],mst[MAXN];

int main(){
	cin>>n>>k; f[0] = 1; mst[0] = 1;
	for (int i=1;i<=n;i++) {cin>>p[i]; if (p[i] > EPS) tot++;} tot = min(tot, k);
	for (int i=1,lim=1<<n;i<lim;i++) cnt[i] = __builtin_popcount(i);
	for (int i=0,lim=1<<n;i<lim;i++) if (cnt[i] < k) for (int j=1;j<=n;j++) 
		if ((i & (1<<(j-1))) == 0) f[i|(1<<(j-1))] += f[i]*p[j]/mst[i], mst[i|(1<<(j-1))] = mst[i] - p[j];
	for (int i=1,lim=1<<n;i<lim;i++) if (cnt[i] == tot && f[i] > EPS) 
		for (int j=1;j<=n;j++) if (i & (1<<(j-1))) vout[j] += f[i];
	for (int i=1;i<=n;i++) printf("%.16lf ",vout[i]);
	return 0;
}

【BZOJ 3450】[Tyvj 1952] Easy

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3450
数据生成器:http://paste.ubuntu.com/22437621/

额,这个题,因为之前做过一道维护平方的数据结构题目
所以没有采用全期望公式,而是用的“概率*值”的方式
之前脑抽了,写了一个用线段树的版本:http://paste.ubuntu.com/22437306/
结果写完以后,发现其实不用线段树QAQ,O(n)扫一遍就好

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

const int MAXN = 300000+9;

int n; char pat[MAXN];
long double vout,T1,T2,T3;

int main(){
	scanf("%d\n%s",&n,pat+1);
	for (int i=1;i<=n;i++) {
		if (pat[i] == 'o') {
			if (pat[i-1] == 'o') continue;
			else { 
				long double p = pat[i-1]=='?'?0.5:1;
				T1 += p*i*i; T2 += p*i; T3 += p;
			}
		} else if (pat[i] == 'x') {
			vout += T1 - T2*2*i + T3*i*i;
			T1 = T2 = T3 = 0; 
		} else {
			vout += (T1 - T2*2*i + T3*i*i)*0.5;
			T1 /= 2; T2 /= 2; T3 /= 2; 
			if (pat[i-1] == 'o') continue;
			long double p = pat[i-1]=='?'?0.25:0.5;
			T1 += p*i*i; T2 += p*i; T3 += p;		
		}
	} vout += T1 - T2*2*(n+1) + T3*(n+1)*(n+1);
	printf("%.4lf\n",(double)vout);
	return 0;
} 

hzwer就是用全期望公式搞的,那样的话看起来比较自然一点:
http://hzwer.com/2838.html

【BZOJ 1415】[Noi2005] 聪聪和可可

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1415
数据生成器:http://paste.ubuntu.com/22417252/

论文题,记忆化深搜
我在处理该去哪时,用的三方的floyd
然而hzwer告诉我,平方的bfs就好QAQ,反正没有T,我就不改啦!(づ ̄ 3 ̄)づ

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

const int MAXN = 1000+9;
const int INF = 1000000;
const double sta = -0.5;

int n,m,C,M,d[MAXN][MAXN],to[MAXN][MAXN],cnt[MAXN];
double ans[MAXN][MAXN];

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret;
}

inline void Floyd(){
	for (int k=1;k<=n;k++) for (int i=1;i<=n;i++) if (d[i][k] < INF) 
		for (int j=1;j<=n;j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
	
	for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) for (int k=1;k<=n;k++) 
		if (d[i][k] == 1 && d[k][j] == d[i][j]-1) {to[i][j] = k; break;}
	for (int i=1;i<=n;i++) to[i][i] = i;
}

double Get_Ans(int u, int v){
	if (ans[u][v] > sta) return ans[u][v];
	else {
		if (to[to[u][v]][v] != v) {
			ans[u][v] = Get_Ans(to[to[u][v]][v],v)+1;
			for (int i=1;i<=n;i++) if (d[v][i] == 1) ans[u][v] += Get_Ans(to[to[u][v]][v],i)+1;
			return ans[u][v] /= cnt[v];
		} else return ans[u][v] = 1;
	}
}

int main(){ 
	n = read(); m = read(); C = read(); M = read();
	for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) d[i][j] = INF, ans[i][j] = -1;
	for (int i=1;i<=n;i++) d[i][i] = 0, ans[i][i] = 0, cnt[i] = 1;
	for (int i=1,a,b;i<=m;i++) cnt[a = read()]++, cnt[b = read()]++, d[a][b] = d[b][a] = 1;
	Floyd(); printf("%.3lf\n",Get_Ans(C,M));
	return 0;
} 

【COGS 1478】麻球繁衍

题目传送门:http://cogs.top/cogs/problem/problem.php?pid=1487

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

const int MAXN = 1000+9;

int n,m;
double w,p[MAXN],vout;

inline int read(){
	char c=getchar(); int buf=0,f=1;
	while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
	return buf*f;
}

int main(){
	freopen("tribbles.in","r",stdin);
	freopen("tribbles.out","w",stdout);
	for (int T=1,TT=read();T<=TT;T++){
		n = read(), w = read(); m = read(); 
		for (int i=0;i<n;i++) scanf("%lf",&p[i]);
		vout = p[0];
		for (int k=2;k<=m;k++) {
			double tmp = 0;
			for (int i=0;i<n;i++) tmp += p[i]*pow(vout,i);
			vout = tmp; 
		}
		printf("Case #%d: %.7lf\n",T,pow(vout, w));
	} 
	return 0;
} 

【COGS 1489】玩纸牌

题目传送门:http://cogs.top/cogs/problem/problem.php?pid=1489

这一道题真的是坑啊!
总体思路肯定是:先DP出每天完成计划的概率,然后再根据期望的定义来算

然后就是坑点了。
不难得出,转移方程:\(p(i,j) = p(i – 1,j – 1) \cdot {p_{win}} + p(i,j – 1) \cdot {p_{lose}}\)
然而这是错的!因为如果i/j满足条件的话,这个货就会立即停止,即i/j>a/b的概率为0
妈妈啊!wa了好久!

不过这题还是学了一点东西:
1. 枚举的时候,遇到分数,为了避免误差可以变除为乘
2. 全期望公式,不仅可以用来装逼,还可以用来化简式子,避免误差
比如这个题目,使用全期望公式,可以化到:\(ans = \frac{1}{{lose}}\)

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

const int MAXN = 1000+9;
const double EPS = 1e-15;

double t1[MAXN],t2[MAXN],win,lose,*p1,*p2;
int n,a,b;

inline double cal(double ty){
	memset(t1,0,sizeof(t1));
	memset(t2,0,sizeof(t2));
	p1 = t1; p2 = t2; p2[0] = 1;
	
	for (int j=1;j<=n;j++) {
		for (int i=0;i*b<=a*j;i++) p1[i] = p2[i]*lose + ((i)?p2[i-1]*win:0);
		swap(p1, p2);
	}
	
	double ret = 0;
	for(int i=0;i*b<=a*n;i++) ret += p2[i];
	return ret;
}

int main(){
    freopen("expected.in","r",stdin);
    freopen("expected.out","w",stdout);
	int TT; cin>>TT;
	for (int T=1;T<=TT;T++){
		scanf("%d/%d %d",&a,&b,&n);
		win = (double)a/b; lose = 1-win;
		lose = cal(win); win = 1.0 - lose;
		double  w = 1, vout = 0; int day = 1;
		while (w > EPS) {
			vout += w*lose*day;
			w *= win; day++;
		}
		printf("Case #%d: %d\n",T,(int)(vout+0.05));
	}
	return 0;
} 

【BZOJ 1076】[SCOI2008] 奖励关

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1076
数据生成器:http://paste.ubuntu.com/20577780/

概率DP第一题! 撒花~ *★,°*:.☆\( ̄▽ ̄)/$:*.°★*
虽然想了很久很久,做了一个下午,但彻底懂啦!

设f[i][k]为状态为i,走了k步时到终点的期望得分
根据全期望公式,得到以下转移方程:
\(f[i][k] = \sum\limits_{j = 1}^n {{p_j} \cdot \max ((f[i|{2^{j – 1}}][k + 1] + val[j]) \cdot ((i\& \lim [j]) = = \lim [j]),f[i][k + 1])}\)
其中直接取max的正确性在于:只要是合法的状态,那么最后都会被计入答案
然后根据DAG的性质,倒着递推即可。

但今天想了一下午,不仅相同了这个,还有更重要的收获:
为什么不能正着推?
不是网上说的会推出无效的状态,而是:
题目上只给了\({P_{(u \to v)}}\),而没有给\({P_{(v \to u)}}\)
而且\({P_{(v \to u)}}\)你还算不出来,因为分母不确定(受转移的影响)。
所以你只能按照上面的方式列方程,进而只能倒推

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

const int MAXN = 80000;
const int KK = 100+9;

int val[MAXN],n,K,ty[MAXN],MX,lim[MAXN];
double f[KK][MAXN];

int main(){
	scanf("%d%d",&K,&n);
	for (int i=1;i<=n;i++) ty[i] = 1<<(i-1);
	for (int i=1,tmp;i<=n;i++) {
		scanf("%d",&val[i]);
		while (scanf("%d",&tmp) && tmp)
			lim[i] |= ty[tmp];
	}
	MX = ty[n]*2-1;
	
	for (int k=K;k;k--) for (int i=0;i<=MX;i++) for (int j=1;j<=n;j++) 
		f[k][i] += max((f[k+1][i|ty[j]]+val[j])*((i&lim[j]) == lim[j]),f[k+1][i])/n;
	
	printf("%.6lf",f[1][0]);
	return 0;
}	

【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;
}