首页 > 代码库 > BZOJ1011: [HNOI2008]遥远的行星

BZOJ1011: [HNOI2008]遥远的行星

2024-07-16 22:22:13   227人阅读

1011: [HNOI2008]遥远的行星

Time Limit: 10 Sec  Memory Limit: 162 MBSec  Special Judge
Submit: 1852  Solved: 633
[Submit][Status]

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.

1< a < =3.5 接下来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%,也算对

题解传送门：http://hi.baidu.com/zeonsgtr/item/789da6f2838a3dc742c36ab7

神题啊，还能这样算。。。

代码：

 1 const maxn=100000+1000; 2 var g:array[0..maxn] of int64; 3     f,m:array[0..maxn] of extended; 4     i,n:longint; 5     y:extended; 6 procedure init; 7  begin 8    readln(n,y); 9    for i:=1 to n do readln(m[i]);10    for i:=1 to n do g[i]:=trunc(i*y);11  end;12 procedure work1(x:longint);13  var  i:longint;14    begin15      for i:=1 to g[x] do f[x]:=f[x]+m[x]*m[i]/(x-i);16    end;17 procedure work2(x:longint);18  var i:longint;19    begin20      f[x]:=(f[x-100]/m[x-100])*((x-100-g[x-100]/2)/(x-g[x-100]/2));21      for i:=g[x-100]+1 to g[x] do22        f[x]:=f[x]+m[i]/(x-i);23      f[x]:=f[x]*m[x];24    end;25 26 procedure main;27  begin28    for i:=1 to n do f[i]:=0.0;29    for i:=2 to n do30     if i<=500 then work1(i) else work2(i);31    for i:=1 to n do writeln(f[i]:0:6);32  end;33 begin34   assign(input,‘input.txt‘);assign(output,‘output.txt‘);35   reset(input);rewrite(output);36   init;37   main;38   close(input);close(output);39 end.
View Code

t取100就可以过，万恶的BZOJ，哪里说非得输出6位小数啊。。。


联系
我们