今天zoj月赛。
回来都3点了。。看了下E搜了下，TLE了，就看B。。。
B就是，给你骰子n，m。求n个骰子的加和大于m个骰子加和的概率。
自己用笔模拟了半天。。。决定用循环。
8个循环 嘻嘻。。。
虽然是结束后交的。。。那个double的好纠结。。。中间还溢出了。。只能加一下除一下。。。
然后经lzs同学提醒。。可以用递归哈。。。又写了个递归版的。。
循环版的0ms，递归的20ms。。。
其实这个循环蛮好看的是吧~~~
a[i][j] 意思是 i个骰子组成加和为j的次数。
#include <cstdio> #include <cstdlib> #include <iostream> #include <string.h> #include <queue> #include <limits.h> #include <math.h> using namespace std; int main() { int a[10][100]; memset(a,0,sizeof(a)); for(int i=1; i<=6; i++) for(int k=1; k<=6; k++) for(int j=1; j<=6; j++) for(int l=1; l<=6; l++) for(int m=1; m<=6; m++) for(int o=1; o<=6; o++) for(int p=1; p<=6; p++) for(int h=1; h<=6; h++) a[8][i+k+j+l+m+o+p+h]++; for(int k=1; k<=6; k++) for(int j=1; j<=6; j++) for(int l=1; l<=6; l++) for(int m=1; m<=6; m++) for(int o=1; o<=6; o++) for(int p=1; p<=6; p++) for(int h=1; h<=6; h++) a[7][k+j+l+m+o+p+h]++; for(int j=1; j<=6; j++) for(int l=1; l<=6; l++) for(int m=1; m<=6; m++) for(int o=1; o<=6; o++) for(int p=1; p<=6; p++) for(int h=1; h<=6; h++) a[6][j+l+m+o+p+h]++; for(int l=1; l<=6; l++) for(int m=1; m<=6; m++) for(int o=1; o<=6; o++) for(int p=1; p<=6; p++) for(int h=1; h<=6; h++) a[5][l+m+o+p+h]++; for(int m=1; m<=6; m++) for(int o=1; o<=6; o++) for(int p=1; p<=6; p++) for(int h=1; h<=6; h++) a[4][m+o+p+h]++; for(int o=1; o<=6; o++) for(int p=1; p<=6; p++) for(int h=1; h<=6; h++) a[3][o+p+h]++; for(int p=1; p<=6; p++) for(int h=1; h<=6; h++) a[2][p+h]++; for(int h=1; h<=6; h++) a[1][h]++; int n,m; while( ~scanf("%d%d",&n,&m) ) { int sum = 0; double ans = 0.0; if( n <= 1 ) goto end; for(int i=m; i<=m*6; i++) { sum = 0; for(int y=i+1; y<=n*6; y++) sum += a[n][y]; ans += sum*1.0*a[m][i]/pow(6.0,m); } end:; printf("%.16lf/n",ans/pow(6.0,n)); } return 0; }
递归版
#include <cstdio> #include <cstdlib> #include <iostream> #include <string.h> #include <queue> #include <limits.h> #include <math.h> using namespace std; int a[10][100],i; void DFS(int x,int sum) { if( x == 0 ) { a[i][sum]++; return ; } for(int k=1; k<=6; k++) DFS(x-1,sum+k); } int main() { memset(a,0,sizeof(a)); for(i=1; i<=8; i++) DFS(i,0); int sum,n,m; while( ~scanf("%d%d",&n,&m) ) { double ans = 0.0; if( n <= 1 ) goto end; for(int i=m; i<=m*6; i++) { sum = 0; for(int y=i+1; y<=n*6; y++) sum += a[n][y]; ans += sum*1.0*a[m][i]/pow(6.0,m); } end:; printf("%.16lf/n",ans/pow(6.0,n)); } return 0; }
