当前位置: 代码迷 >> 综合 >> BZOJ1011 [HNOI2008]遥远的行星 【奇技淫巧】
  详细解决方案

BZOJ1011 [HNOI2008]遥远的行星 【奇技淫巧】

热度:73   发布时间:2023-12-25 05:00:27.0

1011: [HNOI2008]遥远的行星

Time Limit: 10 Sec   Memory Limit: 162 MBSec   Special Judge
Submit: 5058   Solved: 1888
[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%,也算对



这题的正解也着实让我吓跪。。。

首先对于i,ansi = ∑M[i] * M[j]/(i - j)

直接模拟O(a n^2)铁定T

我们观察题目,样例为何不直接输出整数呢?5%这个误差为何如此之大?

是不是在暗示着我们什么?

对,我们不一定要如此严谨地求解

当i足够大时,i - j对于结果的影响就变小了,我们只需大概用个0.5 * a * i来替代j就降一维的复杂度

注意当i比较小时还是要规规矩矩地算

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define fo(i,x,y) for (int i = (x); i <= (y); i++)
#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 1000000000;
inline int read(){int out = 0,flag = 1;char c = getchar();while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}while (c >= 48 && c <= 57) {out = out * 10 + c - 48; c = getchar();}return out * flag;
}
double ans,a,M[maxn],sum[maxn];
int n,t;
int main()
{n = read(); cin>>a;REP(i,n) scanf("%lf",&M[i]),sum[i] += sum[i - 1] + M[i];REP(i,n){t = (int)floor(i * a + 1e-8); ans = 0;if (i <= 1000){REP(j,t) ans += M[i] * M[j] / (i - j);printf("%.6lf\n",ans);}else printf("%.6lf\n",M[i] * sum[t] / (i - t / 2));}return 0;
}