簡易題敘#
題目給你 \(t\) 組測資，每組測資有 \(n\) 個數字（\(n\) 是蛋糕大小），一開始蛋糕是乾的，\(a_i\) 代表從 \(i\) 開始往下數 \(a_i\) 個（包含 \(i\) 自己）的蛋糕都有被淋濕，超過底部沒關係，求最後蛋糕各層有沒有濕，是濕的就輸出 \(1\)，乾的輸出 \(0\)。
範例測資：
- 輸入
3
6
0 3 0 0 1 3
10
0 0 0 1 0 5 0 0 0 2
3
0 0 0
- 輸出
1 1 0 1 1 1
0 1 1 1 1 1 0 0 1 1
0 0 0
概念講解#
首先，因為一開始蛋糕是乾的，我們將差分陣列 \(dif\) 初始化為 \(0\)。
memset(dif, 0, sizeof(dif));
輸入 \(a_i\) 時，如果是 \(0\) 直接不理它，不是的話就在頭尾加 \(1\) 減 \(1\)（注意，超過第一層的要算到第一層，也就是三元運算子那塊）
for (int i = 1, x; i <= n; i++) {
cin >> x;
if (!x) continue;
dif[(i - x + 1 > 0 ? i - x + 1 : 1)]++;
dif[i + 1]--;
}
跑一遍每個位置的前綴和，大於 \(0\) 代表有淋濕，輸出 \(1\)，否則是 \(0\)。
int now = 0;
for (int i = 1; i <= n; i++) {
now += dif[i];
cout << (now > 0 ? 1 : 0) << ' ';
}
範例程式碼#
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int t, n, dif[N];
signed main() {
cin >> t;
while (t--) {
cin >> n;
memset(dif, 0, sizeof(dif));
for (int i = 1, x; i <= n; i++) {
cin >> x;
if (!x) continue;
dif[(i - x + 1 > 0 ? i - x + 1 : 1)]++;
dif[i + 1]--;
}
int now = 0;
for (int i = 1; i <= n; i++) {
now += dif[i];
cout << (now > 0 ? 1 : 0) << ' ';
}
cout << '\n';
}
}
