bestcoder Round #7 前三题题解

BestCoder Round #7

Start Time : 2014-08-31 19:00:00    End Time : 2014-08-31 21:00:00
Contest Type : Register Public   Contest Status : Ended

Current Server Time : 2014-08-31 21:12:12

Solved Pro.ID Title Ratio(Accepted / Submitted)
 bestcoder Round #7 前三题题解 1001 Little Pony and Permutation 37.91%(348/918)
 bestcoder Round #7 前三题题解 1002 Little Pony and Alohomora Part I 29.86%(132/442)
  1003 Little Pony and Dice 20.00%(8/40)
  1004 Little Pony and Boast Busters 4.41%(3/68)
bestcoder Round #7 前三题题解 hdu4985 Little Pony and Permutation 73.23%(93/127)
bestcoder Round #7 前三题题解 hdu4986 Little Pony and Alohomora Part I 61.11%(88/144)
bestcoder Round #7 前三题题解 hdu4987 Little Pony and Dice 23.53%(36/153)
  hdu4988 Little Pony and Boast Busters 80.00%(16/20)

1001( hdu4985 Little Pony and Permutation ):

题意:给出一些那样的映射,把每个环放到括号里输出。

题解:直接搞,超水,看代码:

代码:

 //#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
#define ll long long
#define usll unsigned ll
#define mz(array) memset(array, 0, sizeof(array))
#define minf(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("1biao.out","w",stdout)
#define mp make_pair
#define pb push_back
const int maxn=;
int n;
int a[maxn];
int b[maxn];
int main() {
int i,j;
while(scanf("%d",&n)!=EOF) {
FOR(i,,n)scanf("%d",&a[i]);
mz(b);
FOR(i,,n) {
if(!b[i]) {
printf("(%d",i);
j=a[i];
while(j!=i) {
printf(" %d",j);
b[j]=;
j=a[j];
}
putchar(')');
} }
puts("");
}
return ;
}

(有人说用递归会爆栈,太萎了,看我的碉递归版:

 //#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
#define ll long long
#define usll unsigned ll
#define mz(array) memset(array, 0, sizeof(array))
#define minf(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("1biao.out","w",stdout)
#define mp make_pair
#define pb push_back
const int maxn=;
int n;
int a[maxn];
int b[maxn];
int i,j; void dg(const int &x){
if(x==i)return;
printf(" %d",x);
b[x]=;
dg(a[x]);
} int main() {
while(scanf("%d",&n)!=EOF) {
FOR(i,,n)scanf("%d",&a[i]);
mz(b);
FOR(i,,n) {
if(!b[i]) {
printf("(%d",i);
dg(a[i]);
putchar(')');
} }
puts("");
}
return ;
}

1002( hdu4986 Little Pony and Alohomora Part I):

题意:随机出一个元素个数为n的1001的输入,求1001的输出的括号对 的个数的期望值。

题解:找规律,分类,近似解

先暴力搞出每种1001的输入,算期望,发现N为一位数的时候后面都算不快了,不过我们得到了前几个数据。

观察数据,可以发现ans(n)=1/1 + 1/2 + 1/3 + ... + 1/n

这个是调和级数!没有超碉公式能算。

不过n大的时候有近似公式,ans(n)约等于 ln(n)+0.57721566490153286060651209

于是我们就数少的时候暴力算,数大的时候用这个约等于的来算。

注意暴力算的时候从1/n加到1,由于浮点数的性质,这样精度比较高。

(其实这个约等于的和暴力算得的有好多数不一样,暴力算的因为精度有限也可能不对。如果要全部输出暴力的结果,可以分段打表,隔一段记一个数,输入n在两段之间时,从上一段记的那个数开始算)

代码:

 //#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
#define ll long long
#define usll unsigned ll
#define mz(array) memset(array, 0, sizeof(array))
#define minf(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("1biao.out","w",stdout)
#define mp make_pair
#define pb push_back double farm(int n) {
double re=0.0;
for(int i=n; i>=; i--) {
re+=1.0/i;
}
return re;
} int main() {
int i,j;
int n;
while(scanf("%d",&n)!=EOF) {
if(n<=) {///8个0交C++能984ms过,4个0能过
double t=farm(n);
printf("%.4f\n",t);
} else
printf("%.4f\n",log((double)n)+0.5772156649);///实际上10035就不一样了,不过数据里没有
//getchar();
}
return ;
}

1003( hdu4987 Little Pony and Dice ):

题意:大富翁!地图有0~n这些格子,从0开始扔骰子走,骰子有m面,标有1~m。当人到达n或者超过n就结束。求在n结束的概率。(1<= n,m <=10^9)

题解:DP+特判。

f[i]表示到第i个格子的概率,s[i]表示0~i的概率和。

则f[i]=s[i-1]-s[i-1-m]

这样O(n)就能算,但是n<=10^9,光这样算还不行。

再次找规律,发现n大的时候,后面的f[i]会全是一样的数,那么我们遇到连续若干个一样的数,就可以把它当做解了。“一样”我用差小于10^-9来判,连续2000个一样。

这样能过初审了,但是会被hack,system test也过不去,可能是因为m超大的时候很多小数加起来,精度不够。

固定m,则n=m时答案最大。当m=555555时,答案最大也为0,则m>=555555就直接答案为0。加上这个就能过了。

还有一个特判,是n<=m时能直接一个公式求得答案,公式推导我写在代码的注释里了。

代码:

 //#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std;
#define ll long long
#define usll unsigned ll
#define mz(array) memset(array, 0, sizeof(array))
#define minf(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("1biao.out","w",stdout)
#define mp make_pair
#define pb push_back
const int maxcul=;
const int maxcnt=;
const double eps=1e-; double f[maxcul+];
double s[maxcul+];
double farm(int m,int n){
if(m>)return 0.0;/// m固定,当n=m时ans取最大值,m大于这个时最大值也是0
if (n<=m) return pow(1.0+1.0/m,n-)/m;
/// C(n-1,0)/m + C(n-1,1)/m/m + C(n-1,2)/m/m/m + ... + C(n-1,n-1)/(m^n)
///=( C(n-1,0) + C(n-1,1)/m + C(n-1,2)/m/m + ... + C(n-1,n-1)/(m^(n-1)) )/m
///=(1+1/m)^(n-1)/m
int i,j;
int cnt=;
mz(f);
f[]=1.0;
s[]=1.0;
for(i=;i<=n;i++){
int minj=max(,i-m);
if(minj==) f[i] = s[i-]/m;
else f[i] = (s[i-] - s[minj-]) / m;
s[i]=f[i]+s[i-];
if(i>m && fabs(f[i]-f[i-])<eps)cnt++;
else cnt=;
if(cnt>maxcnt)break;
}
if(cnt>maxcnt) return f[i];
else return f[n];
} int main() {
int i,j;
int m,n;
while(scanf("%d%d",&m,&n)!=EOF){
printf("%.5f\n",farm(m,n));
}
return ;
}
上一篇:Tomcat7 配置 ssl


下一篇:Oracle查询死锁&杀死会话