第一次的题解,希望以后有时间多写一点
差分的原理
b[i] = a[i] - a[i-1],...,b[1] = a[1] - a[0]
a[i] = b[i]+..b[1],...,a[1] = b[1]
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 2e5 + 10;
int a[N],b[N];
//最暴力的做法,是过了8/10的数据也挺好的
int main()
{
int k;
cin>>k;
while(k--)
{
memset(a,0,sizeof a);
memset(b,0,sizeof b);
int n;
scanf("%d",&n);
for(int i = 1;i <= n;i++)
{
int x;
cin>>x;
if(x)
{
b[max(i-x + 1,1)] ++,b[i+1] --;//这里前缀和先加起来
//像b[max(i-x + 1,1)] = 1,b[i+1] = 0;
//像b[max(i-x + 1,1)] = 1,b[i+1] --
//的式子都是不对的,前面加了后面没减
//前面变成了1,后面可能减更多,这样不好
//所以我们这样可以最好的保证0的存在
//对于多次计算的数,我们将他与1比较输出
}
}
for(int i = 1;i <= n;i++)
{
b[i] += b[i-1];//这是将差分前缀和起来,求出原来数组
if(b[i] > 1){cout<<1<<" ";continue;}
cout<<b[i]<<" ";
}
cout<<endl;
}
return 0;
}