\(\text{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_i\le C\) \(\text{and}\) \(C\le 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_j\le C\ \text{and}\ C\le x_i+x_j+(d-y_i-y_j)\)

两个指针扫描，由于排好序先保证 \(x_i+x_j\le 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)\) 的方法。

\(\text{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\n")

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\n");

    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");

}

大佬

[HNOI2017]大佬

\(\text{Solution}\)

\(\text{Source}\)