首页 > 其他 > 详细

【oiClass 2122】神奇的项链(数学)

时间:2018-09-22 20:53:50      阅读:250      评论:0      收藏:0      [点我收藏+]

题目描述

笨笨有一条神奇的项链,为什么说它神奇呢?因为它有两个性质:
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。每2个整数之间用1个空格隔开;请放心,数据保证对于任意珠子满足(Ei-1+Ei+1)Mod 2=0;

暴力推一下:

因为e[i]=(e[i-1]+e[i+1])/2+d[i]

所以e[i]=(e[i-1]-d[i])*2-e[i-2]=e[i-1]*2-e[i-2]-d[i-1]*2

推一下可得:

e[3]=e[2]*2-e[1]-d[2]*2

e[4]=e[2]*3-e[1]*2-d[2]*4-d[3]*2

e[5]=e[2]*4-e[1]*3-d[2]*6-d[3]*4-d[4]*2

得到e[n]=e[2]*(n-1)-e[1]*(n-2)-d[2]*(n-2)*2-d[3]*(n-3)*2-....

解e[2]得e[2]=(e[n]+(d[2]*(n-2)*2+d[3]*(n-3)*2+...)+e[1]*(n-2))/(n-1)

再从头列举下去即可。

 1 #include <cstdio>
 2 long long n,en,e[500001],d[500001];
 3 int main(void){
 4     scanf("%lld%lld%lld",&n,&e[1],&en);
 5     e[n]=en;
 6     for(int i=2;i<n;++i){
 7         scanf("%lld",&d[i]);
 8         en+=d[i]*(n-i)*2;
 9     }
10     en=(en+e[1]*(n-2))/(n-1);
11     printf("%lld %lld ",e[1],e[2]=en);
12     for(int i=3;i<n;++i)
13         printf("%lld ",e[i]=(e[i-1]-d[i-1])*2-e[i-2]);
14     printf("%lld",e[n]);
15 }

 

【oiClass 2122】神奇的项链(数学)

原文:https://www.cnblogs.com/gzh01/p/9690927.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!