题解：P15729 [JAG 2024 Summer Camp #2] Add Add Add

· · 题解

超详细题解，求赞！

有点思维含量，让我瑟瑟发抖。

题意简述

给定两个长度为 N 的正整数序列 A_1,A_2,\cdots, A_N 和 B_1,B_2,\dots,B_N。

对于 k=2 \sim 2N，定义：

S(k)=\sum_{i=1}^N\sum_{j=1}^N [i+j \le k](A_i+B_j)

其中 [\ ] 为艾佛森括号。

输出 S(2),S(3),\cdots,S(2N)，共 2N-1 行。

思路

问题转化

设：

\begin{aligned} F(t)&=\sum_{i=1}^N\sum_{j=1}^N [i+j=t](A_i+B_j)\\ &=\sum_{i=1}^N\sum_{j=1}^N [i+j=t]A_i+\sum_{i=1}^N\sum_{j=1}^N [i+j=t]B_j \end{aligned}

第二项中求和下标是 j，但由于 j 的范围与 i 完全相同，写成 B_i 也可以。

  1. 对每个 A_i，若存在 j=t-i 且 1 \le j \le N，则贡献一次 A_i。
  2. 对每个 B_i，若存在 i=t-j 且 1 \le i \le N，则贡献一次 B_i。

则原式变为：

S(k)=\sum_{t=2}^k F(t)

问题转化为：先计算 F(2),F(3),\cdots,F(2N)，再求前缀和。

计算 F(t)

计算 i 的范围：

\because i+j=t \iff j=t-i\\ \therefore 1 \le i,j \le N \iff 1 \le t-i \le N\\ \because 1 \le t-i \iff i \le t-1\\ 又\because t-i \le N \iff i \ge t-N\\ \therefore t-N \le i \le t-1

计算 j 的范围同理：

t-N \le j \le t-1

所以令 L=\max(1,t-N),R=\min(N,t-1)，则 F(t) 为：

F(t)=\left(\sum_{i=L}^R A_i\right)+\left(\sum_{i=L}^R B_i\right)

因为 i 和 j 的范围完全一样，并且 A 和 B 的贡献是独立的，所以可以直接加。

用前缀和预处理即可。

Code

记得开 long long。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int n,a[maxn],b[maxn];
long long sa[maxn],sb[maxn],ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],sa[i]=sa[i-1]+a[i];
    for(int i=1;i<=n;i++) cin>>b[i],sb[i]=sb[i-1]+b[i];
    for(int t=2;t<=2*n;t++){
        int l=max(1,t-n),r=min(n,t-1);
        ans+=(sa[r]-sa[l-1])+(sb[r]-sb[l-1]),cout<<ans<<'\n';
    }
}