题解 P4774 【[NOI2018]屠龙勇士】

· · 题解

\mathsf{Solution\text{ }For\text{ }P4774}

\large\mathcal{By\text{ }ShadderLeave} \tiny\texttt{与博客日报内容配套的同步题解}

\mathsf{Description}

为了读懂这题到底想让你干什么，先从简单的看起

先不管机器人对屠龙宝刀的选择以及杀死一条恶龙之后点击就送的屠龙宝刀，现在假设面对每一条龙时你手里的刀的属性已知，这个问题似乎变得简单了一些。

因为每一条恶龙的初始血量知道，但是恶龙可以无限制的回血，必须刚好把血量砍成 0 才能算杀死了恶龙，我们不妨想，假设这条龙每个时刻都在回血，而我们的攻速是无限快，那么就只要满足

\texttt{攻击的刀数}\times\texttt{攻击力}=n\times\texttt{回血量}+\texttt{初始血量}

那么实际上就是一个同余方程

\texttt{攻击刀数}\times\texttt{攻击力}\equiv\texttt{初始血量}\pmod{\texttt{回血量}}

我们设面对第 i 条恶龙时我们手上的剑的攻击力为 a_i，第 i 条恶龙的初始血量为 r_i，恢复能力为 m_i，我们最小的攻击次数为 x。那么题目实际上就是在求线性同余方程组

\begin{cases}a_1x\equiv r_1\pmod{m_1}\\a_2x\equiv r_2\pmod{m_2}\\.....\\a_ix\equiv r_i\pmod{m_i}\\.....\\a_nx\equiv r_n\pmod{m_n}\end{cases}

的解

首先肯定是利用扩展中国剩余定理求解

但是这题有变化的是这些方程的 x 是带系数的，我们需要对传统的方法加上一点点的变通

首先对于原版的扩展中国剩余定理我们的解法是：
设前 i-1 个方程的一个解为 ans，lcm 是前 i-1 个方程模数的最小公倍数，那么不难发现 ans+k\times lcm(k\in \mathbb{Z}) 是前 i-1 个方程的通解。
将通解代入第 i 个方程 a_ix\equiv r_i\pmod{m_i} 中得到

a_i\times(ans+k\times lcm)\equiv r_i\pmod{m_i}

其中已知的量有：a_i,ans,lcm,r_i,m_i 要求的是 k

移项得： a_i\times k\times lcm\equiv r_i-a_i\times ans\pmod{m_i}

化为不定方程形式为 a_i\times lcm\times \boxed{k}+m_i\times \boxed{p}=r_i-a_i\times ans,p\in \mathbb{Z}
(框起来的是未知数部分)

使用 \mathsf{Exgcd} 求解得到 k 的一个可行解（如果 \mathsf{Exgcd} 无解那么整个方程组无解）
这时候前 i 个方程的一个解 ans^\prime =ans+k\times lcm（这里的 k 是指 \mathsf{Exgcd} 解出来的一个值）
前 i 个方程的模数的最小公倍数 lcm^\prime=lcm\times (m_i/g) (这里的 g 是指在 \mathsf{Exgcd} 时求出来的 \gcd(lcm,m_i))

这时候便有了前 i 个方程的一个解以及模数的最小公倍数，直接重复以上步骤求解第 i+1 的方程即可

本题 \mathsf{ExCRT} 部分注意事项：

那么现在问题回归了，按照题目的描述我们怎么把给出的剑按照机器人的选择配对以及杀死恶龙爆出的剑怎么处理？

可以借助 \mathcal{STL} 的 \mathcal{multi\_set}(划重点)来预处理出面对每条恶龙我们会使用的剑。

对于初始的剑，直接按照攻击力插入 multi\_set 中，为什么不用 set 是因为可能出现攻击力相同的剑，这样在从集合中去掉一把剑的时候会把攻击力相同的剑全部去掉，不合题意。

然后枚举每一条龙的生命值，按照题目描述，使用 \mathcal{multi\_set} 自带的二分查找函数找出对应的剑然后把这把剑从集合中删去，同时添加杀死该条恶龙可获得的剑。

这里要注意 \mathcal{multi\_set} 的使用，详见代码。

\mathsf{Code:}

#include<bits/stdc++.h>
#include<set>
#include<algorithm>
using namespace std;
const int maxn=100007;
typedef long long LL;
LL m[maxn],r[maxn];
LL rew[maxn],a[maxn];
inline LL R()
{
    LL re;
    char c;
    while((c=getchar())>'9'||c<'0');
    re=c-48;
    while((c=getchar())>='0'&&c<='9')
    re=re*10+c-48;
    return re;
}
LL N,M,T;
LL g,ATK;
inline void Exgcd(LL a,LL b,LL &x,LL &y)
{
    if(!b)
    {
        g=a;
        x=1;y=0;
        return ;
    }
    Exgcd(b,a%b,y,x);
    y-=(a/b)*x;
    return ;
}
inline LL X(LL ai,LL b,LL m)//龟速乘
{
    LL s=0;
    while(b)
    {
        if(b&1) s=(s+ai)%m;
        ai=(ai<<1)%m;
        b>>=1;
    }
    return s;
}
inline LL ExCRT()
{
    LL ans=0,lcm=1,A,B,C,x,y;
    for(int i=1;i<=N;i++)
    {
        A=X(lcm,a[i],m[i]);B=m[i];
        C=((r[i]-X(a[i],ans,m[i]))%m[i]+m[i])%m[i];//等式右边调整为正值
        Exgcd(A,B,x,y);
        x=(x%m[i]+m[i])%m[i];
        if(C%g) return -1;//无解
        ans+=X(C/g,x,m[i]/g)*lcm;
        lcm=lcm*(m[i]/g);
    }
    if(ans<ATK)//不是合法解
    {
        x=(ATK-ans)%lcm==0?(ATK-ans)/lcm:(ATK-ans)/lcm+1;//至少要多砍多少刀才是合法的
        ans=ans+x*lcm;//通解形式
    }
    return ans;
}
int main()
{
    T=R();
    while(T--)
    {
        multiset<LL>sword;
        ATK=0;//记得置0
        N=R();M=R();
        for(register int i=1;i<=N;i++)
            r[i]=R();//初始生命值
        for(register int i=1;i<=N;i++)
            m[i]=R();//恢复能力
        for(register int i=1;i<=N;i++)
            rew[i]=R();//杀死恶龙后屠龙宝刀点击送
        for(register int i=1;i<=M;i++)
            sword.insert(R());//初始的剑
        multiset<LL>::iterator it;
        for(register int i=1;i<=N;i++)
        {
            it=sword.upper_bound(r[i]);//使用upperbound（想想为什么）
            if(it!=sword.begin()) it--;
            a[i]=(*it);

            sword.erase(it);//这句表示删除迭代器it所指向的位置，如果写 sword.erase(*it);则表示删除所有值等于it指向的元素键值的元素  

            sword.insert(rew[i]);//屠龙宝刀点击送
            ATK=max(ATK,r[i]%a[i]==0?r[i]/a[i]:r[i]/a[i]+1);//处理出至少要砍多少刀
        }
        printf("%lld\n",ExCRT());       
    }
    return 0;
}

这道题目是非常值得一做的题目，对于理解 \mathsf{ExCRT} 有很大的帮助。
如果有不懂的地方或者发现这篇蒟蒻题解哪里有问题欢迎私信D我。（大雾
谢谢管理大大审核^_^

\huge\mathcal{The\text{ }End}