题解 P5847 mea

· · 题解

传送门P5847

思维题。

首先我们考虑，知道了 S_1 就能根据 M_1 推出 S_2 的值，知道了 S_2 就能根据 M_2 推出 S_3 的值，以此类推，所以，知道一个符合范围的 S_1，就能求出一个解，具体如下。

(S_1+S_2)\div 2=M_1\longrightarrow S_2=2\times M_1-S_1 (S_2+S_3)\div 2=M_2\longrightarrow S_3=2\times M_2-S_2 (S_3+S_4)\div 2=M_1\longrightarrow S_4=2\times M_3-S_3 ... (S_i+S_{i+1})\div 2=M_1\longrightarrow S_{i+1}=2\times M_{i}-S_{i}

把 S_2,S_3...S_{n+1} 分别用 S_1 表示得：

S_2=2\times M_1-S_1 S_3=2\times M_2-2\times M_1+S_1 S_4=2\times M_3-2\times M_2+2\times M_1-S_1 ... 2\times(M_1-M_2+M_3-M_4+\cdot\cdot\cdot+M_{i-1})-S_1 & (i \bmod 2=0)\\ 2\times(-M_1+M_2-M_3+\cdot\cdot\cdot+M_{i-1})+S_1 & (i \bmod 2=1) \end{matrix}\right.

即 S_i=\left\{\begin{matrix} 2\times(M_1-M_2+M_3-M_4+\cdot\cdot\cdot+M_{i-1})-S_1 & (i \bmod 2=0)\\ -2\times(M_1-M_2+M_3-M_4+\cdot\cdot\cdot-M_{i-1})+S_1 & (i \bmod 2=1) \end{matrix}\right.

此时，在题目中我们发现一个还没用过的东西：S_i\le S_{i+1}。

于是我们考虑对于每个 i(1\le i\le n) 把 S_i、S_{i+1} 带入不等式。

S_1\le S_2 \longrightarrow S_1\le2\times M_1-S_1 \longrightarrow S_1\le M_1 S_2\le S_3 \longrightarrow 2\times M_1-S_1 \le 2\times(M_2- M_1)+S_1 \longrightarrow 2\times(2\times M_1-M_2)\le 2\times S_1 \longrightarrow 2\times M_1-M_2\le S_1

就像这样，我们可以得到式子：

S_1\ge 2\times(M_1-M_2+M_3-M_4+\cdot\cdot\cdot+M_{i-1})-M_{i} & (i \bmod 2=0)\\ S_1\le 2\times (M_1-M_2+M_3-M_4+\cdot\cdot\cdot-M_{i-1})+M_i& (i \bmod 2=1) \end{matrix}\right.

然后就可以根据每个 i 的不等式得到一个关于 S_1 不等式组，解出这个不等式组即为 S_1 的取值范围，得到 S_1 的取值范围后，因为确定 S_1 即可确定一组解，所以 S_1 的取值范围中整数个数即为所求。

对于这个不等式组，我们发现可以前缀和处理，然后对于奇数的 i 更新答案区间右端点，对于偶数的 i 更新答案区间左端点，设左端点为 l，右端点为 r，答案即为 r-l+1，但是考虑不等式组无解，不能输出负数，应输出 0。

代码（很短）：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define int long long
using namespace std;
int n,l,r,s[5000005],m[5000005];
signed main()
{
    scanf("%lld",&n);
    l=-9223372036854775807,r=9223372036854775807;
    for(int i=1;i<=n;i++)scanf("%lld",&m[i]);
    for(int i=1;i<=n;i++){//前缀和 
        if(i&1)s[i]=s[i-1]+m[i];
        else s[i]=s[i-1]-m[i];
    }
    for(int i=1;i<=n;i++){//求左、右端点 
        if(i&1)r=min(r,(s[i-1]<<1ll)+m[i]);
        else l=max(l,(s[i-1]<<1ll)-m[i]);
    }
    printf("%lld",max(r-l+1,0ll));
    return 0;
}