首页 > 代码库 > Codeforces Round #259 (Div. 2)

Codeforces Round #259 (Div. 2)

A. Little Pony and Crystal Mine

水题,每行D的个数为1,3.......n-2,n,n-2,.....3,1,然后打印即可

#include <iostream>#include <vector>#include <algorithm>#include <string>using namespace std;int main(){    int n;    cin >> n;    vector<string> crystal(n,string(n,*));    for(int i = 0 ; i <= n/2; ++ i){        int mid = n/2;        for(int j = mid-i; j <= mid+i; ++ j) crystal[i][j]=D;    }    for(int i = n-1 ; i > n/2; -- i){        int mid = n/2;        for(int j = mid-(n-1-i); j <= mid+(n-1-i); ++ j) crystal[i][j]=D;    }    for(int i = 0 ; i < n;  ++ i ){        cout<<crystal[i]<<endl;    }}
View Code

B. Little Pony and Sort by Shift

题目意思:

  给一个序列a1,a2...an,每次操作将最后一个元素放在数列开始位置,即a1,a2.....an变成an,a1,a2......an-1,通过多少次操作可以将序列变成非递减序列。

解题思路:

  如果序列本身是非递减序列,则输出0

  如果序列不是非递减的,令pre=0, i=n-1,然后将a[i]与a[pre]比较,

  如果a[i]≤a[pre],说明可以将a[i]放在数列前面,则更新pre=i,然后--i,继续上面操作,直到a[i]>a[pre],则不能交换(如果交换后不能满足非递减序列),退出循环

  再遍历 0~i,是否满足非递减

#include <iostream>#include <vector>#include <algorithm>#include <string>using namespace std;int main(){    int n, res = 0;    cin >>n;    vector<int> a(n,0);    bool flag = false;    for(int i = 0 ; i < n; ++ i){        cin >> a[i];        if(i && a[i]<a[i-1]) flag = true;    }    if(flag){        int pre= 0, i = n-1;        for( i = n-1; i >= 0; -- i){            if(a[i]<= a[pre]){                res++;                pre = i;            } else break;        }        for(int j = 0 ; j < i; ++ j){            if(a[j] > a[j+1]) {res=-1;break;}        }    }    cout<<res<<endl;}
View Code

C. Little Pony and Expected Maximum

题目意思:

  有一个m面的骰子,骰子投掷出数为1 ,2,3,4......m,每个数被投掷出的概率是1/m,然后将该骰子投掷n次,问投掷出大期望值是多少?(每次投掷都是相互独立的)

解题思路:

  现在以m=6,n=3为例说明投掷n次后,注意每种情况出现的概率是1/mn

  最大值为1的情况是(1,1,1)

  最大值为2的情况是三次投掷中至少有一次是2

    当三次投掷中只有1次是2,则剩下2次,每次出现的情况只能是1,故有C(3,1)种可能

    当三次投掷中只有2次是2,则剩下1次,只能出现1,故有C(3,2)种可能

    当三次投掷全部是2时,则有C(3,3)种可能

    故所有的可能数是C(3,1)+C(3,2)+C(3,3)

  最大值为3的情况是三次投掷中至少有一次是3

    当三次投掷中只有1次是3时,则剩下2次,每次出现的点数是1或者2两种,故剩下2次的可能数是22  故整个可能数是C(3,1)*2种可能

    当三次投掷中只有2次是3时,则剩下1次,每次出现的点数是1或者2两种,故剩下1次的可能数是21  故整个可能数是C(3,2)*21 种可能

    当三次投掷中3次是3时,则剩下0次,每次出现的点数是1或者2两种,故剩下2次的可能数是20  故整个可能数是C(3,3)*20 种可能

    故所有的可能是C(3,1)*2+C(3,2)*21 +C(3,3)*20

  .................................

  假设现在是m,n,最大值为k的情况是n次投掷中至少有一次是k

    当n次投掷中只有1次是k时,则剩下n-1次,每次出现的点数是1....k-1任何一个数,故剩下n-1次的可能数是(k-1)n-1 故整个可能数是C(n,1)*(k-1)n-1种可能

    当n次投掷中只有2次是k时,则剩下n-2次,每次出现的点数是1....k-1任何一个数,故剩下n-2次的可能数是(k-1)n-2 故整个可能数是C(n,2)*(k-1)n-2种可能

    当n次投掷中只有3次是k时,则剩下n-3次,每次出现的点数是1....k-1任何一个数,故剩下n-1次的可能数是(k-1)n-3 故整个可能数是C(n,3)*(k-1)n-3种可能

    ....................................................

    故所有的可能是C(n,1)*(k-1)n-1 +C(n,2)*(k-1)n-2+C(n,3)*(k-1)n-3+.............+C(n,n)*(k-1)n-n, 缺少C(n,0)*(k-1)n

    根据公式(1+x)^n=C(n,n)+C(n,n-1)x^1+C(n,n-2)x^2+………+C(n,2)x^(n-2)+C(n,1)x^(n-1)+C(n,0)x^n

    故上述所有可能等于(1+k-1)n-(k-1)n-1=kn-(k-1)n-1

  故最大值为k的可能数是kn-(k-1)n-1

  整个的期望是Σk(kn-(k-1)n-1)/mn,其中k=1......n

  由于m,n都很大,用pow会溢出故需要处理,上述公式变为Σk(kn-(k-1)n-1)/mn=Σ(m(k/m)n+1-(k/k-1)(k-1/m)n)

#include <iostream>#include <cmath>#include <cstdio>using namespace std;int main(){    int m,n;    cin >> m >> n;    double  res = 0;    for(int i = 1; i <=m; ++i){        double a = double(i)/m, b = double(i-1)/m;        res+=double(m)*pow(a,n+1)-double(i)*pow(b,n);    }    printf("%0.5f\n",res);}
View Code