首页 > 代码库 > Coupons

Coupons

2024-07-13 09:43:19   212人阅读

uva10288:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1229

题意：有一种盒子，盒子一面会随机放一种卡片，现在要集齐n种卡片，问要买多少个盒子。

题解：假如说n==2，那么第一次买，肯定可以得到一种新的卡片，第二次买得到新的卡片的概率是1/2，也就是说你那买2包才能得到新的卡片，所以期望值是1+2==3；如果n==3的话，第一次概率是1，第二次是2/3,也就是说第二次要买3/2包才能得到一种新的卡片，第三次是1/3，所以要买3包，所以总的期望是1+3/2+3;一次类推，可以得到期望：n/1+n/2+n/3+.....+n/n.还有题目中的输出格式，用log(a)/log(10)+1就可以得到a的位数。还有uva用的是lld，不是I64d

 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<set> 6 #include<cmath> 7 using namespace std; 8 long long n,temp,a,b,ans; 9 long long gcd(long long a, long long b){10     if(b==0)11         return a;12     return gcd(b,a%b);13 }14 15 int main(){16    while(~scanf("%lld",&n)){17        a=1;b=1;ans=0;18        for(int i=2;i<=n;i++){19            a=a*i+b;20            b=b*i;21            temp=gcd(a,b);22            a/=temp;23            b/=temp;24        }25        a*=n;26        temp=gcd(a,b);27        a/=temp;28        b/=temp;29        ans=a/b;30         a=a%b;31         temp=gcd(a,b);32         a/=temp;33         b/=temp;34         int m,t;35          int s=(int)(log(b)/log(10)+1);36         m=t=(int)(log(ans)/log(10)+2);37         if(a==0)38             printf("%lld\n",ans);39         else{40             while(t--)printf(" ");41             printf("%lld\n",a);42             printf("%lld ",ans);43             while(s--)printf("-");44             printf("\n");45             while(m--)printf(" ");46             printf("%lld\n",b);47         }48 49    }50 }
View Code


联系
我们