P4774 [NOI2018]屠龙勇士

    • 724通过
    • 3.1K提交
  • 题目提供者 chen_zhe Aya
  • 评测方式 云端评测
  • 标签 不定方程 同余,中国剩余定理 逆元 NOI系列 2018 O2优化 高性能
  • 难度 省选/NOI-
  • 时空限制 2000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小D 最近在网上发现了一款小游戏。游戏的规则如下:

    • 游戏的目标是按照编号$1 \rightarrow n$ 顺序杀掉$n$ 条巨龙,每条巨龙拥有一个初始的生命值$a_i$ 。同时每条巨龙拥有恢复能力,当其使用恢复能力时,它的生命值就会每次增加 $p_i$ ,直至生命值非负。只有在攻击结束后且当生命值恰好为 $0$ 时它才会死去。

    • 游戏开始时玩家拥有$m$ 把攻击力已知的剑,每次面对巨龙时,玩家只能选择一 把剑,当杀死巨龙后这把剑就会消失,但作为奖励,玩家会获得全新的一把剑。 小D 觉得这款游戏十分无聊,但最快通关的玩家可以获得ION2018 的参赛资格, 于是小D 决定写一个笨笨的机器人帮她通关这款游戏,她写的机器人遵循以下规则:

    • 每次面对巨龙时,机器人会选择当前拥有的,攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑,则选择攻击力最低的一把剑作为武器。

    • 机器人面对每条巨龙,它都会使用上一步中选择的剑攻击巨龙固定的$x$ 次,使巨龙的生命值减少$x \times ATK$ 。

    • 之后,巨龙会不断使用恢复能力,每次恢复$p_i$ 生命值。若在使用恢复能力前或某一次恢复后其生命值为$0$ ,则巨龙死亡,玩家通过本关。

    那么显然机器人的攻击次数是决定能否最快通关这款游戏的关键。小 D 现在得知了每条巨龙的所有属性,她想考考你,你知道应该将机器人的攻击次数$x$ 设置为多少,才能用最少的攻击次数通关游戏吗?

    当然如果无论设置成多少都无法通关游戏,输出$-1$ 即可。

    输入输出格式

    输入格式:

    从文件dragon.in 中读入数据。

    第一行一个整数T ,代表数据组数。

    接下来T 组数据,每组数据包含$5$ 行。

    • 每组数据的第一行包含两个整数,$n$ 和$m$ ,代表巨龙的数量和初始剑的数量;

    • 接下来一行包含$n$ 个正整数,第$i$ 个数表示第$i$ 条巨龙的初始生命值$a_i$ ;

    • 接下来一行包含$n$ 个正整数,第$i$ 个数表示第$i$ 条巨龙的恢复能力$p_i$ ;

    • 接下来一行包含$n$ 个正整数,第$i$ 个数表示杀死第$i$ 条巨龙后奖励的剑的攻击力;

    • 接下来一行包含$m$ 个正整数,表示初始拥有的$m$ 把剑的攻击力。

    输出格式:

    输出到文件dragon.out 中。 一共$T$ 行。

    第$i$ 行一个整数,表示对于第$i$ 组数据,能够使得机器人通关游戏的最小攻击次数$x$ ,如果答案不存在,输出$-1$。

    输入输出样例

    输入样例#1: 复制
    2
    3 3
    3 5 7
    4 6 10
    7 3 9
    1 9 1000
    3 2
    3 5 6
    4 8 7
    1 1 1
    1 1
    输出样例#1: 复制
    59
    -1

    说明

    第一组数据:

    • 开始时拥有的剑的攻击力为$\{1,9,10\}$,第$1$ 条龙生命值为$3$,故选择攻击力为$1$的剑,攻击$59$ 次,造成$59$ 点伤害,此时龙的生命值为$-56$,恢复14 次后生命值恰好为$0$,死亡。

    • 攻击力为$1$ 的剑消失,拾取一把攻击力为$7$ 的剑,此时拥有的剑的攻击力为 $\{7,9,10\}$,第2 条龙生命值为$5$,故选择攻击力为$7$ 的剑,攻击$59$ 次,造成$413$点伤害,此时龙的生命值为$-408$,恢复$68$ 次后生命值恰好为$0$,死亡。

    • 此时拥有的剑的攻击力为$\{3,9,10\}$,第$3$ 条龙生命值为$7$,故选择攻击力为$3$ 的剑,攻击$59$ 次,造成$177$ 点伤害,此时龙的生命值为$-170$,恢复$17$ 次后生命值恰好为0,死亡。

    • 没有比$59$ 次更少的通关方法,故答案为$59$。

    第二组数据: 不存在既能杀死第一条龙又能杀死第二条龙的方法,故无法通关,输出$-1$。

    【子任务】

    测试点编号 $n$ $m$ $p_i$ $a_i$ 攻击力 其他限制
    1 $\le 10^5$ $=1$ $=1$ $\le 10^5$ $=1$
    2 $\le 10^5$ $=1$ $=1$ $\le 10^5$ $=1$
    3 $\le 10^5$ $=1$ $=1$ $\le 10^5$ $\le 10^5$
    4 $\le 10^5$ $=1$ $=1$ $\le 10^5$ $\le 10^5$
    5 $\le 10^3$ $\le 10^3$ $\le 10^5$ $\le 10^5$ $\le 10^5$ 特性 1、特性 2
    6 $\le 10^3$ $\le 10^3$ $\le 10^5$ $\le 10^5$ $\le 10^5$ 特性 1、特性 2
    7 $\le 10^3$ $\le 10^3$ $\le 10^5$ $\le 10^5$ $\le 10^5$ 特性 1、特性 2
    8 $=1$ $=1$ $\le 10^8$ $\le 10^8$ $\le 10^6$ 特性 1
    9 $=1$ $=1$ $\le 10^8$ $\le 10^8$ $\le 10^6$ 特性 1
    10 $=1$ $=1$ $\le 10^8$ $\le 10^8$ $\le 10^6$ 特性 1
    11 $=1$ $=1$ $\le 10^8$ $\le 10^8$ $\le 10^6$ 特性 1
    12 $=1$ $=1$ $\le 10^8$ $\le 10^8$ $\le 10^6$ 特性 1
    13 $=1$ $=1$ $\le 10^8$ $\le 10^8$ $\le 10^6$ 特性 1
    14 $=10^5$ $=10^5$ $=1$ $\le 10^8$ $\le 10^6$ 无特殊限制
    15 $=10^5$ $=10^5$ $=1$ $\le 10^8$ $\le 10^6$ 无特殊限制
    16 $\le 10^5$ $\le 10^5$ 所有 $p_i$ 是质数 $\le 10^{12}$ $\le 10^6$ 特性 1
    17 $\le 10^5$ $\le 10^5$ 所有 $p_i$ 是质数 $\le 10^{12}$ $\le 10^6$ 特性 1
    18 $\le 10^5$ $\le 10^5$ 无特殊限制 $\le 10^{12}$ $\le 10^6$ 特性 1
    19 $\le 10^5$ $\le 10^5$ 无特殊限制 $\le 10^{12}$ $\le 10^6$ 特性 1
    20 $\le 10^5$ $\le 10^5$ 无特殊限制 $\le 10^{12}$ $\le 10^6$ 特性 1

    特性 1 是指:对于任意的 $i$,$a_i \le p_i$。

    特性 2 是指:$\operatorname{lcm}(p_i) \le 10^6$,即所有 $p_i$ 的最小公倍数不大于 $10^6$。

    对于所有的测试点,$T \le 5$,所有武器的攻击力 $\le 10^6$,所有 $p_i$ 的最小公倍数 $\le 10^{12}$。

    保证 $ T, n, m $ 均为正整数。

    【提示】

    你所用到的中间结果可能很大,注意保存中间结果的变量类型。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。