3729.改变数组元素

Powered by:NEFU AB-IN

Link

情人节快乐&＃xff01;

• 题意

  
  

  
  

  给定一个空数组 V和一个整数数组 a1,a2,…,an
  现在要对数组 V进行 n次操作。
  第 i次操作的具体流程如下&＃xff1a;
  从数组 V尾部插入整数 0。将位于数组 V末尾的 ai个元素都变为 1&＃xff08;已经是 1的不予理会&＃xff09;。

• 思路

  思路就是差分&＃xff0c;没什么好说的&＃xff0c;就是想记录一下memset的用法
  可以注意到此题 T &＃61; 2e4, n &＃61; 2e5, 虽然memset相对于循环定义来说&＃xff0c;快了不少
  但如果我们每次都

  memeset(b, 0, sizeof b)


  会导致每组数据都O(n)跑一遍&＃xff0c;4e9就很难过&＃xff0c;也就是卡memset&＃xff01;&＃xff01;

  所以采用下面两种方法&＃xff0c;原理是一样的&＃xff0c;都是不全清0

  memset(b, 0, (n &＃43; 1) * 4) // 意思就是&＃xff0c;我们下标是从0开始的&＃xff0c;所以用n&＃43;1个元素。数组类型是int&＃xff0c;所以占4个byte
for (int i &＃61; 1; i <&＃61; n; &＃43;&＃43;i) // 循环清0
b[i] &＃61; 0;


  亲测快了十倍&＃xff01;

• 代码

  /*
* &＃64;Author: NEFU AB-IN
* &＃64;Date: 2023-02-14 21:37:04
* &＃64;FilePath: \Acwing\3729\3729.cpp
* &＃64;LastEditTime: 2023-02-14 22:18:33
*/
#include
using namespace std;
#define int long long
#undef int
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS \
ios::sync_with_stdio(false); \
cin.tie(nullptr); \
cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << &＃39;\n&＃39;
typedef pair<int, int> PII;
const int N &＃61; 1e6 &＃43; 10, INF &＃61; 0x3f3f3f3f;
int a[N], b[N];
int n;
void solve()
{
scanf("%d", &n);
memset(b, 0, (n &＃43; 1) * 4);
// for (int i &＃61; 1; i <&＃61; n; &＃43;&＃43;i)
// b[i] &＃61; 0;
for (int i &＃61; 1; i <&＃61; n; &＃43;&＃43;i)
{
scanf("%d", &a[i]);
b[max(1, i - a[i] &＃43; 1)]&＃43;&＃43;;
b[i &＃43; 1]--;
}
for (int i &＃61; 1; i <&＃61; n; &＃43;&＃43;i)
{
b[i] &＃43;&＃61; b[i - 1];
printf("%d ", b[i] ? 1 : 0);
}
printf("\n");
return;
}
signed main()
{
int T;
scanf("%d", &T);
while (T--)
solve();
return 0;
}