[HNOI2017] 大佬

Description

Transmission Gate

Solution

题目面长度堪比《离骚》，不过也是道巧妙题

这一题操作很多，混在一起不好考虑，那么将他们分类进行处理。

总的来说，操作分为回复和攻击， 其中攻击又有两种类型,每种类型又互不干扰,所以可以拆开处理。 可以发现大佬攻击和自己回复的值是一定的，而大佬不会回复，所以两个操作互不影响，所以分开求解。我们只要求出一个时间长度， 并且在这个长度内击败大佬即可。

那么设(dp[i][j]) 表示到第i天,自信值还有j的情况下最多有(dp[i][j])天不回复用来攻击的最大值.

接下来考虑攻击, 考虑这样一个状态((i,j)),表示用i天打出j的伤害.可以BFS + Hash做.

那么有:
[ I_1 + I_2 leq HP ~ && ~ I_1 + I_2 + (D - J_1 - J_2) geq C ]
然后排序之后,TwoPointer扫一下就可以了。

Inspiration

在题目的要求/操作/限制条件很多的时候，我们可以分类进行处理。

这一题的模型其实就是用01背包表示出一个特定的值，但是因为第三种物品太多，前两种物品很少。所以我们可以枚举前两种，计算第三种。 (gsa)而枚举可以采用twopointer，因为前两种物品有单调性。(gsa)

Code

#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define drep(i, a, b) for(int i = (a), i##_end_ = (b); i >= i##_end_; --i)
#define clar(a, b) memset((a), (b), sizeof(a))
#define debug(...) fprintf(stderr, __VA_ARGS__)
typedef long long LL;
typedef long double LD;
int read() {
    char ch = getchar();
    int x = 0, flag = 1;
    for (;!isdigit(ch); ch = getchar()) if (ch == '-') flag *= -1;
    for (;isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    return x * flag;
}
void write(int x) {
    if (x < 0) putchar('-'), x = -x;
    if (x >= 10) write(x / 10);
    putchar(x % 10 + 48);
}

const int Maxn = 109, Maxm = 29, Maxmc = 109;
const int HashSize = 1000009;
int n, m, mc, a[Maxn], w[Maxn], C[Maxn];
int dp[Maxn][Maxmc];

struct node {
    int tims, damage, level;
    int operator < (const node nothaer) const {
        return damage < nothaer.damage || damage == nothaer.damage && tims < nothaer.tims;
    }
    int operator == (const node nothaer) const {
        return tims == nothaer.tims && damage == nothaer.damage; 
    }
};
struct HASH {
    int head[HashSize], nxt[HashSize * 20], size;  
    node to[HashSize];  
    HASH() {
        clar(head, -1);
    }
    void insert(node val) {
        int res = (val.level * 817ll % HashSize + val.damage * 1926ll % HashSize + val.tims * 19260817ll % HashSize) % HashSize;
        for (int i = head[res]; ~i; i = nxt[i]) if (to[i] == val) return ;
        to[++size] = val;
        nxt[size] = head[res];
        head[res] = size;
    }

    int exist(node val) {
        int res = (val.level * 817ll % HashSize + val.damage * 1926ll % HashSize + val.tims * 19260817ll % HashSize) % HashSize;
        for (int i = head[res]; ~i; i = nxt[i]) if (to[i] == val) return 1;
        return 0;
    }
}tab;

void init() {
    n = read(), m = read(), mc = read();
    rep (i, 1, n) a[i] = read();
    rep (i, 1, n) w[i] = read();
    rep (i, 1, m) C[i] = read();
}

int Limit = 0, limitDam, LZ;


queue <node> que;
vector <node> Fkq;
void BFS() {
    que.push((node){1, 1, 0}); tab.insert((node){1, 1, 0});
    Fkq.push_back((node){1, 1, 0});
    while (!que.empty()) {
        node u = que.front(); que.pop();
        if (u.tims < Limit) {
            node New = (node){u.tims + 1, u.damage, u.level + 1};
            if (!tab.exist(New)) tab.insert(New), que.push(New);
            New = (node){u.tims + 1, u.damage * u.level, u.level};
            if (1ll * u.level * u.damage <= 1ll * LZ && !tab.exist(New) && u.level > 1) 
                tab.insert(New), que.push(New), Fkq.push_back(New);
        }
    }
}

void solve() {
    clar(dp, -1), dp[0][mc] = 0;
    rep (i, 0, n)
        rep (j, 0, mc) 
            if(~dp[i][j]) {
                if (j >= a[i + 1]) dp[i + 1][min(j - a[i + 1] + w[i + 1], mc)] = max(dp[i + 1][min(j - a[i + 1] + w[i + 1], mc)], dp[i][j]);
                if (j >= a[i + 1]) dp[i + 1][j - a[i + 1]] = max(dp[i + 1][j - a[i + 1]], dp[i][j] + 1);
            }

    rep (i, 1, n) 
        rep (j, 0, mc) limitDam = Limit = max(Limit, dp[i][j]);

    rep (i, 1, n) LZ = max(LZ, C[i]);

    BFS();
    sort(Fkq.begin(), Fkq.end());

    rep (i, 1, m) {
        int Flag = 0, Max = -0x3f3f3f3f, leftPoint = 0;

        if (C[i] <= limitDam) {
            puts("1");
            continue;
        }
        drep (j, Fkq.size() - 1, 0) {
            for (; leftPoint < (int)Fkq.size() - 1 && Fkq[leftPoint].damage + Fkq[j].damage <= C[i]; ++leftPoint)
                Max = max(Max, Fkq[leftPoint].damage - Fkq[leftPoint].tims);
            if (Max + Fkq[j].damage - Fkq[j].tims >= C[i] - limitDam) {
                Flag = 1;
                break;
            }
            if (C[i] >= Fkq[j].damage && Fkq[j].damage + limitDam - Fkq[j].tims >= C[i]) {
                Flag = 1;
                break;
            }
        }

        puts(Flag ? "1" : "0");
    }
}

int main() {
    init();
    solve();

#ifdef Qrsikno
    debug("nRunning time: %.3lf(s)n", clock() * 1.0 / CLOCKS_PER_SEC);
#endif
    return 0;
}