【NOI2018】屠龙骑士 题解

题目

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

也就是 这个剑的选择已经给定了。

找到选的剑可以通过手写平衡树,但是这是D2T1 手写平衡树太毒瘤了 我们有内置红黑树的set/multiset!支持upper_bound和lower_bound。

显然攻击力可能会重复,所以不能用set。

那就直接multiset上!

选好了显然要计算还需要多少刀才能砍死巨龙。

首先显然要把巨龙砍到再砍一刀生命就为负数,这些刀必须砍。

然后剩下的,设攻击力为s,恢复能力为p,生命为a。

gcd(s,p)a\gcd(s,p)|a的前提下(否则就打不死了),可以把a,p,sa,p,s全部除以gcd(a,p)\gcd(a,p),这样就方便计算了。下面的a,p,sa,p,s都是除后的。

首先可以exgcd解出最少要砍几刀。

这个值需要 ,如果=0并且 ,那还最少砍的次数就应该是p。如果a=0,还最少要砍的次数就应该是0。

假设最少要砍k刀。

之后显然多砍p刀是没有影响的。

就得到了一个方程:

xkx\ge k

由于这些方程不互质,就不能直接CRT而是要用exCRT。

他们的写法都好玄学我完全看不懂

把每个方程的p分解质因数,拆成O(logp)O(\log p)个方程。

然后把模数的底数相同的合并,就合并成O(loglcm)O(\log \mathrm{lcm})个方程了。

但是分解是O(np)O(n\sqrt{p})的好慢啊...

可以先计算出lcm并对lcm分解质因数 显然不需要Pollard Rho可以直接根号分解,然后底数就只有可能是这 个质因数。

分解的时候就只需要考虑这些质因数了 。

exCRT出答案以后,如果不满足k\ge k的限制,,, 由于答案是 意义下的,设算出来答案为S,max{k}=M\max\{k\}=M,答案只需要+ 就好。

显然

时间复杂度

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
/*
Author: CNYALI_LK
LANG: C++
PROG: dragon.cpp
Mail: cnyalilk@vip.qq.com
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define DEBUG printf("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define Debug debug("Passing [%s] in LINE %lld\n",__FUNCTION__,__LINE__)
#define all(x) x.begin(),x.end()
#define x first
#define y second
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
typedef long long ll;
typedef pair<ll,ll> pii;
template<class T>ll chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>ll chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
ll read(){
ll s=0,base=1;
char c;
while(!isdigit(c=getchar()))if(c=='-')base=-base;
while(isdigit(c)){s=s*10+(c^48);c=getchar();}
return s*base;
}
multiset<ll> t;
multiset<ll>::iterator it;
ll a[102424],p[102424],b[102424],ys[102424],atl[102424],_ans;
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){x=1;y=0;return;}
exgcd(b,a%b,y,x);
y-=(a/b)*x;
}
ll Calc(ll a,ll b,ll &c,ll &d,ll &e){
e=b/a;
b%=a;
ll h=gcd(a,c),x,y;
if(b%h)return 1;
a/=h;b/=h;c/=h;
exgcd(a,c,x,y);
if(b)
x=((x%c+c)%c*b+c-1)%c+1;
else
x=0;
e+=x;
d=e%c;
chkmax(_ans,e);
return 0;
}
ll st,ax[102424],px[102424];
ll mul(ll a,ll b,ll p){
ll c=0;
for(;b;b>>=1,a=(a+a)%p)if(b&1)c=(c+a)%p;
return c;

}
ll CRT(ll n){
ll s=1,sum=0,x,y;
for(ll i=1;i<=n;++i)s*=px[i];
for(ll i=1;i<=n;++i){
exgcd(s/px[i],px[i],x,y);
x=(x%px[i]+px[i])%px[i];
sum=(sum+mul(mul(x,(s/px[i]),s),ax[i],s))%s;
}
return sum;
}
void calc(ll n){
ll s=1,h,pxy,xl,stdc;
for(ll i=1;i<=n;++i)s=s/gcd(s,p[i])*p[i];
stdc=s;
st=0;
for(ll i=2;i*i<=s;++i)if(!(s%i)){
++st;
px[st]=1;
ax[st]=0;
while(!(s%i)){
s/=i;
px[st]*=i;
}
xl=1;
for(ll j=1;j<=n;++j)if(!(p[j]%i)){
pxy=1;
while(!(p[j]%i)){
pxy*=i;
p[j]/=i;
}
if(pxy>xl){
if(ys[j]%xl!=ax[st]){printf("-1\n");return;}
else {xl=pxy;ax[st]=ys[j]%pxy;}
}
else{
if(ys[j]%pxy!=ax[st]%pxy){printf("-1\n");return;}
}
}
}
if(s>1){
++st;
px[st]=s;
ax[st]=0;
xl=1;
for(ll j=1;j<=n;++j)if(!(p[j]%s)){
pxy=1;
while(!(p[j]%s)){
pxy*=s;
p[j]/=s;
}
if(pxy>xl){
if(ys[j]%xl!=ax[st]){printf("-1\n");return;}
else {xl=pxy;ax[st]=ys[j]%pxy;}
}
else{
if(ys[j]%pxy!=ax[st]%pxy){printf("-1\n");return;}
}
}
}
ll ans=CRT(st),ax;
if(ans<_ans){
ax=((_ans-ans)/stdc)+!!((_ans-ans)%stdc);
ans=ans+ax*stdc;
}
printf("%lld\n",ans);
}
int main(){
freopen("dragon.in","r",stdin);
freopen("dragon.out","w",stdout);
ll T,n,m,s;
T=read();
for(;T;--T){
n=read();m=read();
for(ll i=1;i<=n;++i)a[i]=read();
for(ll i=1;i<=n;++i)p[i]=read();
for(ll i=1;i<=n;++i)b[i]=read();
t.erase(t.begin(),t.end());
for(ll i=1;i<=m;++i)t.insert(read());
ll ok=1;
_ans=0;
for(ll i=1;i<=n;++i){
it=t.upper_bound(a[i]);
if(it==t.begin())s=*it;
else s=*(--it);
t.erase(it);
if(Calc(s,a[i],p[i],ys[i],atl[i])){printf("-1\n");ok=0;break;};
t.insert(b[i]);
}
if(ok)calc(n);
}
return 0;
}
文章目录
|

博客使用Disqus作为评论系统