( ext{Solution})
我们发现5个行为中2操作与其它操作无关，所以我们采用贪心，尽量让多的时间去攻击大佬。
设 (f[i][j]) 表示前 (i) 天剩 (j) 血量所能攻击的最多次数，是个很简单的 (dp) ，决策就是刷不刷水题， (D) 就是最多的时间。
void DP() {
memset(f, -1, sizeof f);
f[0][MC] = 0;
for (int i = 0; i < n; ++ i)
for (int j = 0; j <= MC; ++ j) {
if (f[i][j] == -1) continue;
chkmax(D, f[i][j]);
int t = j - a[i + 1];
if (t < 0) continue;
chkmax(f[i + 1][t], f[i][j] + 1);
t = min(t + w[i + 1], MC);
chkmax(f[i + 1][t], f[i][j]);
}
}
那么现在就是给你很多组询问，询问是否能在 (D) 天内击败大佬。
考虑一个二元组 ((x, y)) 表示达到讽刺值为 (x) ，能力值为 (y) 的最少天数。
然后这些二元组我们可以从 ((1,0)) (bfs)暴力求。
void Get() {
queue<pii> Q;
Q.push(pii(1, 0));
M[pii(1, 0)] = 0;
while (Q.size()) {
pii x = Q.front(); Q.pop();
int now = M[x];
if (vis[x.first])
chkmin(V[x.first], now + 1);
else {//V[x]: 至少到V[x]天讽刺值为x,并且明天可以继续累积
vis[x.first] = 1;
b[++tot] = x.first;
V[x.first] = now + 1;
}
if (now >= D - 1) continue;//明天不能继续累积，只能攻击
if (!M.count(pii(x.first, x.second + 1))) {//升级
M[pii(x.first, x.second + 1)] = now + 1;
Q.push(pii(x.first, x.second + 1));
}
if (x.second > 1 && 1ll * x.first * x.second < maxM &&
!M.count(pii(x.first * x.second, x.second))) {//累积讽刺值
M[pii(x.first * x.second, x.second)] = now + 1;
Q.push(pii(x.first * x.second, x.second));
}
}
}
求出二元组后，对所有二元组按讽刺值排序(第一维)，记 (g[i]) 为第 (i) 个二元组 (x_i-y_i) 的值。
考虑不怼大佬，回嘴击败大佬：
if (C < D) return true;
考虑怼一次大佬，需满足有 (x_ile C) ( ext{and}) (Cle x_i +(d -y_i)=g[i]+d)
for (int i = 1; i <= tot; ++ i)
if (C >= x[i] && g[i] >= C - D)
return 1;//怼一次
考虑怼两次大佬，需满足有 (x_i+x_jle C ext{and} Cle x_i+x_j+(d-y_i-y_j))
两个指针扫描，由于排好序先保证 (x_i+x_jle C) 然后维护前缀 (g[i]) 最大值 (Mx[i])
for (int i = 1; i <= tot; i++) {
if (x[i] > c)
return 0;//如果当前大于c，那么之后必然大于c，不满足条件1,是一个小剪枝
while (tail && x[i] + x[tail] > C)
--tail;//由于x单调，可能的答案在i到tail之间
if (tail && g[i] + Mx[tail] >= C - D)
return 1;
}
这题难就难在将原问题抽离成两个单独的问题，将复杂的问题抽离成一些容易的，比较好处理的问题，会对结题有很大帮助，然后就是要多积累，熟悉经典问题的解法，如本题的讨论怼几次的问题上为了满足条件，运用了双指针扫描 ((two\_pointer)) 的方法。
( ext{Source})
#include <bitset>
#include <map>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <assert.h>
#include <algorithm>
using namespace std;
#define LL long long
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define GO debug("GO
")
inline int rint() {
register int x = 0, f = 1; register char c;
while (!isdigit(c = getchar())) if (c == '-') f = -1;
while (x = (x << 1) + (x << 3) + (c ^ 48), isdigit(c = getchar()));
return x * f;
}
template<typename T> inline void chkmin(T &a, T b) { a > b ? a = b : 0; }
template<typename T> inline void chkmax(T &a, T b) { a < b ? a = b : 0; }
const int N = 105;
const int maxM = 1e8 + 5;
const int maxN = 1e6 + 10;
#define pii pair<int, int>
bitset<maxM> vis;
map<pii, int> M;
map<int, int> V;
int n, m, MC, D, tot, a[N], w[N], b[maxN], f[N][N], g[maxN], Mx[maxN];
void DP() {
memset(f, -1, sizeof f);
f[0][MC] = 0;
for (int i = 0; i < n; ++ i)
for (int j = 0; j <= MC; ++ j) {
if (f[i][j] == -1) continue;
chkmax(D, f[i][j]);
int t = j - a[i + 1];
if (t < 0) continue;
chkmax(f[i + 1][t], f[i][j] + 1);
t = min(t + w[i + 1], MC);
chkmax(f[i + 1][t], f[i][j]);
}
}
void Get() {
queue<pii> Q;
Q.push(pii(1, 0));
M[pii(1, 0)] = 0;
while (Q.size()) {
pii x = Q.front(); Q.pop();
int now = M[x];
if (vis[x.first])
chkmin(V[x.first], now + 1);
else {
vis[x.first] = 1;
b[++tot] = x.first;
V[x.first] = now + 1;
}
if (now >= D - 1) continue;
if (!M.count(pii(x.first, x.second + 1))) {
M[pii(x.first, x.second + 1)] = now + 1;
Q.push(pii(x.first, x.second + 1));
}
if (x.second > 1 && 1ll * x.first * x.second < maxM &&
!M.count(pii(x.first * x.second, x.second))) {
M[pii(x.first * x.second, x.second)] = now + 1;
Q.push(pii(x.first * x.second, x.second));
}
}
}
bool solve() {
int tail = tot, C;
scanf("%d", &C);
if (C < D) return 1;
for (int i = 1; i <= tot; ++ i)
if (C >= b[i] and g[i] >= C - D)
return 1;
for (int i = 1; i <= tot; ++ i) {
if (b[i] > C) return 0;
while (tail and b[i] + b[tail] > C) tail --;
if (tail and g[i] + Mx[tail] >= C - D) return 1;
}
return 0;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("xhc.in", "r", stdin);
freopen("xhc.out", "w", stdout);
#endif
scanf("%d%d%d", &n, &m, &MC);
for (int i = 1; i <= n; ++ i) scanf("%d", a + i);
for (int i = 1; i <= n; ++ i) scanf("%d", w + i);
DP();
if (D == 0) {
for (int i = 1; i <= m; ++ i) printf("0
");
return 0;
}
Get();
sort(b + 1, b + 1 + tot);
for (int i = 1; i <= tot; ++ i) {
g[i] = b[i] - V[b[i]];
Mx[i] = max(Mx[i - 1], g[i]);
}
while (m --)
puts(solve() ? "1" : "0");
}