Powered by:NEFU AB-IN

Link

3729. 改变数组元素

情人节快乐！

• 题意

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

• 思路

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

  memeset(b, 0, sizeof b)
  

  会导致每组数据都O(n)跑一遍，4e9就很难过，也就是卡memset！！

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

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

  亲测快了十倍！

• 代码

  /*
  * @Author: NEFU AB-IN
  * @Date: 2023-02-14 21:37:04
  * @FilePath: \Acwing\3729\3729.cpp
  * @LastEditTime: 2023-02-14 22:18:33
  */
  #include <bits/stdc++.h>
  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 << '\n'
  typedef pair<int, int> PII;
  
  const int N = 1e6 + 10, INF = 0x3f3f3f3f;
  int a[N], b[N];
  
  int n;
  void solve()
  {
      scanf("%d", &n);
      memset(b, 0, (n + 1) * 4);
      // for (int i = 1; i <= n; ++i)
      //     b[i] = 0;
      for (int i = 1; i <= n; ++i)
      {
          scanf("%d", &a[i]);
          b[max(1, i - a[i] + 1)]++;
          b[i + 1]--;
      }
      for (int i = 1; i <= n; ++i)
      {
          b[i] += b[i - 1];
          printf("%d ", b[i] ? 1 : 0);
      }
      printf("\n");
      return;
  }
  
  signed main()
  {
      int T;
      scanf("%d", &T);
      while (T--)
          solve();
      return 0;
  }