差分$O(n)$
设数组V原本就有n个数,且全为0,则第i操作是将[i - a[i] + 1, i]置为1。
设差分数组为ans[i],则第i次操作即为:
for(int i = 1; i <= n; ++i)
{
ans[std::max(1, i - a[i] + 1)] += 1;
ans[i + 1] -= 1;
}
当ans[i]被重复置1时,利用差分还原时ans[i]会大于1,但是只要第i个位置有被置过1,那么直接输出1即可,因此输出应为:
for(int i = 1; i <= n; ++i)
{
cout << (ans[i] > 0) << " ";
}
C++ 代码
#include <bits/stdc++.h>
using std::cout;
using std::cin;
int T;
int n, m;
void solve()
{
cin >> n;
std::vector<int> a(n + 1);
std::vector<int> ans(n + 2);
for(int i = 1; i <= n; ++i)
{
cin >> a[i];
}
for(int i = 1; i <= n; ++i)
{
ans[std::max(1, i - a[i] + 1)] += 1;
ans[i + 1] -= 1;
}
for(int i = 1; i <= n; ++i)
{
ans[i] += ans[i - 1];
}
for(int i = 1; i <= n; ++i)
{
cout << (ans[i] > 0) << " ";
}
cout << endl;
}
int main()
{
cin >> T;
while(T--)
{
solve();
}
return 0;
}
昨天复制错代码了。。复制了第一个解法的。。