HDU5159 – Card(找规律)

题目链接：HDU5159

【题意】桌子上有a张牌，每张牌从1到a编号，编号为i(1<=i<=a)的牌上面标记着分数i , 每次从这a张牌中随机抽出一张牌，然后放回，执行b次操作，记第j次取出的牌上面分数是 S j  , 问b次操作后不同种类分数之和的期望是多少。

【分析】 数学没学好公式不会推，比赛的时候就找到规律了，但是要高精度又带小数，想到用JAVA写，但是好长时间没用JAVA了，导致来不及写出来就结束比赛了；讲下规律，写了个暴力代码发现：

答案就是所有排列中不同的数的和sum/排列总数cnt

cnt很容易得出就是x^b;

打表发现1~x每个数出现的次数都是相同的p，而p=x^b-(x-1)^b；

这样sum就是(1+x)*x/2 * p;

求出了sum和cnt答案就是sum/cnt了

但是sum和cnt超出double范围了，只能用JAVA的BigDecimal，还需要预处理不然超时；

【AC CODE】8065ms

import java.util.*;
import java.math.BigDecimal;
import java.io.*;
import java.text.DecimalFormat;

public class Main{
    static BufferedReader in = new BufferedReader(new InputStreamReader

(System.in));
    static BufferedWriter out = new BufferedWriter(new OutputStreamWriter

(System.out));
    static double[][] ans = new double[100000+10][6];
    static BigDecimal[] cnt = new BigDecimal[6];
    static DecimalFormat df = new DecimalFormat("0.000");
    public static void main(String args[])throws Exception{
        BigDecimal one = BigDecimal.valueOf(1);
        BigDecimal two = BigDecimal.valueOf(2);
        BigDecimal buf = BigDecimal.valueOf(0);
        for(int i = 1; i <= 5; i++) {
            cnt[i] = one;
            ans[1][i] = 1.0;
        }
        cnt[0] = one;
        BigDecimal oc, p;
        for(int i = 2; i <= 100000; i++){
            BigDecimal I = BigDecimal.valueOf(i);
            for(int j = 1; j <= 5; j++){
                oc = cnt[j];
                cnt[j] = cnt[j-1].multiply(I);
                cnt[j].setScale(10, BigDecimal.ROUND_HALF_UP);//不加容易超时
                p = cnt[j].subtract(oc);
                buf = I.add(one).multiply(I);
                buf = buf.divide(two,10,BigDecimal.ROUND_HALF_UP);
                buf = buf.multiply(p);
                buf = buf.divide(cnt[j],10,BigDecimal.ROUND_HALF_UP);
                ans[i][j] = buf.doubleValue();
            }
        }
        /*============ =============*/
        int t = Integer.parseInt(in.readLine());
        int ct = 1;
        for (int i = 0; i < t; i++){
            StringTokenizer st = new StringTokenizer(in.readLine());
            int x = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            System.out.print("Case #");
            String num = df.format(ans[x][b]);
            System.out.println(ct + ": " + num);
            ct++;
        }
    }
}

【附上暴力打表的C++代码】

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <map>
//#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 100000+10;
int a,b, sum, cnt, num[10];
bool vis[MAXN];
int time[MAXN];

void dfs(int p)
{
	if(p == b)
	{
		int tol = 0;
		rep(i,0,b)
		{
			if(!vis[num[i]])
				vis[num[i]] = true, tol += num[i], time[num[i]]++;
		}
		rep(i,0,b) vis[num[i]] = false;
		sum += tol;
		cnt++;
		return;
	}
	repe(i,1,a)
	{
		num[p] = i;
		dfs(p+1);
	}
}
int main()
{
#ifdef SHY
	freopen("e:\\1.txt", "r", stdin);
#endif
	int t, count = 0;
	scanf("%d%*c", &t);
	while(t--)
	{
		scanf("%d %d%*c", &a, &b);
		sum = cnt = 0;
		int sum2 = 0;
		clc(time,0);
		dfs(0);
		printf("%d %d\n", a,b);
		repe(i,1,a)
		{
			printf("%d) %d\n", i,time[i]);
			//sum2 += time[i]*i;
			//printf("%d\n", sum2);
		}
		int p = pow(1.0*a,1.0*b)-pow(1.0*(a-1),1.0*b);
		printf("== %d ==\n", p);
		printf("Case #%d: %.3lf\n", ++count, (double)sum/((double)cnt));
	}
	return 0;
}
/*
15
1 1
1 2
1 3
1 4
1 5
2 1
2 2
2 3
2 4
2 5
3 1
3 2
3 3
3 4
3 5
*/