[div2 B 900]Napoleon Cake
分析： 差分，每次用\(1\)来标记每段区间被覆盖过，最后为\(0\)的就是没被覆盖的 ，不能完全算\(dp\)
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int T, n, x, cf[N];
signed main() {
cin >> T;
while (T --) {
memset(cf, 0, sizeof cf);
cin >> n;
for (int i = 1; i <= n; i ++) {
cin >> x;
if (x) {
cf[i + 1] --, cf[max(i - x + 1, 1)] ++;
}
}
for (int i = 1; i <= n; i ++) {
cf[i] += cf[i - 1];
if (cf[i] >= 1) {
cout << 1 << " ";
} else {
cout << 0 << " ";
}
}
cout << endl;
}
}
[div2 B 900]Non-Substring Subsequence
分析： 其实就是统计一段区间有没有\(0\)或\(1\)，简单\(dp\)
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int T, n, q, ql, qr, r[N][2], l[N][2];
char str[N];
signed main() {
cin >> T;
while (T --) {
memset(r, 0, sizeof r);
memset(l, 0, sizeof l);
cin >> n >> q >> str + 1;
for (int i = n; i; i --) {
if (str[i] == ‘1‘) {
r[i][1] = r[i + 1][1] + 1;
r[i][0] = r[i + 1][0];
} else {
r[i][0] = r[i + 1][0] + 1;
r[i][1] = r[i + 1][1];
}
}
for (int i = 1; i <= n; i ++) {
if (str[i] == ‘1‘) {
l[i][1] = l[i - 1][1] + 1;
l[i][0] = l[i - 1][0];
} else {
l[i][0] = l[i - 1][0] + 1;
l[i][1] = l[i - 1][1];
}
}
while (q --) {
cin >> ql >> qr;
if (qr + 1 <= n && r[qr + 1][str[qr] - ‘0‘]) {
cout << "YES" << endl;
} else if (ql - 1 >= 1 && l[ql - 1][str[ql] - ‘0‘]) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
}
}