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 = ; i <= n/; ++ i){
int mid = n/;
for(int j = mid-i; j <= mid+i; ++ j) crystal[i][j]='D';
}
for(int i = n- ; i > n/; -- i){
int mid = n/;
for(int j = mid-(n--i); j <= mid+(n--i); ++ j) crystal[i][j]='D';
}
for(int i = ; i < n; ++ i ){
cout<<crystal[i]<<endl;
}
}
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 = ;
cin >>n;
vector<int> a(n,);
bool flag = false;
for(int i = ; i < n; ++ i){
cin >> a[i];
if(i && a[i]<a[i-]) flag = true;
}
if(flag){
int pre= , i = n-;
for( i = n-; i >= ; -- i){
if(a[i]<= a[pre]){
res++;
pre = i;
} else break;
}
for(int j = ; j < i; ++ j){
if(a[j] > a[j+]) {res=-;break;}
}
}
cout<<res<<endl;
}
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)*22 种可能
当三次投掷中只有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)*22 +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 = ;
for(int i = ; i <=m; ++i){
double a = double(i)/m, b = double(i-)/m;
res+=double(m)*pow(a,n+)-double(i)*pow(b,n);
}
printf("%0.5f\n",res);
}