A+B Problem

传送门:Swust oj 1206

描述:

有两个数组A, B,其中数组A含有n个数,数组B含有m个数 ( m ≤ n ) 。 现在要对A数组进行n-m+1次操作: 对第一次操作:A1=A1+B1 , A2=A2+B2 , … ,Am=Am+Bm 对第二次操作:A2=A2+B1 , A3=A3+B2 , … , Am+1=Am+1+Bm 对第i次操作(1 ≤ i ≤ n-m+1):Ai=Ai+B1 , Ai+1=Ai+1+B2 , … , Ai+m-1=Ai+m-1+Bm 现在你的任务是求出进行上述操作后的A数组。

输入:

多组测试数据
第一行一个整数T (T ≤ 40),表示有T组测试数据。
每组测试数据有三行,第一行两个整 数n,m ( 1 ≤ m ≤ n ≤ $10^5$ ) ,分别表示
A,B数组的元素个数。
第二行为n个整数Ai ( 1 ≤ Ai ≤ $10^5$ )
第二行为m个整数Bi ( 1 ≤ Bi ≤ $10^5$ )

输出:

输出进行操作操作后的A数组n个整数,用空格隔开。

样例:

  • Input
    4 2
    1 1 1 1
    1 1

  • Output
    2 3 3 2

  • 分析:

    1
    2
    3
    4
    5
    1  1  1  1
    +1 +1
    +1 +1
    +1 +1
    2 3 3 2

题解

通过数据范围我们可以看出采用O(N*M)的方法是会超时的,所以我们先求出B数组的前缀和,然后O(N)处理A数组
当 i ≤ m 时,如果i<=(n-m+1),a[i]+=b[i],否则a[i]+=(b[i]-b[i-n+m-1]);
当 i>m && i ≤ n-m 时,a[i]+=b[m];
否则的话 a[i]+=(b[m]-b[i-n+m-1]);

具体原因可以在纸上推导一下

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#define LL long long int
using namespace std;
LL a[100005],b[100005];
int main()
{
ios::sync_with_stdio(false);
int t;while(cin>>t){
while(t--){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++){
cin>>b[i];
b[i]+=b[i-1];
}
for(int i=1;i<=n;i++){
if(i<=m)
{
if(i<=(n-m+1))a[i]+=b[i];
else a[i]+=(b[i]-b[i-n+m-1]);
}
else if(i>m&&i<=n-m)a[i]+=b[m];
else a[i]+=(b[m]-b[i-n+m-1]);
cout<<a[i]<<" \n"[i==n];
}
}
}
return 0;
}
Donate comment here