「NOI2018」屠龙勇士

发表于 | 分类于 | | 浏览量： 次

扩展中国剩余定理的裸题，但是好难写啊。

传送门

洛谷P4774

BZOJ5418

题解

首先，可以写个平衡树来维护每次面对巨龙时可选的剑，并事先构造出面对每一条巨龙时用的剑的攻击力。

写个毛线平衡树，调set多省事。

然后就是EXCRT的裸题了。

由于这题的数据范围卡的比较紧，一下子没注意某个地方就爆long long了，得龟速乘。

还有就是和EXCRT的裸题不一样的是，这题要求每一条巨龙的生命值小于等于0过，所以最后还需要再扫一趟检查一遍。

细节还是比较多的，如果是蒟蒻我在现场的话，还真的不一定能AC。

代码

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
#include<set>
#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=100005;
int T,n,m;LL A[maxn],P[maxn],K[maxn],ATK[maxn];multiset<LL> S;multiset<LL>::iterator p;
inline LL read()
{
	LL ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
LL Exgcd(LL a,LL b,LL& x,LL& y)
{
	if(!b){x=1;y=0;return a;}
	LL d=Exgcd(b,a%b,x,y);
	LL t=x;x=y;y=t-a/b*y;
	return d;
}
LL Multiply(LL x,LL y,LL TT)
{
	if(y<0){x=-x;y=-y;}
	LL ret=0,w=x;
	while(y)
	{
		if(y&1) ret=(ret+w)%TT;
		w=(w+w)%TT;y>>=1;
	}
	return ret;
}
inline void EXCRT()
{
	LL LCM=1,X=0,Y,Z,D,D2,E,F;
	for(int i=1;i<=n;i++)
	{
		D=Exgcd(ATK[i],P[i],Z,Y);
		if(A[i]%D){printf("%d\n",-1);return;}
		Z=Multiply(Z,A[i]/D,P[i]/D);
		D2=Exgcd(LCM,P[i]/D,F,E);
		if((Z-X)%D2){printf("%d\n",-1);return;}
		F=Multiply(F,(Z-X)/D2,P[i]/D/D2);
		X=X+Multiply(F,LCM,LCM/D2*(P[i]/D));
		LCM=LCM/D2*(P[i]/D);
		X=(X%LCM+LCM)%LCM;
	}
	for(int i=1;i<=n;i++)
		if(X*ATK[i]<A[i])
			X+=(A[i]-X*ATK[i]+LCM*ATK[i]-1)/(LCM*ATK[i])*LCM;
	printf("%lld\n",X);
}
int main()
{
	T=read();
	while(T--)
	{
		n=read();m=read();S.clear();
		for(int i=1;i<=n;i++) A[i]=read();
		for(int i=1;i<=n;i++) P[i]=read();
		for(int i=1;i<=n;i++) K[i]=read();
		for(int i=1;i<=m;i++) S.insert(read());
		for(int i=1;i<=n;i++)
		{
			p=S.lower_bound(A[i]);
			if(*p==A[i]){ATK[i]=*p;S.erase(p);}
			else if(p!=S.begin()){p--;ATK[i]=*p;S.erase(p);}
			else{ATK[i]=*S.begin();S.erase(S.begin());}
			S.insert(K[i]);
		}
		EXCRT();
	}
	return 0;
}