P4774 [NOI2018] 屠龙勇士
题目描述
小 D 最近在网上发现了一款小游戏。游戏的规则如下:
- 游戏的目标是按照编号 \(1 \rightarrow n\) 顺序杀掉 \(n\) 条巨龙,每条巨龙拥有一个初始的生命值 \(a_i\) 。同时每条巨龙拥有恢复能力,当其使用恢复能力时,它的生命值就会每次增加 \(p_i\) ,直至生命值非负。只有在攻击结束后且当生命值 恰好 为 \(0\) 时它才会死去。
- 游戏开始时玩家拥有 \(m\) 把攻击力已知的剑,每次面对巨龙时,玩家只能选择一把剑,当杀死巨龙后这把剑就会消失,但作为奖励,玩家会获得全新的一把剑。
小 D 觉得这款游戏十分无聊,但最快通关的玩家可以获得 ION2018 的参赛资格,于是小 D 决定写一个笨笨的机器人帮她通关这款游戏,她写的机器人遵循以下规则:
- 每次面对巨龙时,机器人会选择当前拥有的,攻击力不高于巨龙初始生命值中攻击力最大的一把剑作为武器。如果没有这样的剑,则选择 攻击力最低 的一把剑作为武器。
- 机器人面对每条巨龙,它都会使用上一步中选择的剑攻击巨龙固定的 \(x\) 次,使巨龙的生命值减少 \(x \times ATK\) 。
- 之后,巨龙会不断使用恢复能力,每次恢复 \(p_i\) 生命值。若在使用恢复能力前或某一次恢复后其生命值为 \(0\) ,则巨龙死亡,玩家通过本关。
那么显然机器人的攻击次数是决定能否最快通关这款游戏的关键。小 D 现在得知了每条巨龙的所有属性,她想考考你,你知道应该将机器人的攻击次数 \(x\) 设置为多少,才能用最少的攻击次数通关游戏吗?
当然如果无论设置成多少都无法通关游戏,输出 \(-1\) 即可。
数据范围
对于所有的测试点,\(T \le 5\),所有武器的攻击力 \(\le 10^6\),所有 \(p_i\) 的最小公倍数 \(\le 10^{12}\)。
保证 $ T, n, m $ 均为正整数。
solution:
我们不难发现其实砍每条龙的剑是唯一确定的,根据题意,我们恰好砍死一条龙时的伤害方程为:
\[x \times atk = a_i+p_i*K \]
其中 \(atk\) 表示砍的次数,\(K\) 表示回了多少次血。
转化一下:
\[atk\times x \equiv a_i \ (mod \ p_i) \]
我们假设用来砍这条龙的剑伤为 \(b_i\) (即上述式子中的 \(x\) ),那么我们就要求一个 最小攻击次数 \(x\) 满足:
\[b_{i}x \equiv a_i \ (mod \ p_i) \]
我们先思考一下在 excrt 中我们是这么处理的:
假设之前 \(i-1\) 个方程合并出了一个解 \(ans\) 和一个所有 \(p\) 的 最小公倍数 \(lcm\)。那么前 \(i-1\) 个方程的通解可表示为 :\(ans+x\times lcm\)
我们要让这个通解满足现在的方程:
\[b_{i}(ans+x\times lcm) \equiv a_i \ (mod \ p_i) \]
然后我们将同余方程转成等式:
\[b_{i}(ans+x\times lcm) = a_i +p_i\times y \]
移项:
\[(b_i\times lcm)x+(-p_i)y = a_i -b_i\times ans \]
看到这个式子就说明这题写完了,直接 exgcd 求解就完了。
但是还要注意一些细节:首先是选剑,我们可以用平衡树或者 multiset 实现。还有就是我们求出来的答案要把龙砍死,所以要注意一下最难砍的那条龙最少要砍几刀,如果答案不到那个数,记得加回去。
都是做 crt 的人了,__int128这种常识就不需要多说了吧~~
Code:
#include<bits/stdc++.h>
#define ll __int128
const int N=1e5+5;
using namespace std;
ll read()
{
ll res=0;char c=getchar();
while(c<48||57<c)c=getchar();
while(48<=c&&c<=57)res=(res<<3)+(res<<1)+c-'0',c=getchar();
return res;
}
short out[1005];
void write(ll x)
{
while(x){out[++out[0]]=x%10;x/=10;}
while(out[0])putchar(48+out[out[0]--]);
putchar('\n');
}
void exgcd(ll a,ll b,ll &x,ll &y)
{
if(!b)x=1,y=0;
else exgcd(b,a%b,y,x),y-=a/b*x;
}
ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll a[N],b[N],p[N],t[N];
ll LCM(ll a,ll b){return a/gcd(a,b)*b;}
ll A,B,C,m=1,ans=0,x,y,mx;
bool merge(ll a,ll b,ll p)
{
A=b*m%p;
B=p;
C=(a-b*ans%p+p)%p;
exgcd(A,B,x,y);
ll d=gcd(A,B),q=C/d,qa=B/d,qb=A/d;
if(C%d){cout<<"-1\n";return 0;}
x=(x%B+B)%B;
ans+=(q*x%qa*m%(m*=qa));
ans%=m;
return 1;
}
int n,q;
multiset<ll> s;
void init()
{
s.clear();m=1,ans=0;mx=0;
}
void work()
{
init();
cin>>n>>q;
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++)t[i]=read();
for(int i=1;i<=q;i++){ll x=read();s.insert(x);}
for(int i=1;i<=n;i++)
{
auto u=s.upper_bound(a[i]);
if(u!=s.begin())u--;
b[i]=*u;s.erase(u),s.insert(t[i]);
mx=max(mx,(a[i]-1)/b[i]+1);
}
int i=1;
while(i<=n&&merge(a[i],b[i],p[i]))i++;
if(i==n+1)
{
if(ans<mx)ans+=((mx-ans-1)/m+1)*m;
write(ans);
}
}
int main()
{
//freopen("P4774_1.in","r",stdin);
//freopen("P4774.out","w",stdout);
int T;
cin>>T;
while(T--)work();
return 0;
}
来源链接:https://www.cnblogs.com/LG017/p/18703091
如有侵犯您的版权,请及时联系3500663466#qq.com(#换@),我们将第一时间删除本站数据。
暂无评论内容