无聊的牛牛和羊羊

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m, s;
    scanf("%d%d", &n, &m);
    double f[m+1];
    s = n + m;
    double p = 1.0*s*(s-1)/2;
    for(int i=1;i<=m;i++){
        int x=i, y=s-i;
        double a = 1.0*y*(y-1)/2 / p;
        double b = 1.0*y*x / p;
        double c = 1.0*x*(x-1)/2 / p;
        f[i] += b*(f[i-1]+1);
        if(i>1)
            f[i] += c*(f[i-2]+1);
        f[i] += a;
        f[i] /= (1-a);
    }
    printf("%.1lf\n", f[m]);
    return 0;
}

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

double roundk(double num, int k) {
    return round(num * pow(10, k)) / pow(10, k);
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    int s = n + m;
    double f0 = 0, f1 = s / 2.0;
    for(int k = 2; k <= m; k++) {
        double cur = s * (s - 1) / (1.0 * k * (2 * s - k - 1)) + 2 * (s - k) * 1.0 / (2 * s - k - 1) * f1 + (k - 1) * 1.0 / (2 * s - k - 1) * f0;
        f0 = f1;
        f1 = cur;
    }
    printf("%.1f\n", roundk(f1, 1));
    return 0;
}

本题考察递推公式，设总共有s个0,1(s >= 2)，每次从其中随机选出2个，将这两个数中的1变成0，试求平均多少次操作后，s个数全部变成0.

当s个数中有k个1时，设平均需要f(k)次操作使得s个数全部变成0.一次操作后有3种可能性，即k --> k, k --> k - 1, k --> k - 2.分别表示取出了00， 01或10,11.这三种情况的概率分别为C(s - k, 2)/C(s, 2), (s - k) * k / C(s, 2), C(k, 2)/C(s, 2). 由此可以得到f(k)的递推公式.

f(k) = 1 + C(s - k, 2) / C(s, 2) f(k) + (s - k) k / C(s, 2) f(k - 1) + C(k, 2) / C(s, 2) f(k - 2)

化简此递推公式，即得到k到k-1，k-2的递推公式。当k=1时，是特殊情况，由分析可以得到f(1) = f(0) + s / 2, f(0) = 0.综上得解.

def fun(n, m):
    if m <= 0:
        return 0
    elif m == 1:
        return (n + m) / 2
    else:
        s = ((m + n) * (m + n -1)) / 2
        m_2 = m * (m - 1) / 2
        m_1 = m
        n_1 = n
        n_2 = n * (n - 1) / 2
        fz = 1 + ((m_2 * fun(n+2, m - 2))/ s) + ((m * n * fun(n+1, m - 1)) / s)
        fm = (1 - (n_2 / s))
        sum = fz/fm
        return sum

if __name__ == "__main__":
    n, m = map(int, input().split())
    print(round(fun(n, m),1))

未能在规定时间内运行结束，可以怎么改呢

	const readline=require('readline');



	const rl=readline.createInterface({



	input:process.stdin,



	output:process.stdout 



	})



	var mark=new Array();



	var result=new Array();



	rl.on("line",function(line){



	var arr=line.split(' ');



	var n=parseInt(arr[0]);



	var m=parseInt(arr[1]);



	for(var i=0;i<100;i++)



	{



	mark[i]=new Array();



	result[i]=new Array();



	for(var j=0;j<100;j++)



	{



	mark[i][j]=false;



	result[i][j]=0;



	}



	}



	var time=DFS(n,m);



	console.log(time.toFixed(1));



	process.exit(0);



	});



	function DFS(n,m){



	if(m<=0){



	return 0;



	}



	if(mark[n][m]===true)



	{



	return result[n][m];



	}



	var p1=n*(n-1)/((n+m)*(n+m-1));



	var p2=2*n*m/((n+m)*(n+m-1));



	var p3=m*(m-1)/((n+m)*(n+m-1));



	result[n][m]=(1+p2*DFS(n+1,m-1)+p3*DFS(n+2,m-2))/(1-p1);



	mark[n][m]=true;



	return result[n][m];



	}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strs = br.readLine().split(" ");
        int n = Integer.parseInt(strs[0]), m = Integer.parseInt(strs[1]);

        int total = n + m;
        double[] f = new double[m + 1];
        f[0] = 0;
        f[1] = total / 2.0;

        double s = total * (total - 1) / 2.0;
        for (int i = 2; i <= m; i++) {
            double tmp = total - i;
            double p1 = tmp * (tmp - 1) / 2.0 / s;
            double p2 = tmp * i / s;
            double p3 = i * (i - 1) / 2.0 / s;
            f[i] = (1 + p2 * f[i - 1] + p3 * f[i - 2]) / (1 - p1);
        }
        System.out.println(String.format("%.1f", f[m]));
    }
}

#include<stdio.h>
double f[100];
int main()
{
    int yes,no,all;
    scanf("%d%d",&yes,&no);
    all=yes+no;
    double pos=(double)all*(all-1)/2;
    for(int i=1;i<=no;i++)
    {
        int n=i,y=all-i;
        double c1=((double)y*(y-1)/2)/pos;
        double c2=(double)y*n/pos;
        double c3=((double)n*(n-1)/2)/pos;
        f[i]+=c2*(f[i-1]+1);
        if(i>=2) f[i]+=c3*(f[i-2]+1);
        f[i]+=c1;
        f[i]=f[i]/(1-c1);
    }
    printf("%.1lf",f[no]);
    return 0;
}
//列出公式后计算就好了

#include<stack>
#include<algorithm>
#include <iostream>
#include <iomanip>

using namespace std;
#define maxn 55
float dp[maxn];
int n,m;
float p1(int x,float deno){
    return (n+x)*(m-x) / deno;
}
float p2(int x,float deno){
    return (m-x)*(m-x-1)/2.0f/deno;
}
float p3(int x,float deno){
    return (n+x)*(n+x-1)/2.0f/deno;
}
int main(){

    while(cin >> n >> m){
        float deno = (n+m)*(n+m-1) / 2.0f;
        for(int i = 0;i < maxn;i ++){
            dp[i] = 0.0f;
        }
        for(int i = m-1;i >=0;i --){
            dp[i] += (dp[i+1]+1)*p1(i,deno) + p3(i,deno);
            if(i+2 <=m){
                dp[i] += p2(i,deno) * (dp[i+2] + 1);
            }
            dp[i] /= (1-p3(i,deno));
        }
        cout << setiosflags(ios::fixed) << setprecision(1) << dp[0] << endl;
    }
    return 0;
}