luoguP1291 [SHOI2002]百事世界杯之旅

Date: Fri 02 November 2018
Updated: Fri 02 November 2018

In 5. OI.

Tags: OI

题目


假设有n个不同名字

先抽一次,必定抽出一个新的——ans+1

再抽第二次,这时有(n-1)/n的概率能抽到新的,所以期望抽n/(n-1)次能抽到新的——ans+n/(n-1)

再抽第三次,这时有(n-2)/n的概率能抽到新的,所以期望抽n/(n-2)次能抽到新的——ans+n/(n-2)

……

以此类推,答案是1+n/(n-1)+n/(n-2)+n/(n-3)+...+n/1

答案也就是n(1+1/2+1/3+1/4+..1/n)


另外这题的输出答案方式很清奇,要小心爆ll,要记得%%

#include<bits/stdc++.h>
#define ll long long
#define fsb(a,b,c) for(ll a=b;a<=c;a++)
#define fbs(a,b,c) for(ll a=b;a>=c;a--)
using namespace std;
ll n,a=0,b=1;
template<typename qw>inline void rll(qw &x){
 x=0;qw f=1;char c=getchar();
 while(!isdigit(c))f=c=='-'?-1:f,c=getchar();
 while(isdigit(c))x=x*10+c-'0',c=getchar();
 x*=f;
}
inline ll gcd(ll a,ll b){
 return b==0?a:gcd(b,a%b);
}
inline void add(ll aa,ll bb){
 ll k=gcd(b,bb),ansa,ansb;
 ansb=b/k*bb;ansa=b/k*aa+bb/k*a;
 k=gcd(ansa,ansb);
 a=ansa/k;b=ansb/k;
}
inline ll len(ll x){
 ll ans=0;
 while(x>0){
  ans++;x/=10;
 }
 return ans;
}
int main(){
 rll(n);
 fsb(i,1,n){
  ll aa=n,bb=i,k=gcd(aa,bb);
  aa/=k;bb/=k;
  add(aa,bb);
 }
 if(a%b==0){
  printf("%lld\n",a/b);
 }else{
  ll x=a/b;a-=x*b;ll lx=len(x),lb=len(b);
  fsb(i,1,lx)printf(" ");printf("%lld\n",a);
  printf("%lld",x);fsb(i,1,lb)printf("-");puts("");
  fsb(i,1,lx)printf(" ");printf("%lld\n",b);
 }
 return 0;
}

Social