Luogu

LOJ

分析

可以发现确保自己不死和攻击大佬是两个独立的行为。

于是我们可以先求出最多有多少天可以用来攻击大佬，只需要做一个简单的 DP 即可。设这个天数为 $t$。

考虑怼大佬的操作，我们实际上只关心能够发动它的天数以及它的伤害。于是我们可以 BFS 出所有这样的 $(d, F)$ 二元组。

接下来考虑如何能够打败一个自信值为 $c$ 的大佬。进行分类讨论：

• 不怼大佬，那么需要满足 $t \geq c$。

• 怼一次大佬，那么需要存在一个 $(d, F)$ 满足 $F \leq c, F + t - d \geq c$。

• 怼两次大佬，那么需要存在两个 $(d_1, F_1)$ 和 $(d_2, F_2)$ 满足 $F_1 + F_2 \leq c, F_1 + F_2 + t - d_1 - d_2 \geq c$。

  考虑将所有二元组以 $F$ 为第一关键字、$d$ 为第二关键字排序，然后从大到小枚举第一个 $i$、双指针从小到大枚举第二个 $j$ 满足 $F_i + F_j \leq c$，并记录 $F_j - d_j$ 的最大值 $mx$。那么只需要判定是否在某个 $i$ 处有 $F_i - d_i + mx + t \geq c$ 即可。

代码

理论上需要使用哈希表判重，我因为懒就写了 map，也能过原题数据。

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;

void chkmax(int &x, int y) { if (y > x) x = y; }
int read() {
    int X = 0, w = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}

const int N = 100 + 10, LIM = 1e8;

int n, m, mc;
int a[N], w[N];
int dp[N][N], t;
struct Attack { int d, F; };
bool operator <(Attack a, Attack b) {
    return a.F < b.F || (a.F == b.F && a.d < b.d);
}
vector<Attack> atk;

struct Node { int d, F, L; };
map<Attack, bool> M;
queue<Node> Q;
void bfs() {
    Q.emplace((Node){1, 1, 0});
    while (!Q.empty()) {
        int d = Q.front().d, F = Q.front().F, L = Q.front().L; Q.pop();
        if (d == t) continue;
        Q.emplace((Node){d + 1, F, L + 1});
        Attack r = (Attack){d + 1, F * L};
        if (L > 1 && 1ll * F * L <= LIM && !M.count(r)) {
            atk.emplace_back(r), M[r] = 1;
            Q.emplace((Node){d + 1, F * L, L});
        }
    }
}

bool check(int c) {
    if (c <= t) return 1;
    for (auto i : atk)
        if (i.F <= c && i.F + t - i.d >= c) return 1;
    for (int i = (int)atk.size() - 1, j = 0, mx = -1e9; ~i; --i) {
        while (j < (int)atk.size() && atk[i].F + atk[j].F <= c) mx = max(mx, atk[j].F - atk[j].d), ++j;
        if (atk[i].F - atk[i].d + mx + t >= c) return 1;
    }
    return 0;
}

int main() {
    n = read(), m = read(), mc = read();
    for (int i = 1; i <= n; ++i) a[i] = read();
    for (int i = 1; i <= n; ++i) w[i] = read();
    for (int i = 1; i <= n; ++i)
        for (int j = a[i]; j <= mc; ++j) {
            chkmax(dp[i][j - a[i]], dp[i - 1][j] + 1);
            chkmax(dp[i][min(mc, j - a[i] + w[i])], dp[i - 1][j]);
        }
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= mc; ++j) t = max(t, dp[i][j]);
    bfs();
    sort(atk.begin(), atk.end());
    for (int i = 1; i <= m; ++i) puts(check(read()) ? "1" : "0");
    return 0;
}