Chlience

【题解】LOJ 2021 「AHOI / HNOI2017」大佬
Problem你有 $mc$ 点血量上限,开始时血量 $c=mc$你有等级 $L$ 和伤害 $F$ ,开始时 $L...
扫描右侧二维码阅读全文
02
2019/02

【题解】LOJ 2021 「AHOI / HNOI2017」大佬

Problem

你有 $mc$ 点血量上限,开始时血量 $c=mc$
你有等级 $L$ 和伤害 $F$ ,开始时 $L=0,F=1$

$BOSS$ 有 $C$ 点血量

每天你会受到$BOSS$ 的 $a_i$ 点伤害,若你的血量 $c\geq0$ ,那么可选择一个操作:

  1. $BOSS$ 扣一点血($C=C-1$)
  2. 回复 $w_i$ 点血($c=min(c+w_i,mc)$)
  3. 让自己的等级加一($L=L+1$)
  4. 让自己的伤害乘以自己的等级($F=F*L$)
  5. $BOSS$ 扣 $F$ 点血,归零等级,伤害降为 $1$($C=C-F,L=0,F=1$)此操作不超过 $2$ 次

问能否在 $n$ 天内使得 $BOSS$ 的血量恰好为 $0$

有 $m$ 个不同的 $BOSS$,每个 $BOSS$ 的血量不一定相同
对于每个 $BOSS$ 输出结果

Thought

题面真鸡儿长

首先,你需要保证在你活下去的基础上,能够进行的操作尽可能的多
考虑到数据范围,我们可以直接 DP 出能够进行的操作数

设 $f[i][j]$ 表示前 $i$ 天剩下 $j$ 点血量需要多少回血操作
我们需要的就是 $max(i-f[i][j])$

设能够进行 $k$ 次操作
那么问题变为:在 $k$ 个回合内,能否通过 $1,3,4,5$ 这几个操作使得 $BOSS$ 血量恰好为 $0$

听说接下来是 在 $C\leq 10^8$ 的状态下,直接 BFS 搜索 + two-pointer

设造成伤害 $F$ 需要天数 $d$
需要满足两个条件:

$$ F[i]+F[j]+D-d[i]-d[j]\ge C\\ F[i]+F[j]\leq C\\ $$

条件一保证了能够造成不小于 $C$ 的伤害
条件二保证了固定伤害不超过 $C$,后续伤害必然是由每天一点伤害单独补齐,这同时也保证了 $d[i]+d[j]\leq D$

所以只需要按照 $F$ 排序后,枚举一个端点,满足 $F[i]+F[j]\leq C$ 的位置肯定是单调的
然后我们取 $F[x]-D[x]$ 的最大值作为另外一个端点即可

说实话,我觉得这道题出的很烂

Code

#include <bits/stdc++.h>
using namespace std;
const int mod = 9812347;
const int N = 110;
typedef pair <int, int> P;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
int n, m, mc;
int a[N], w[N], c[N], C;
int f[N][N], D;
P F[1000010];
int cnt;
struct node {
    int d, f, l;
};
struct Hash {
    P f[2000010];
    int nxt[2000010], head[mod], tot;
    void insert(P a) {
        int t = (1ll * a.first * 101 + a.second) % mod;
        ++ tot; f[tot] = a; nxt[tot] = head[t]; 
        head[t] = tot;
    }
    bool query(P a) {
        int t = (1ll * a.first * 101 + a.second) % mod;
        for(int i = head[t]; i; i = nxt[i])
            if(f[i] == a)
                return true;
        return false;
    }
}h;
void bfs() {
    queue <node> q;
    q.push({1, 1, 0});
    while(!q.empty()) {
        node now = q.front(); q.pop();
        if(now.d == D) continue;
        q.push({now.d + 1, now.f, now.l + 1});
        if(now.l > 1 && 1ll * now.f * now.l <= C) {
            P newnode = {now.f * now.l, now.l};
            if(h.query(newnode))
                continue;
            q.push({now.d + 1, now.f * now.l, now.l});
            F[++ cnt] = {now.f * now.l, now.d + 1};
            h.insert(newnode);
        }
    }
}
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 <= m; ++ i) {
        c[i] = read();
        C = max(C, c[i]);
    }
    f[0][0] = mc;
    for(int i = 1; i <= n; ++ i)
        for(int j = 0; j < i; ++ j)
            if(f[i - 1][j] >= a[i]) {
                f[i][j] = min(mc, max(f[i][j], f[i - 1][j] - a[i]));
                f[i][j + 1] = min(mc, max(f[i][j + 1], f[i - 1][j] - a[i] + w[i]));
                D = max(D, i - j);
            }
    bfs();
    sort(F + 1, F + cnt + 1);
    for(int i = 1; i <= m; ++ i) {
        if(c[i] <= D) puts("1");
        else {
            int maxvalue = INT_MIN;
            bool flag = 0;
            for(int j = cnt, k = 1; j >= 1 && !flag; -- j) {
                while(k < j && F[j].first + F[k].first <= c[i]) {
                    maxvalue = max(maxvalue, F[k].first - F[k].second);
                    ++ k;
                }
                if(c[i] <= D + (F[j].first - F[j].second) + maxvalue)
                    flag = 1;
                if(F[j].first <= c[i] && c[i] <= D + (F[j].first - F[j].second))
                    flag = 1;
            }
            printf("%d\n", flag);
        }
    }
    return 0;
}
Last modification:February 2nd, 2019 at 10:02 am

Leave a Comment