DZY Loves Balls
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 860 Accepted Submission(s): 467
Problem Description
There are n black balls and m white balls in the big box.Now, DZY starts to randomly pick out the balls one by one. It forms a sequence S. If at the i-th operation, DZY takes out the black ball, Si=1, otherwise Si=0.DZY wants to know the expected times that '01' occurs in S.
Input
The input consists several test cases. ( TestCase≤150)The first line contains two integers, n, m(1≤n,m≤12)
Output
For each case, output the corresponding result, the format is p/q(p and q are coprime)
Sample Input
1 1 2 3
Sample Output
1/2 6/5
Hint
Case 1: S='01' or S='10', so the expected times = 1/2 = 1/2 Case 2: S='00011' or S='00101' or S='00110' or S='01001' or S='01010' or S='01100' or S='10001' or S='10010' or S='10100' or S='11000', so the expected times = (1+2+1+2+2+1+1+1+1+0)/10 = 12/10 = 6/5
Source
题解:特判了下12 12以及 11 12 和 12 11..其余的话暴力枚举就行了..
#include#include #include #include #include using namespace std;typedef long long LL;int n,m,p,q;int ans[30];void dfs(int step,int a,int b){ if(a>m||b>n) return; ///剪枝,不然TLE if(a==m&&b==n){ q++; int k = 0; for(int i=0;i
改成了标记前结点,快了许多。
#include#include #include #include #include using namespace std;typedef long long LL;int n,m,p,q;void dfs(int a,int b,int pre,int num){ if(a>n||b>m) return; if(a==n&&b==m){ p+=num; q++; return; } if(b<=m) dfs(a,b+1,0,num); if(a<=n){ if(pre==0) dfs(a+1,b,1,num+1); else dfs(a+1,b,1,num); }}int gcd(int a,int b){ return b==0?a:gcd(b,a%b);}int main(){ while(scanf("%d%d",&n,&m)!=EOF){ p = q = 0; dfs(0,0,-1,0); int d = gcd(p,q); printf("%d/%d\n",p/d,q/d); } return 0;}