A - Arcade Game Gym - 100814A (概率思维题)

题目链接:https://cn.vjudge.net/contest/285964#problem/A

题目大意:每一次给你你一个数,然后对于每一次操作,可以将当前的数的每一位互换,如果互换后的数小于等于原来的数,那么停止操作,如果大于原来的数,则继续操作,到达当前这些数字能租成的最大的数的时候停止,然后问你能组成最大的数概率是多少?

具体思路:对于当前的数,我们先计算出这个比这个数大的有多少个,这个过程可以通过全排列的函数来进行计算。然后再计算一下当前的位数能构成的数的个数是多少,然后就开始求概率了。假设比当前的数大的有三个,那么概率计算就是 C(2,0)*(1/3)+C(2,1)*(1/3)*(1/3)+C(2,2)*(1/3)*(1/3)*(1/3).解释一下为什么是C(2,1),我们假设当前的关系是1>2>3,对于1,我们既可以通过2跳过去,还可以通过3跳过去,所以是C(2,1)。然后再开始化简式子(直接组合数会超时,,)对于上面的式子,我们把(1/3)提取出来,然后就变成了(1/3)*(1+2*(1/3)+(1/3)*(1/3)),然后就是(1/q)*(1+1/q)^(n-1).

AC代码:

 #include<iostream>
#include<cmath>
#include<stdio.h>
#include<algorithm>
using namespace std;
# define ll long long
const int maxn = 2e4+;
int f[maxn];
int a[maxn];
int main(){
// cout<<(1.0/6.0)*(1.0+1.0/6.0)<<endl;
int T;
f[]=;
for(int i=;i<=;i++){
f[i]=f[i-]*i;
}
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
int num=;
while(n){
a[++num]=n%;
n/=;
}
for(int i=;i<=num/;i++){
swap(a[i],a[num-i+]);
}
int ans=;
while(next_permutation(a+,a+num+)){
ans++;
}
if(ans==){
printf("0.000000000\n");
continue;
}
double tot=1.0/(f[num]*1.0);
//cout<<f[num]<<endl;
double d=1.0/(f[num]*1.0);
double tmp=1.0+d;
//cout<<tmp<<" "<<tot<<endl;
for(int i=;i<ans;i++){
tot=tot*tmp;
}
printf("%.9lf\n",tot);
}
return ;
}
上一篇:MongoDB设置访问权限、设置用户


下一篇:ajax参数设置略解