hdu 2086：A1 = ?（推公式）

红太狼 2023-06-10 11:28 10阅读 0赞

# hdu 2086：A1 = ?（推公式） #

[题目链接][Link 1]

以前虽然做过这种推公式，找规律的大类题，但是这种几乎是百分之八十解题用在推公式的题还是做的少  
虽然题目不是太难，但是起初推公式弄错了方向，导致无从下手，  
后面再重新找方向推了一遍终于把它推出来了

**推导过程：**  
由**Ai=(Ai-1+Ai+1)/2-Ci** 得：

A1=(A0+A2)/2-C1  
A2=(A1+A3)/2-C2

--------------------

A1+A2=(A0+A1+A2+A3)/2-(C1+C2)  
进一步推导：  
A1+A2=(A0+A3)-2(C1+C2)

同理：  
A1+A3=(A0+A4)-2(C1+C2+C3)

又有：  
A1+A1=(A0+A2)-2C1

可以对C\[\]数组求个前缀和，这样就变为：  
A1+A1=A0+A2-2sum\[1\]  
A1+A2=(A0+A3)-2sum\[2\]  
A1+A3=(A0+A4)-2sum\[3\];  
…  
A1+An=(A0+A(n+1))-2sum\[n\]

**(其中：A(n+1)中的n+1表示下标，下面一样）**

--------------------

等式两边相加得：  
(n+1)A1+(A2+…+An)=nA0+(A2+…+An)+A(n+1)-2(sum\[1\]+sum\[2\]+…+sum\[n\]);

即：  
(n+1)A1=nA0+An+1-2(sum\[1\]+…+sum\[n\])

A1=(nA0+A(n+1)-2(sum\[1\]+…+sum\[n\]))/(n+1)

附上一张自己的推导草稿纸：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70]

于是AC代码为：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #include<cmath>
    #define inf 99999999
    #define ll long long
    using namespace std;
    double sum[3010];         //前缀和
    double c[3010];        //c[]数组
    int main(){
        
        int n;
        while(~scanf("%d",&n)){
        
            memset(sum,0,sizeof(sum));
            memset(c,0,sizeof(c));
            double sum_n=0;
            double a0,an1;
            scanf("%lf%lf",&a0,&an1);        //a0与a(n+1);
            for(int i=1;i<=n;i++){
        
                scanf("%lf",&c[i]);
                sum[i]=sum[i-1]+c[i];
                sum_n+=sum[i];                //借助前缀和数组，一重循环把和求出
            }
            double a1=1.0*(n*a0+an1-2*sum_n)/(n+1);
            printf("%.2f\n",a1);
        }
        return 0;
    }

虽然不难，但是还是有点东西的

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=2086
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70]: /images/20230531/d6da7150b34a41b3a15e199abb257c4e.png