BZOJ1811:[Ioi2005]mea 乱搞

思路:发现若\(S_1\)不同,则整个序列就不同.因此我们的任务就是找出有多少种\(S_1\)的方案.

我们把\(S_2...S_{n+1}\)都用关于\(S_1\)的一次函数表示,则我们有\(n\)个线性约束条件,对于第\(i\)个条件,我们有\(S_{i}\leq{S_{i+1}}\).

直接接出\(S_1\)的上下界即可.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long LL;
 
#define N 5000010
int k[N];LL b[N];
 
int main(){
    int n;scanf("%d",&n);register int i;LL a;
    k[1]=1,b[1]=0;
    for(i=2;i<=n+1;++i)scanf("%lld",&a),k[i]=-k[i-1],b[i]=2LL*a-b[i-1];
    LL up=1LL<<60,down=-1LL<<60;
    for(i=1;i<=n;++i){
        if(k[i]==1)up=min(up,b[i+1]-b[i]);
        else down=max(down,b[i]-b[i+1]);
    }
    if(up>0)up/=2;else{if(up&1)up=(up-1)/2;else up/=2;}
    if(down>0){if(down&1)down=(down+1)/2;else down/=2;}else down/=2;
    if(up<down){puts("0");return 0;}else printf("%lld",up-down+1);
    return 0;
}