本文共 1282 字，大约阅读时间需要 4 分钟。

神奇的项链(fett)

题目描述

从前有一条神奇的项链，为什么说它神奇呢？因为它有两个性质：1. 神奇的项链可以拉成一条线，线上依次是N 个珠子，每个珠子有一个能量值Ei；2. 除了第一个和最后一个珠子，其他珠子都满足Ei=(Ei-1+Ei+1)/2+Di。由于这条项链很长，我们只能知道其两端珠子的能量值。并且我们知道每个珠子的Di是多少。请聪明的你求出这N 个珠子的能量值分别是多少。

输入

第一行三个整数N、E1、EN，表示珠子个数N，第一个珠子和第N 个珠子的能量值。第二行N-2 个整数，表示第2 个珠子到第N-1 个珠子的Di。

输出

输出仅一行，N 个整数，表示1 到N 个这N 个珠子各自的能量值Ei。请放心，数据保证对于任意珠子满足(Ei-1+Ei+1)Mod 2=0

样例输入

Sample Input 1:

4 1 40 0

Sample Input 2:

10 1 221 2 -3 5 1 4 2 -1

样例输出

Sample Output 1:

1 2 3 4

Sample Output 2:

1 14 25 32 45 48 49 42 31 22

数据范围限制

40%的数据 1<N<=100。
70%的数据 1<N<=5,000，所有数据（包括计算中的）不超过10^9。
100%的数据 1<N<=500,000，|E1|、|EN|<=10^{14，|Di|<=10}4。

这道题其实是一道数学题，我们将题目给出的公式转变一下，然后再求出第二个值（如果暴力枚举，会超时，所以我们用二分），就直接可以暴力了

E[i]=(E[i-1]+E[i+1])/2+D[i]
同乘2，得：
2E[i]=E[i-1]+E[i+1]+2D[i]
移项，得：
E[i+1]=2E[i]-E[i-1]-2D[i]
所以通项公式为
E[i]=2E[i-1]-E[i-2]-2D[i-1]

code:

#include<iostream>#include<cstdio>using namespace std;long long n,l,r,a,e[500005],d[500005];int main(){
   	freopen("fett.in","r",stdin);	freopen("fett.out","w",stdout);	cin>>n;	cin>>e[1]>>a;	for(int i=2;i<=n-1;i++)	 cin>>d[i];	l=-10000000000000;	r=10000000000000;	while(l<r)	{
   		e[2]=(l+r)/2;		for(int i=3;i<=n;i++) e[i]=2*(e[i-1]-d[i-1])-e[i-2];		if(e[n]==a)		{
   			for(int i=1;i<=n;i++)				cout<<e[i]<<' ';			return 0; 		}		else			if(e[n]<a)l=e[2];		 	else r=e[2]; 	}}

谢谢