「BZOJ1011」[HNOI2008] 遥远的行星

2014年7月24日4,9240

Description

直线上N颗行星，X=i处有行星i,行星J受到行星I的作用力，当且仅当i<=AJ.此时J受到作用力的大小为 Fi->j=Mi*Mj/(j-i) 其中A为很小的常量，故直观上说每颗行星都只受到距离遥远的行星的作用。请计算每颗行星的受力，只要结果的相对误差不超过5%即可.

Input

第一行两个整数N和A. 1<=N<=10^5.0.01< a < =0.35
接下来N行输入N个行星的质量Mi,保证0<=Mi<=10^7

Output

N行，依次输出各行星的受力情况

Sample Input

5 0.3
3
5
6
2
4

Sample Output

0.000000
0.000000
0.000000
1.968750
2.976000

HINT

精确结果应该为0 0 0 2 3,但样例输出的结果误差不超过5%,也算对

Source

http://hi.baidu.com/zeonsgtr/item/789da6f2838a3dc742c36ab7

这种题到底是什么鬼

#include<iostream>
#include<cstdio>
#include<cmath>
#define eps 1e-8
using namespace std;
int n;
int M[1000005],T=20;
double A,f[1000005];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
    n=read();scanf("%lf",&A);
    for(int i=1;i<=n;i++)
        M[i]=read();
    for(int i=1;i<=T;i++)
    {
        int r=eps+floor(A*i);
        for(int j=1;j<=r;j++)f[i]+=(double)M[i]*M[j]/(i-j);
    }
    for(int i=T+1;i<=n;i++)
    {
        int l=eps+floor(A*(i-T));
        int r=eps+floor(A*i);
        for(int j=l+1;j<=r;j++)f[i]+=(double)M[i]*M[j]/(i-j);
        f[i]+=(double)M[i]*(f[i-T]/M[i-T])*(i-T-(double)l/2)/double(i-(double)l/2);
    }
    for(int i=1;i<=n;i++)
        printf("%.6lf\n",f[i]);
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cmath>

#define eps 1e-8

using namespace std;

int n;

int M[1000005],T=20;

double A,f[1000005];

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int main()

{

n=read();scanf("%lf",&A);

for(int i=1;i<=n;i++)

M[i]=read();

for(int i=1;i<=T;i++)

{

int r=eps+floor(A*i);

for(int j=1;j<=r;j++)f[i]+=(double)M[i]*M[j]/(i-j);

}

for(int i=T+1;i<=n;i++)

{

int l=eps+floor(A*(i-T));

int r=eps+floor(A*i);

for(int j=l+1;j<=r;j++)f[i]+=(double)M[i]*M[j]/(i-j);

f[i]+=(double)M[i]*(f[i-T]/M[i-T])*(i-T-(double)l/2)/double(i-(double)l/2);

}

for(int i=1;i<=n;i++)

printf("%.6lf\n",f[i]);

return 0;

}

« 「CFgym100460B」Time of Trial NOI2014起床困难综合症 »

hzwer.com _ Home | http://hzwer.com

「BZOJ1011」[HNOI2008] 遥远的行星

Description

Input

Output

Sample Input

Sample Output

HINT

Source

分类目录

热门文章

Myfriends

近期评论