题目链接

题目大意

有n条龙,分别具有$a_i,p_i,atk'_i$三个属性

代表生命力,恢复能力,奖励的剑的攻击力。初始有m把剑,攻击力分别为$atk_i​$其中每杀死第$i​$条龙可以获得攻击力为$atk'_i​$的剑。攻击后龙会恢复生命力直至生命力不小于0,只有在龙的生命力恢复后为0时算作击杀。

询问最少多少次攻击可以保证任意的龙都被杀死。

每条龙对应使用的剑的攻击力$ATK_i$满足条件:

$$ATK_i=\begin{equation}\left\{ \begin{array}{lr}atk_j~~(\exists atk_j\le=a_i ~\&\&~atk_{j+1}\ge a_i) \\atk_1 \end{array}\right.\end{equation}$$

即要求一个同余方程组$$x \cdot ATK_i \equiv a_i\pmod{p_i}$$此处$atk_j$指第$i$条龙对应的剑的攻击力。

解题步骤

概述

题目可以分为两个子问题来进行处理。

  1. 我们首先处理出每条龙对应使用的剑的攻击力。很好处理,不用手写平衡树,直接multiset维护即可。需要注意的细节是使用迭代器记得判断iter != t.begin(),不大于生命力故使用upper_bound,可能有多把相同攻击力的剑故使用multiset
  2. 处理了$ATK_i$后就需要求解同余方程组了。我们先使用扩展欧几里得将方程变形为扩展中国剩余定理的基本形式(形如$x \equiv a_i \pmod{p_i}$的方程组),然后使用扩展中国剩余定理求解即可得到答案。细节部分需要注意的是,求出的$x$ 为方程组的最小可行解,但不是此题答案。此题的答案还需要满足$x\cdot ATK_i\ge a_i$,对答案与$\max{\lceil {\frac{a_i}{ATK_i}}\rceil}$取较大值即可。

数学变形

对于$$x \cdot ATK_i \equiv a_i\pmod{p_i}^{[1]}$$我们如何将其化作ExCRT的一般形式?

  1. 显然上式$^{[1]}$可变形为$x\cdot ATK_i+k\cdot p_i=a_i$,我们可以对其使用扩展欧几里得求解出一组特解$x',y'$使得$x'\cdot ATK_i\frac{a_i}{(ATK_i,p_i)}+y'\cdot P_i\frac{a_i}{(ATK_i,p_i)}=(ATK_i,p_i)$。随后我们可以由此得到原方程的特解$sx=x'\times(ATK_i,p_i),sy=y'\times(ATK_i,p_i)$。然后由此可以构造通解$x=sx+k\cdot\frac{a_i}{(ATK_i,p_i)}$。这里注意了,此时得到的式子变形直接可以得到$x\equiv sx\pmod{\frac{a_i}{(ATK_i,p_i)}}^{[2]}$。
  2. 得到的式$^{[2]}$即为ExCRT的基本形式,接下来就是基本的解ExCRT套路了,套用版子即可,但注意long long*long longlong long的问题。ExCRT模板在此处

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N=100020;
long long exgcd(long long a,long long b,long long &x,long long &y)
{
    if(!b){x=1,y=0;return a;}
    long long d=exgcd(b,a%b,y,x);
    y-=a/b*x;return d;
}
long long mul(long long x,long long y,long long mod){ return (x*y-(long long)(x/(long double)mod*y+1e-3)*mod+mod)%mod; }
long long ExCRT(long long *a,long long *m,long long n)
{
    long long A=a[1],M=m[1],x,y;
    for(int i=2;i<=n;i++)
    {
        long long d=exgcd(M,m[i],x,y);
        if((a[i]-A)%d!=0)
            return -1;
        long long t=m[i]/d;
        x=mul(x,(a[i]-A)/d,t);
        A+=x*M,M*=t;
        A=(A%M+M)%M;
    }
    return A;
}
long long lcm(long long x,long long y)
{
    return x/__gcd(x,y)*y;
}
int attack[N],g[N];
long long life[N],recovery[N],aa[N],bb[N];
int main()
{
    //freopen("dragon.in","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;bool NoSolution=false;
        long long mi=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%lld",&life[i]);
        for(int i=1;i<=n;i++)
            scanf("%lld",&recovery[i]);
        for(int i=1;i<=n;i++)
            scanf("%d",&g[i]);
        multiset<long long>t;
        for(int i=1;i<=m;i++)
            scanf("%d",&attack[i]),t.insert(attack[i]);
        for(int i=1,now;i<=n;i++)
        {
            multiset<long long>::iterator iter=t.upper_bound(life[i]);
            if(iter!=t.begin()&&*(--iter)<=life[i])now=*iter,t.erase(iter);
            else now=*t.begin(),t.erase(t.begin());
            mi=max(mi,life[i]/now+(life[i]%now!=0));
            //cerr<<i<<':'<<now<<endl;
            long long xnow,ynow,d=exgcd(now,recovery[i],xnow,ynow);
            if(life[i]%d!=0)NoSolution=true;
            aa[i]=mul(xnow,life[i]/d,recovery[i]/d),bb[i]=recovery[i]/d;
            t.insert(g[i]);
        }
        printf("%lld\n",NoSolution?-1:(max(ExCRT(aa,bb,n),mi)));
    }
}

 

其他

膜一波教会我的ViXbob Orz

keyboard_arrow_up