Blog

题目

Luogu
LOJ
Acwing

思路

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 110, M = 10000010, mod = 3587201;
int n, m, mc, f[N][N];
int a[N], w[N], c[N];
struct PII { int d, f; };
struct NODE { int d, l, f; };
bool operator<(PII a, PII b) { return (a.f == b.f) ? a.d < b.d : a.f < b.f; }
// 手写hash
int h[mod + 10], ptr[M], idx;
PII val[M];
void insert(PII x) {
    int t = (1ll * x.f + 101 + x.d) % mod;
    val[idx] = x, ptr[idx] = h[t], h[t] = idx++;
}
bool find(PII x) {
    int t = (1ll * x.f + 101 + x.d) % mod;
    for (int i = h[t]; i != -1; i = ptr[i])
        if (val[i].f == x.f && val[i].d == x.d) return true;
    return false;
}
// 存储二元组
PII p[M]; int ps;
// 广搜相关
NODE q[M];
int hh = 0, tt = -1;
// 广搜
void BFS(int md, int maxc) {
    memset(h, -1, sizeof h);
    q[++tt] = (((NODE){ 1, 0, 1 }));
    insert((PII){ 1, 1 });
    while (hh <= tt) {
        NODE t = q[hh++];
        if (t.d >= md) continue;
        q[++tt] = ((NODE){ t.d + 1, t.l + 1, t.f });
        insert((PII){ t.d + 1, t.f }); 
        // 等级大于 1 才有意义, 最大的伤害不超过敌人最大血量
        // 而且需要 hash 里面找不到
        if (t.l > 1 && 1ll * t.f * t.l <= maxc && 
            !find((PII){ t.d + 1, t.f * t.l })) {
            PII x = (PII){ t.d + 1, t.l * t.f };
            q[++tt] = ((NODE){ t.d + 1, t.l, t.l * t.f });
            insert(x), p[ps++] = x;
        }
    }
}
// 判重之后的数组
PII t[M]; int ts;
signed main() {
    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]);
    int maxc = 0;
    for (int i = 1; i <= m; i++) 
        cin >> c[i], maxc = max(maxc, c[i]);
    // 前面的小DP
    for (int i = 1; i <= n; i++)
        for (int j = a[i]; j <= mc; j++)
            f[i][j - a[i]] = max(f[i][j - a[i]], f[i - 1][j] + 1), 
            f[i][min(j - a[i] + w[i], mc)] = 
                max(f[i][min(j - a[i] + w[i], mc)], f[i - 1][j]);
    int md = 0; 
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= mc; j++)
            md = max(md, f[i][j]);
    BFS(md, maxc), sort(p, p + ps);
    // 这里去个重
    t[ts++] = p[0];
    for (register int i = 1; i < ps; i++) 
        if (p[i].f != p[i - 1].f) t[ts++] = p[i];
    for (register int i = 1; i <= m; i++) {
        // 不怼
        if (c[i] <= md) { puts("1"); continue; }
        int r = 0, flag = 0, maxpre = -1e9;
        for (register int j = ts - 1; j >= 0; j--) {
            // 维护前缀最大值
            while (r < ts && t[r].f + t[j].f <= c[i]) 
                maxpre = max(maxpre, t[r].f - t[r].d), r++;
            // 怼一次的情况顺便枚举了
            if (t[j].f <= c[i] && t[j].f + md - t[j].d >= c[i]) { flag = 1; break; }
            // 怼两次
            if (t[j].f + md - t[j].d + maxpre >= c[i]) { flag = 1; break; }
        }   
        printf("%d\n", flag);
    }
    return 0;
}