题解：AT_arc135_b [ARC135B] Sum of Three Terms

· · 题解

相邻三个数的约束很复杂，能否转成两个数的？

能。考虑类似裂项的做法：

a_{x+1}+a_{x+2}+a_{x+3}=s_{x+3}\end{cases}

下减上：s_{x+3}-s_{x+2}=a_{x+3}-a_{x}。换句话说，s 的差分是 a 的隔三项差。

因此按下标对 3 取模结果分类把 a 分成三个独立的序列，它们的差分就对应 a 的隔三项差。设第 i 个序列的差分为 d_i。

现在得到三个序列的差分，要还原这些序列还需要首项，分别是 a_1、a_2 和 a_3（以下若出现 a 则下标均在 [1,3] 范围内）。

首项需要满足：

  1. 每个序列所有数都非负（即差分数组前缀和的最小值加首项非负）：\forall 1\le i\le 3,a_i+\min(0,\min_j\sum_k d_k)\ge 0。
  2. 和为 s_1：a_1+a_2+a_3=s_1。

令 q_i=\min(0,\min_j\sum_k d_k)，则 a_i\ge -q_i。则 a_1+a_2+a_3\ge -q_1-q_2-q_3。

若 -q_1-q_2-q_3>s_1，则无解。否则构造 a_1=-q_1,a_2=-q_2,a_3=s_1+q_1+q_2 即可。

然后用首项推后面的数。

:::success[code]

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=300005;
int n,a[N],d[5][N],p[5],q[5],D,W,aa[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=3;i<=n+2;i++)cin>>a[i],aa[i]=a[i]; // a 是文字里的 s
    for(int i=n+2;i>=3;i--)a[i]-=a[i-1]; // 差分
    for(int _=1;_<=3;_++){
        for(int i=_+3;i<=n+2;i+=3){ // 分三个序列
            d[_][++p[_]]=a[i];
            d[_][p[_]]+=d[_][p[_]-1];
        }
    }
    for(int i=1;i<=3;i++){
        q[i]=min(0ll,*min_element(d[i]+1,d[i]+p[i]+1)); // 获取首项最小值
    }
    D=a[3];
    W=-q[1]-q[2]-q[3];
    if(W>D)cout<<"No\n"; // 无解
    else{
        cout<<"Yes\n"; // 有解
        cout<<-q[1]<<' '<<-q[2]<<' '<<D+q[1]+q[2]<<' ';
        int u=D,x=-q[1],y=-q[2],z=D+q[1]+q[2]; // 推首项
        for(int i=4;i<=n+2;i++){ // 循环推出后面的项
            int _=0;
            cout<<(_=aa[i]-u+x)<<' ';
            x=y;
            y=z;
            z=_;
            u=aa[i];
        }
    }
    return 0;
}

:::