本文主要是介绍P4774 [NOI2018] 屠龙勇士,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
#1024程序员节征文活动
[NOI2018] 屠龙勇士
搬题面:
[NOI2018] 屠龙勇士
题目描述
小 D 最近在网上发现了一款小游戏。游戏的规则如下:
- 游戏的目标是按照编号 1 → n 1 \rightarrow n 1→n 顺序杀掉 n n n 条巨龙,每条巨龙拥有一个初始的生命值 a i a_i ai 。同时每条巨龙拥有恢复能力,当其使用恢复能力时,它的生命值就会每次增加 p i p_i pi ,直至生命值非负。只有在攻击结束后且当生命值 恰好 为 0 0 0 时它才会死去。
- 游戏开始时玩家拥有 m m m 把攻击力已知的剑,每次面对巨龙时,玩家只能选择一把剑,当杀死巨龙后这把剑就会消失,但作为奖励,玩家会获得全新的一把剑。
小 D 觉得这款游戏十分无聊,但最快通关的玩家可以获得 ION2018 的参赛资格,于是小 D 决定写一个笨笨的机器人帮她通关这款游戏,她写的机器人遵循以下规则:
- 每次面对巨龙时,机器人会选择当前拥有的,攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑,则选择 攻击力最低 的一把剑作为武器。
- 机器人面对每条巨龙,它都会使用上一步中选择的剑攻击巨龙固定的 x x x 次,使巨龙的生命值减少 x × A T K x \times ATK x×ATK 。
- 之后,巨龙会不断使用恢复能力,每次恢复 p i p_i pi 生命值。若在使用恢复能力前或某一次恢复后其生命值为 0 0 0 ,则巨龙死亡,玩家通过本关。
那么显然机器人的攻击次数是决定能否最快通关这款游戏的关键。小 D 现在得知了每条巨龙的所有属性,她想考考你,你知道应该将机器人的攻击次数 x x x 设置为多少,才能用最少的攻击次数通关游戏吗?
当然如果无论设置成多少都无法通关游戏,输出 − 1 -1 −1 即可。
输入格式
第一行一个整数 T T T,代表数据组数。
接下来 T T T 组数据,每组数据包含 5 5 5 行。
- 每组数据的第一行包含两个整数, n n n 和 m m m ,代表巨龙的数量和初始剑的数量;
- 接下来一行包含 n n n 个正整数,第 i i i 个数表示第 i i i 条巨龙的初始生命值 a i a_i ai;
- 接下来一行包含 n n n 个正整数,第 i i i 个数表示第 i i i 条巨龙的恢复能力 p i p_i pi;
- 接下来一行包含 n n n 个正整数,第 i i i 个数表示杀死第 i i i 条巨龙后奖励的剑的攻击力;
- 接下来一行包含 m m m 个正整数,表示初始拥有的 m m m 把剑的攻击力。
输出格式
一共 T T T 行。
第 i i i 行一个整数,表示对于第 i i i 组数据,能够使得机器人通关游戏的最小攻击次数 x x x ,如果答案不存在,输出 − 1 -1 −1。
样例 #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
提示
更多样例
更多样例请在附加文件中下载。
样例 2
见附加文件中的 dragon2.in
与 dragon2.ans
。
样例 1 解释
第一组数据:
-
开始时拥有的剑的攻击力为 { 1 , 9 , 10 } \{1,9,10\} {1,9,10},第 1 1 1 条龙生命值为 3 3 3,故选择攻击力为 1 1 1 的剑,攻击 59 59 59 次,造成 59 59 59 点伤害,此时龙的生命值为 − 56 -56 −56,恢复 14 次后生命值恰好为 0 0 0,死亡。
-
攻击力为 1 1 1 的剑消失,拾取一把攻击力为 7 7 7 的剑,此时拥有的剑的攻击力为
{ 7 , 9 , 10 } \{7,9,10\} {7,9,10},第 2 条龙生命值为 5 5 5,故选择攻击力为 7 7 7 的剑,攻击 59 59 59 次,造成 413 413 413 点伤害,此时龙的生命值为 − 408 -408 −408,恢复 68 68 68 次后生命值恰好为 0 0 0,死亡。 -
此时拥有的剑的攻击力为 { 3 , 9 , 10 } \{3,9,10\} {3,9,10},第 3 3 3 条龙生命值为 7 7 7,故选择攻击力为 3 3 3 的剑,攻击 59 59 59 次,造成 177 177 177 点伤害,此时龙的生命值为 − 170 -170 −170,恢复 17 17 17 次后生命值恰好为 0,死亡。
-
没有比 59 59 59 次更少的通关方法,故答案为 59 59 59。
第二组数据:
不存在既能杀死第一条龙又能杀死第二条龙的方法,故无法通关,输出 − 1 -1 −1。
子任务
测试点编号 | n n n | m m m | p i p_i pi | a i a_i ai | 攻击力 | 其他限制 |
---|---|---|---|---|---|---|
1 | ≤ 1 0 5 \le 10^5 ≤105 | = 1 =1 =1 | = 1 =1 =1 | ≤ 1 0 5 \le 10^5 ≤105 | = 1 =1 =1 | 无 |
2 | ≤ 1 0 5 \le 10^5 ≤105 | = 1 =1 =1 | = 1 =1 =1 | ≤ 1 0 5 \le 10^5 ≤105 | = 1 =1 =1 | 无 |
3 | ≤ 1 0 5 \le 10^5 ≤105 | = 1 =1 =1 | = 1 =1 =1 | ≤ 1 0 5 \le 10^5 ≤105 | ≤ 1 0 5 \le 10^5 ≤105 | 无 |
4 | ≤ 1 0 5 \le 10^5 ≤105 | = 1 =1 =1 | = 1 =1 =1 | ≤ 1 0 5 \le 10^5 ≤105 | ≤ 1 0 5 \le 10^5 ≤105 | 无 |
5 | ≤ 1 0 3 \le 10^3 ≤103 | ≤ 1 0 3 \le 10^3 ≤103 | ≤ 1 0 5 \le 10^5 ≤105 | ≤ 1 0 5 \le 10^5 ≤105 | ≤ 1 0 5 \le 10^5 ≤105 | 特性 1、特性 2 |
6 | ≤ 1 0 3 \le 10^3 ≤103 | ≤ 1 0 3 \le 10^3 ≤103 | ≤ 1 0 5 \le 10^5 ≤105 | ≤ 1 0 5 \le 10^5 ≤105 | ≤ 1 0 5 \le 10^5 ≤105 | 特性 1、特性 2 |
7 | ≤ 1 0 3 \le 10^3 ≤103 | ≤ 1 0 3 \le 10^3 ≤103 | ≤ 1 0 5 \le 10^5 ≤105 | ≤ 1 0 5 \le 10^5 ≤105 | ≤ 1 0 5 \le 10^5 ≤105 | 特性 1、特性 2 |
8 | = 1 =1 =1 | = 1 =1 =1 | ≤ 1 0 8 \le 10^8 ≤108 | ≤ 1 0 8 \le 10^8 ≤108 | ≤ 1 0 6 \le 10^6 ≤106 | 特性 1 |
9 | = 1 =1 =1 | = 1 =1 =1 | ≤ 1 0 8 \le 10^8 ≤108 | ≤ 1 0 8 \le 10^8 ≤108 | ≤ 1 0 6 \le 10^6 ≤106 | 特性 1 |
10 | = 1 =1 =1 | = 1 =1 =1 | ≤ 1 0 8 \le 10^8 ≤108 | ≤ 1 0 8 \le 10^8 ≤108 | ≤ 1 0 6 \le 10^6 ≤106 | 特性 1 |
11 | = 1 =1 =1 | = 1 =1 =1 | ≤ 1 0 8 \le 10^8 ≤108 | ≤ 1 0 8 \le 10^8 ≤108 | ≤ 1 0 6 \le 10^6 ≤106 | 特性 1 |
12 | = 1 =1 =1 | = 1 =1 =1 | ≤ 1 0 8 \le 10^8 ≤108 | ≤ 1 0 8 \le 10^8 ≤108 | ≤ 1 0 6 \le 10^6 ≤106 | 特性 1 |
13 | = 1 =1 =1 | = 1 =1 =1 | ≤ 1 0 8 \le 10^8 ≤108 | ≤ 1 0 8 \le 10^8 ≤108 | ≤ 1 0 6 \le 10^6 ≤106 | 特性 1 |
14 | = 1 0 5 =10^5 =105 | = 1 0 5 =10^5 =105 | = 1 =1 =1 | ≤ 1 0 8 \le 10^8 ≤108 | ≤ 1 0 6 \le 10^6 ≤106 | 无特殊限制 |
15 | = 1 0 5 =10^5 =105 | = 1 0 5 =10^5 =105 | = 1 =1 =1 | ≤ 1 0 8 \le 10^8 ≤108 | ≤ 1 0 6 \le 10^6 ≤106 | 无特殊限制 |
16 | ≤ 1 0 5 \le 10^5 ≤105 | ≤ 1 0 5 \le 10^5 ≤105 | 所有 p i p_i pi 是质数 | ≤ 1 0 12 \le 10^{12} ≤1012 | ≤ 1 0 6 \le 10^6 ≤106 | 特性 1 |
17 | ≤ 1 0 5 \le 10^5 ≤105 | ≤ 1 0 5 \le 10^5 ≤105 | 所有 p i p_i pi 是质数 | ≤ 1 0 12 \le 10^{12} ≤1012 | ≤ 1 0 6 \le 10^6 ≤106 | 特性 1 |
18 | ≤ 1 0 5 \le 10^5 ≤105 | ≤ 1 0 5 \le 10^5 ≤105 | 无特殊限制 | ≤ 1 0 12 \le 10^{12} ≤1012 | ≤ 1 0 6 \le 10^6 ≤106 | 特性 1 |
19 | ≤ 1 0 5 \le 10^5 ≤105 | ≤ 1 0 5 \le 10^5 ≤105 | 无特殊限制 | ≤ 1 0 12 \le 10^{12} ≤1012 | ≤ 1 0 6 \le 10^6 ≤106 | 特性 1 |
20 | ≤ 1 0 5 \le 10^5 ≤105 | ≤ 1 0 5 \le 10^5 ≤105 | 无特殊限制 | ≤ 1 0 12 \le 10^{12} ≤1012 | ≤ 1 0 6 \le 10^6 ≤106 | 特性 1 |
特性 1 是指:对于任意的 i i i, a i ≤ p i a_i \le p_i ai≤pi。
特性 2 是指: lcm ( p i ) ≤ 1 0 6 \operatorname{lcm}(p_i) \le 10^6 lcm(pi)≤106,即所有 p i p_i pi 的 最小公倍数 不大于 1 0 6 10^6 106。
对于所有的测试点, T ≤ 5 T \le 5 T≤5,所有武器的攻击力 ≤ 1 0 6 \le 10^6 ≤106,所有 p i p_i pi 的最小公倍数 ≤ 1 0 12 \le 10^{12} ≤1012。
保证 $ T, n, m $ 均为正整数。
提示
你所用到的中间结果可能很大,注意保存中间结果的变量类型。
注意不要读错题, x x x 为固定数值。
根据题意可列得
{ b 1 x ≡ a 1 ( m o d p 1 ) b 2 x ≡ a 2 ( m o d p 2 ) … b n x ≡ a n ( m o d p n ) \begin{cases}b_1x\equiv a_1(\mod p_1)\\b_2x\equiv a_2(\mod p_2)\\\dots\\b_nx\equiv a_n(\mod p_n)\end{cases} ⎩ ⎨ ⎧b1x≡a1(modp1)b2x≡a2(modp2)…bnx≡an(modpn)
注意到 p i p_i pi 并不互质,用扩展中国剩余定理求解,模拟抽剑的过程可以用平衡树维护,也可以使用vector/multimap 维护。
这篇关于P4774 [NOI2018] 屠龙勇士的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!