目录

[LOJ 2721][UOJ 396][BZOJ 5418][NOI 2018]屠龙勇士

迁移提示
本文迁移自博客园, 原文链接

[LOJ 2721][UOJ 396][BZOJ 5418][NOI 2018]屠龙勇士

题意

题面好啰嗦啊直接粘LOJ题面好了

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

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

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

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

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

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

杀龙的时候需要三步必杀, 不能重复多次qwq…

$n\le 10^5,m\le 10^5,a_i\le 10^{12}$.

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

题解

乍一看这题神仙的一匹, 然而冷静分析一下可以发现:

拿来淦龙的剑都是固定的, 而且每次相当于把龙的血打到一个不大于 $0$ 的 $p_i$ 的倍数就可以完成任务了.

那么也就是说只要让 $x$ 满足:

$$ x\times ATK_i\equiv a_i \pmod {p_i}\\ x\times ATK_i\ge a_i $$

先来搞第一个限制.

不难发现这个限制相当于下式:

$$ x\times ATK_i+k\times p_i=a_i $$

其中 $ATK_i,p_i,a_i$ 都是确定的, 显然这个东西可以随手 ExGCD 搞一搞解出一个 $\bmod p_i$ 意义下的 $x$.

不过注意这一步要对 $ATK_i$ 和 $p_i$ 进行约分, 不然逆元不唯一就会解出奇怪的东西qaq(sb rvalue在这坑了一个小时)…

然后我们不难发现我们得到了一堆形如这样的方程组:

$$ x\equiv r_i \pmod {p_i} $$

这不裸的 CRT 么?

然而 $p_i$ 不互质. 并不能直接 CRT.

考虑 ExCRT. ExCRT 的大体思路是通过 ExGCD 来合并两个同余方程.

假设我们现在有两个同余方程:

$$ \begin{cases} x\equiv a &\pmod n\\ x\equiv b &\pmod m \end{cases} $$

不难发现它等价于:

$$ \begin{cases} x = a + pn\\ x = b + qm \end{cases} $$

那么也就是说:

$$ a+pn=b+qm $$

移项可得:

$$ a-b=qm-pn $$

好了我们可以 ExGCD 了.

算出 $p$ 和 $q$ 之后可以用 $x=a+pn=b+pm$ 算出 $x$ 来. 它与所有 $\bmod \gcd(n,m)$ 意义下同余的值都是这两个方程的解. 显然我们直接对 $\gcd(n,m)$ 取模就可以得到最小值了.

一直这样合并下去, 只要 ExGCD 的时候出锅那么根据Bézout定理这个方程组无解.

然后我们可以得到一个 $\bmod \operatorname{lcm} {p_i}$ 的 $x$. 接着考虑第二种限制.

显然我们可以对当前已有的 $x$ 计算它是否满足 $x\times ATK_i\ge a_i$, 如果不满足的话把 $x$ 变为 $\bmod \operatorname{lcm} {p_i}$ 意义下同余的最小满足条件的值就可以了. 不难发现答案就是:

$$ x+\operatorname{lcm}\{p_i\}\times \max_{1\le i\le n}\left \lceil \frac {\left \lceil \frac{a_i}{ATK_i}\right \rceil-x}{\operatorname{lcm}\{p_i\}}\right \rceil $$

UOJ因为有Hack所以数据比LOJ强一些, LOJ过了之后建议在UOJ上交一发.

参考代码

下面这份代码在发文时没有被Hack qwq…

 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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>

const int MAXN=1e5+10;
typedef long long intEx;

struct Equation{
	intEx mod;
	intEx rest;
};
Equation E[MAXN];

int n;
int m;
intEx a[MAXN];
intEx p[MAXN];
intEx w[MAXN];
intEx atk[MAXN];

intEx Mul(intEx,intEx,intEx);
intEx ExGCD(intEx,intEx,intEx&,intEx&);

int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)
			scanf("%lld",a+i);
		for(int i=1;i<=n;i++)
			scanf("%lld",p+i);
		for(int i=1;i<=n;i++)
			scanf("%lld",w+i);
		std::multiset<intEx> s;
		for(int i=1;i<=m;i++){
			intEx x;
			scanf("%lld",&x);
			s.insert(x);
		}
		try{
			for(int i=1;i<=n;i++){
				E[i].mod=p[i];
				auto it=s.upper_bound(a[i]);
				if(it!=s.begin())
					--it;
				intEx t;
				atk[i]=*it;
				s.erase(it);
				intEx gcd=ExGCD(atk[i],p[i],E[i].rest,t);
				if(a[i]%gcd!=0)
					throw std::logic_error(R"(a[i]%gcd!=0)");
				E[i].mod/=gcd;
				E[i].rest=Mul(a[i]/gcd,E[i].rest,E[i].mod);
				(E[i].rest+=E[i].mod)%=E[i].mod;
				s.insert(w[i]);
			}
			for(int i=2;i<=n;i++){
				intEx x,y;
				intEx gcd=ExGCD(E[i-1].mod,E[i].mod,x,y);
				intEx lcm=E[i-1].mod/gcd*E[i].mod;
				if((E[i-1].rest-E[i].rest)%gcd!=0)
					throw std::logic_error(R"((E[i].rest-E[i-1].rest)%gcd!=0 @)"+std::to_string(i));
				intEx scale=(E[i-1].rest-E[i].rest)/gcd;
				(E[i].rest+=Mul(Mul(scale,y,lcm),E[i].mod,lcm))%=lcm;
				E[i].mod=lcm;
				E[i].rest=(E[i].rest+lcm)%lcm;
			}
			intEx scale=0;
			for(int i=1;i<=n;i++)
				scale=std::max(scale,((a[i]+atk[i]-1)/atk[i]-E[n].rest+E[n].mod-1)/E[n].mod);
			printf("%lld\n",E[n].rest+scale*E[n].mod);
		}
		catch(std::logic_error x){
			puts("-1");
			continue;
		}
	}
	return 0;
}

intEx ExGCD(intEx a,intEx b,intEx& x,intEx& y){
	if(b==0){
		x=1;
		y=0;
		return a;
	}
	intEx gcd=ExGCD(b,a%b,y,x);
	y-=(a/b)*x;
	return gcd;
}

intEx Mul(intEx a,intEx b,intEx p){
	return __int128(a)*b%p;
}

https://pic.rvalue.moe/2021/08/02/d206f2b21f306.jpg