1011: [HNOI2008]遥远的行星

Time Limit: 10 Sec Memory Limit: 162 MBSec Special Judge
Submit: 5382 Solved: 2007
[Submit][Status][Discuss]

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%,也算对

这个题的方法真的玄学。。。很明显我们发现需要枚举每个行星，然后计算和加起来，但是这样是n^2的复杂度很明显不对，那么我们还有什么比较高科技的操作么？线段树？明显不行。。平衡树？貌似不是这类问题的方法吧。。。然后可以发现这题有special judge，嗯，根据我的判断，估计应该有那种很2的代码A掉。。看了看BZOJ的评测记录，

好了，我估计AC代码就是：

puts("-nan");
    return 0;

交上去一看，果然A了。。。。

好了好了不扯这些，实际上这道题因为有了只要结果的相对误差不超过5%即可.这句话，而且发现a的取值很小，所以我们大可以大胆的使用一些奇怪的方法，比如分块。。。我们暴力计算一个自己确定的T值以内大小的数据，然后对于其它的大于T的，我们分成大小为T的几块，求出中间值得分母，然后代入式子就可以了，因为a很小，所在T取100时也不会超过5%的误差。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#define re register
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define mid ((i-j+i-j+len-1)*0.5)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(arr) memset(arr, 0, sizeof(arr))
const int inf = 0x3f3f3f3f;
ll a[100005],sum[100005],n;
double ans[100005],A;
inline int read()
{
    int x=0,c=1;
    char ch=' ';
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    while(ch=='-') c*=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();
    return x*c;
}
int main() 
{
    //freopen("date.in","r",stdin);
    n=read();scanf("%lf",&A);
    for(re int i=1;i<=n;i++){
        a[i]=read();
        sum[i]=sum[i-1]+a[i];
    }
    for(re int i=1;i<=n;i++){
        int lenth=int(A*i);
        if(lenth<=80){
            for(re int j=1;j<=lenth;j++)
                ans[i]+=(a[i]*a[j])*1.0/(i-j);
        }else{
            int len=lenth/80;
            for(re int j=len;j<=len*80;j+=len)
                ans[i]+=(sum[j]-sum[j-len])*a[i]*1.0/mid;
            for(re int j=len*80+1;j<=lenth;j++)
                ans[i]+=(a[i]*a[j])*1.0/(i-j);
        }
        
    }
    for(re int i=1;i<=n;i++)
        printf("%.10lf
", ans[i]);
    return 0;
}

很奇怪的是这代码洛谷A了但是bzoj并没有A掉。