NOI2018-day2-屠龙勇士(dragon)
相关题目:[NOI2018]屠龙勇士

【题目描述】

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

  • 游戏的目标是按照编号 11~nn 顺序杀掉 nn 条巨龙,每条巨龙拥有一个初始的生命值 aia_i 。同时每条巨龙拥有恢复能力,当其使用恢复能力时,它的生命值就会每次增加 pip_i,直至生命值非负。只有在攻击结束后且当生命值恰好00 时它才会死去。
  • 游戏开始时玩家拥有 mm 把攻击力已知的剑,每次面对巨龙时,玩家只能选择一把剑,当杀死巨龙后这把剑就会消失,但作为奖励,玩家会获得全新的一把剑。

      小 D 觉得这款游戏十分无聊,但最快通关的玩家可以获得 ION2018 的参赛资格, 于是小 D 决定写一个笨笨的机器人帮她通关这款游戏,她写的机器人遵循以下规则:

  • 每次面对巨龙时,机器人会选择当前拥有的,攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑,则选择攻击力最低的一把剑作为武器。
  • 机器人面对每条巨龙,它都会使用上一步中选择的剑攻击巨龙固定的 xx 次,使巨龙的生命值减少 x×ATKx \times ATK
  • 之后,巨龙会不断使用恢复能力,每次恢复 pip_i 生命值。若在使用恢复能力前或某一次恢复后其生命值为 00,则巨龙死亡,玩家通过本关。

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

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

【输入格式】

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

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

      接下来 TT 组数据,每组数据包含 55 行。

  • 每组数据的第一行包含两个整数,nnmm,代表巨龙的数量和初始剑的数量;
  • 接下来一行包含 nn 个正整数,第 ii 个数表示第 ii 条巨龙的初始生命值 aia_i
  • 接下来一行包含 nn 个正整数,第 ii 个数表示第 ii 条巨龙的恢复能力 pip_i
  • 接下来一行包含 nn 个正整数,第 ii 个数表示杀死第 ii 条巨龙后奖励的剑的攻击力;
  • 接下来一行包含 mm 个正整数,表示初始拥有的 mm 把剑的攻击力。

【输出格式】

      输出到文件 dragon.out 中。

      一共 TT 行。

      第 ii 行一个整数,表示对于第 ii 组数据,能够使得机器人通关游戏的最小攻击次数 xx,如果答案不存在,输出 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

【样例 1 解释】

      第一组数据:

  • 开始时拥有的剑的攻击力为 {1,9,10}\{1,9,10\},第 11 条龙生命值为 33,故选择攻击力为 11 的剑,攻击 5959 次,造成 5959 点伤害,此时龙的生命值为 56-56,恢复 1414 次后生命值恰好为 00,死亡。
  • 攻击力为 11 的剑消失,拾取一把攻击力为 77 的剑,此时拥有的剑的攻击力为 {7,9,10}\{7,9,10\},第 22 条龙生命值为 55,故选择攻击力为 77 的剑,攻击 5959 次,造成 -408 68 0$,死亡。
  • 此时拥有的剑的攻击力为 {3,9,10}\{3,9,10\},第 33 条龙生命值为 77,故选择攻击力为 33 的剑,攻击 5959 次,造成 177177 点伤害,此时龙的生命值为 170-170,恢复 1717 次后生命值恰好为 00,死亡。
  • 没有比 5959 次更少的通关方法,故答案为 5959

      第二组数据:

  • 不存在既能杀死第一条龙又能杀死第二条龙的方法,故无法通关,输出 1-1

【样例 2】

      见附加文件中的 dragon2.indragon2.ans

【子任务】

      特性 11 是指:对于任意的 ii 。       特性 是指: 即所有 的最小公倍数不大于 。       对于所有的测试点, ,所有武器的攻击力 ,所有 pip_i 的最小公倍数 1012\le 10^{12}

Solution

multiset 预处理每次选定剑的伤害,然后用 exCRT 合并就好了。

Code

总时间:3927 ms / 内存:6396 KiB     -O2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <cstdio>
#include <cctype>
#include <set>
#include <algorithm>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++i)
typedef long long ll;
const int N = 100002;
template <class T>inline void read(T &x) {
x=0; int f=1; char ch=getchar();
while(!isdigit(ch)){if(f=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x*=f;
}
inline ll mul(ll x,ll y,ll p) {
ll res=x*y-(ll)((long double)x*y/p)*p;
return res<0?res+p:res;
}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void exgcd(ll a,ll b,ll &x,ll &y) {
if(b==0)x=1,y=0;
else exgcd(b,a%b,y,x),y-=(a/b)*x;
}
ll inv(ll a,ll b) {ll x,y;exgcd(a,b,x,y);return (x+b)%b;}

int n, m;
ll a[N], p[N], z[N]; int c[N], v[N];

inline ll solve1() {
ll ans=0;
rep(i,1,n) ans=max(ans,(a[i]-1)/v[i]+1);
return ans;
}

inline ll solve() {
rep(i,1,n) {
ll A=v[i]%p[i], B=a[i]%p[i], g=gcd(A,p[i]);
if(B%g) return -1;
A/=g, B/=g, p[i]/=g;
z[i] = mul(inv(A,p[i]),B,p[i]);
}
rep(i,2,n) {
ll g = gcd(p[i-1],p[i]);
if((z[i]-z[i-1])%g) return -1;
ll x = mul(inv(p[i-1]/g,p[i]/g),(z[i]-z[i-1])/g,p[i]/g);
ll d = p[i-1]/g*p[i];
x=mul(x,p[i-1],d), z[i]=(x+z[i-1])%d, p[i]=d;
}
return z[n];
}

int main() {
freopen("dragon.in","r",stdin);
freopen("dragon.out","w",stdout);
int T; read(T);
while(T--) {
read(n), read(m);
rep(i,1,n) read(a[i]);
rep(i,1,n) read(p[i]);
rep(i,1,n) read(c[i]);
multiset<ll> s;
multiset<ll>::iterator it;
int w; rep(i,1,m) read(w),s.insert(w);
rep(i,1,n) {
if(*s.begin()>=a[i]) v[i]=*s.begin(),s.erase(s.begin());
else it=s.upper_bound(a[i]),v[i]=*--it,s.erase(it);
s.insert(c[i]);
}
if(*(p+1)==1) cout << solve1() << endl;
else cout << solve() << endl;
}
fclose(stdin);
fclose(stdout);
return 0;
}