洛谷 P4774 / loj 2721 [NOI2018] 屠龙勇士题解【同余】【exgcd】【CRT】

推导过程存在漏洞+exCRT板子没打熟于是期望得分÷实际得分=∞？

题目描述

小 D 最近在网上发现了一款小游戏。游戏的规则如下：

游戏的目标是按照编号 $1\sim n$ 顺序杀掉 $n$ 条巨龙，每条巨龙拥有一个初始的生命值 $a_i$。同时每条巨龙拥有恢复能力，当其使用恢复能力时，它的生命值就会每次增加 $p_i$，直至生命值非负。只有在攻击结束后且当生命值恰好为 $0$ 时它才会死去。

游戏开始时玩家拥有 $m$ 把攻击力已知的剑，每次面对巨龙时，玩家只能选择一把剑，当杀死巨龙后这把剑就会消失，但作为奖励，玩家会获得全新的一把剑。

小 D 觉得这款游戏十分无聊，但最快通关的玩家可以获得 ION2018 的参赛资格，于是小 D 决定写一个笨笨的机器人帮她通关这款游戏，她写的机器人遵循以下规则：

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

机器人面对每条巨龙，它都会使用上一步中选择的剑攻击巨龙固定的 $x$ 次，使巨龙的生命值减少 $x\times ATK$。

之后，巨龙会不断使用恢复能力，每次恢复 $p_i$ 生命值。若在使用恢复能力前或某一次恢复后其生命值为 $0$，则巨龙死亡，玩家通过本关。

那么显然机器人的攻击次数是决定能否最快通关这款游戏的关键。小 D 现在得知了每条巨龙的所有属性，她想考考你，你知道应该将机器人的攻击次数 $x$ 设置为多少，才能用最少的攻击次数通关游戏吗？

当然如果无论设置成多少都无法通关游戏，输出 -1 即可。

输入格式

从文件 dragon.in 中读入数据。

第一行一个整数 $T$，代表数据组数。

接下来 $T$ 组数据，每组数据包含 $5$ 行。

每组数据的第一行包含两个整数，$n$ 和 $m$，代表巨龙的数量和初始剑的数量；

接下来一行包含 $n$ 个正整数，第 $i$ 个数表示第 $i$ 条巨龙的初始生命值 $a_i$；

接下来一行包含 $n$ 个正整数，第 $i$ 个数表示第 $i$ 条巨龙的恢复能力 $p_i$；

接下来一行包含 $n$ 个正整数，第 $i$ 个数表示杀死第 $i$ 条巨龙后奖励的剑的攻击力；

接下来一行包含 $m$ 个正整数，表示初始拥有的 $m$ 把剑的攻击力。

输出格式

输出到文件 dragon.out 中。

一共 $T$ 行。

第 $i$ 行一个整数，表示对于第 $i$ 组数据，能够使得机器人通关游戏的最小攻击次数 $x$，如果答案不存在，输出 -1。

样例输入
2

3 3

3 5 7

4 6 10

7 3 9

1 9 1000

3 2

3 5 6

4 8 7

1 1 1

1 1
样例输出
59

-1
样例解释

第一组数据：

开始时拥有的剑的攻击力为 $\{1,9,10\}$，第 $1$ 条龙生命值为 $3$，故选择攻击力为 $1$的剑，攻击 $59$ 次，造成 $59$ 点伤害，此时龙的生命值为 $-56$，恢复 $14$ 次后生命值恰好为 $0$，死亡。

攻击力为 $1$ 的剑消失，拾取一把攻击力为 $7$ 的剑，此时拥有的剑的攻击力为 $\{7,9,10\}$，第 $2$ 条龙生命值为 $5$，故选择攻击力为 $7$ 的剑，攻击 $59$ 次，造成 $413$ 点伤害，此时龙的生命值为 $-408$，恢复 $68$ 次后生命值恰好为 $0$，死亡。

此时拥有的剑的攻击力为 $\{3,9,10\}$，第 $3$ 条龙生命值为 $7$，故选择攻击力为 $3$ 的剑，攻击 $59$ 次，造成 $177$ 点伤害，此时龙的生命值为 $-170$，恢复 $17$ 次后生命值恰好为 $0$，死亡。

没有比 $59$ 次更少的通关方法，故答案为 $59$。

第二组数据：

不存在既能杀死第一条龙又能杀死第二条龙的方法，故无法通关，输出-1。

子任务

测试点编号 $n$ $m$ $p_i$ $a_i$ 攻击力其他限制

$1$ $\le 10^5$ $=1$ $=1$ $\le 10^5$ $=1$ 无

$2$

$3$ $\le 10^5$

$4$

$5$ $\le 10^3$ $\le 10^3$ $\le 10^5$
特性 $1$、

特性 $2$

$6$

$7$

$8$ $=1$ $=1$ $\le 10^8$ $\le 10^8$ $\le 10^6$ 特性 $1$

$9$

$10$

$11$

$12$

$13$

$14$ $=10^5$ $=10^5$ $=1$ 无特殊限制

$15$

$16$ $\le 10^5$ $\le 10^5$
所有 $p_i$ 是质数
$\le 10^{12}$ 特性 $1$

$17$

$18$ 无特殊限制

$19$

$20$

特性 $1$ 是指：对于任意的 $i$，$a_i\le p_i$。

特性 $2$ 是指：$LCM(p_i)\le 10^6$ 即所有 $p_i$ 的最小公倍数不大于 $10^6$。

对于所有的测试点，$T\le 5$，所有武器的攻击力 $\le 10^6$，所有 $p_i$ 的最小公倍数$\le 10^{12}$。

提示

你所用到的中间结果可能很大，注意保存中间结果的变量类型。

题解：

整道题使用 exCRT 就能弄过去。

首先我们考虑每一轮用哪把剑砍龙。由于龙的顺序是固定的，所以每次剩下的剑的集合是固定的。但是每一轮都有剑在动态变化，因此我们用一棵平衡树来维护每次需要用的剑。

此时我们可以预处理砍每条龙用的是哪把剑，令砍第 $i$ 条龙用的剑攻击力为 $c_i$。

那么对于每把剑和相应的龙都应该存在一个 $t\in\mathbb N$ ，使得

\[a_i-c_ix+tp_i=0
\]

把它转化为同余方程的形式即为

\[c_ix\equiv a_i\pmod{p_i}
\]

同时，我们要保证 $x$ 取最小非负整数解时有意义，因此我们先用上面算出来的 $c_i$ 分别求出每头龙至少需要砍多少下才会死，然后我们“提前”砍掉那么多。

即设变量 $xmn$ 表示最少要砍的刀数

\[xmn=\max_{1\le i\le n}\left\{\left\lceil\frac{a_i}{c_i}\right\rceil\right\}
\]

那么对于所有的 $a_i$ 都要减去一个 $xmn\times c_i$。

减过之后，对于所有的龙，我们把方程组列出来，有

\[\left\{
\begin{aligned}
&c_1x\equiv a_1\pmod{p_1}\\\
&c_2x\equiv a_2\pmod{p_2}\\\
&\cdots\\\
&c_nx\equiv a_n\pmod{p_n}
\end{aligned}
\right.
\]

变成了一个 CRT 的形式，由于 $p_i$ 没有保证互质，所以我们使用 exCRT。

但是还有一点，我们用 CRT 解决问题时，左侧的 $x$ 是没有系数的，我们要考虑怎么样把这边的系数化掉。

如果用逆元，两边同除 $c_i$，那么只在 $p_i$ 保证为质数的意义下才能成立，否则逆元无解导致题目答案错误。

我们可以用不定方程来推不定方程，因为 $c_ix\equiv a_i$ 有一系列解，而且和 $x$ 成线性关系，我们直接从这边转化过来就可以了。

\[c_ix\equiv a_i\pmod{p_i}\\\
c_ix+p_it=a_i,\ t\in \mathbb Z
\]

这里只有 $x$ 和 $t$ 是变量，因此只需要把 $x$ 的特解和通解求出来，再构造一个形如 $x\equiv b_i\pmod{d_i}$ 的方程就可以了。

对不定方程 $c_ix+p_it=\gcd(c_i,p_i)$ 求解，得到 $x=x_0$。等式两边同乘 $\frac{a_i}{\gcd(c_i,p_i)}$，$x=\frac{x_0a_i}{\gcd(c_i,p_i)}$。那么 $\Delta x=\frac {p_i}{\gcd(c_i,p_i)}$。

由此构造出了新方程

\[x\equiv \frac{x_0a_i}{\gcd(c_i,p_i)}\left(\bmod \frac{p_i}{\gcd(c_i,p_i)}\right)
\]

原方程组就变成了

\[\left\{
\begin{aligned}
&x\equiv b_1\pmod{d_1}\\\
&x\equiv b_2\pmod{d_2}\\\
&\cdots\\\
&x\equiv b_n\pmod{d_n}
\end{aligned}
\right.
\]

$b_i,d_i$ 由上式计算。

然后套上 exCRT ，最后加上一开始算的 $latex xmn$ 即可。

本来多简单一个题被我公式来公式去整这么复杂。

Code：

(平衡树(BST:: 部分)版面较大，multimap 可过)

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#define ll long long

namespace BST

{

int ls[200100],rs[200100],key[200100],rdm[200100],sz[200100],pcnt=0,root=0;

int Newnode(int x)

{

    ++pcnt;

    key[pcnt]=x;

    rdm[pcnt]=rand();

    ls[pcnt]=rs[pcnt]=0;

    sz[pcnt]=1;

    return pcnt;

}

void maintain(int rt)

{

    sz[rt]=sz[ls[rt]]+sz[rs[rt]]+1;

}

int Merge(int a,int b)

{

    if(!a||!b)

        return a|b;

    if(rdm[a]<rdm[b])

    {

        rs[a]=Merge(rs[a],b);

        maintain(a);

        return a;

    }

    ls[b]=Merge(a,ls[b]);

    maintain(b);

    return b;

}

void split(int rt,ll x,int &a,int &b)

{

    if(!rt)

    {

        a=b=0;

        return;

    }

    if(key[rt]<=x)//不高于

    {

        a=rt;

        split(rs[a],x,rs[a],b);

    }

    else

    {

        b=rt;

        split(ls[b],x,a,ls[b]);

    }

    maintain(rt);

}

void Insert(int x)

{

    int a,b;

    split(root,x,a,b);

    root=Merge(Merge(a,Newnode(x)),b);

}

void Delete(int x)

{

    int a,b,c;

    split(root,x-1,a,b);

    split(b,x,b,c);

    b=Merge(ls[b],rs[b]);

    root=Merge(Merge(a,b),c);

}

int getMin(int rt)

{

    if(ls[rt])

        return getMin(ls[rt]);

    return key[rt];

}

int getMax(int rt)

{

    if(rs[rt])

        return getMax(rs[rt]);

    return key[rt];

}

int getsword(ll x)

{

    int a,b,ans;

    split(root,x,a,b);

    if(!sz[a])

        ans=getMin(b);

    else

        ans=getMax(a);

    root=Merge(a,b);

    return ans;

}

}

ll exgcd(ll a,ll b,ll &x,ll &y)

{

    if(!b)

    {

        x=1,y=0;

        return a;

    }

    ll g=exgcd(b,a%b,y,x);

    y-=a/b*x;

    return g;

}

ll qmul(ll x,ll y,ll p)

{

    ll ans=0,f=1;

    if(x<0)

    {

        x=-x;

        f=-f;

    }

    if(y<0)

    {

        y=-y;

        f=-f;

    }

    while(y)

    {

        if(y&1)

            ans=(ans+x)%p;

        x=(x+x)%p;

        y>>=1;

    }

    return ans*f;

}

ll k[100100],a[100100],b[100100],c[100100];//k 指系数

//c 是奖励的

int main()

{

    freopen("dragon.in","r",stdin);

    freopen("dragon.out","w",stdout);

    int T,n,m;

    ll x,y;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&m);

        BST::pcnt=BST::root=0;

        for(int i=1;i<=n;++i)

            scanf("%lld",&a[i]);

        for(int i=1;i<=n;++i)

            scanf("%lld",&b[i]);

        for(int i=1;i<=n;++i)

            scanf("%lld",&c[i]);

        for(int i=1;i<=m;++i)

        {

            scanf("%lld",&x);

            BST::Insert(x);

        }

        ll xmn=0;

        for(int i=1;i<=n;++i)

        {

            ll f=BST::getsword(a[i]);

            BST::Delete(f);

            BST::Insert(c[i]);

            c[i]=f;

            xmn=xmn>ceil((double)a[i]/f)?xmn:ceil((double)a[i]/f);

        }

        for(int i=1;i<=n;++i)

            a[i]-=c[i]*xmn;

        bool flag=0;

        for(int i=1;i<=n;++i)

        {

            //c[i]*x=a[i](mod b[i])

            ll g=exgcd(c[i],b[i],x,y);

            if(a[i]%g)

            {

                puts("-1");

                flag=1;

                break;

            }

            ll t=b[i]/g;

            //特解 x

            x=(x%t+t)%t;

            x=qmul(x,a[i]/g,t);

            a[i]=x;

            b[i]/=g;//公差

            if(i==1)

                continue;

            g=exgcd(b[i],b[i-1],x,y);

            if((a[i]-a[i-1])%g)

            {

                puts("-1");

                flag=1;

                break;

            }

            t=b[i-1]/g;

            x=(x%t+t)%t;

            x=qmul(x,(a[i]-a[i-1])/g,t);

            a[i]-=qmul(b[i],x,b[i]/g*b[i-1]);

            b[i]=b[i]/g*b[i-1];

            a[i]=(a[i]%b[i]+b[i])%b[i];

        }

        if(!flag)

            printf("%lld\n",xmn+((a[n]%b[n])+b[n])%b[n]);

    }

    return 0;

}

秒客网

洛谷 P4774 / loj 2721 [NOI2018] 屠龙勇士题解【同余】【exgcd】【CRT】

题目描述

输入格式

输出格式

样例输入

样例输出

样例解释

子任务

提示

题解：

Code：

相关文章

测试点编号	$n$	$m$	$p_i$	$a_i$	攻击力	其他限制
$1$	$\le 10^5$	$=1$	$=1$	$\le 10^5$	$=1$	无
$2$
$3$					$\le 10^5$
$4$
$5$	$\le 10^3$	$\le 10^3$	$\le 10^5$			特性 $1$、特性 $2$
$6$
$7$
$8$	$=1$	$=1$	$\le 10^8$	$\le 10^8$	$\le 10^6$	特性 $1$
$9$
$10$
$11$
$12$
$13$
$14$	$=10^5$	$=10^5$	$=1$			无特殊限制
$15$
$16$	$\le 10^5$	$\le 10^5$	所有 $p_i$ 是质数	$\le 10^{12}$		特性 $1$
$17$
$18$			无特殊限制
$19$
$20$

洛谷 P4774 / loj 2721 [NOI2018] 屠龙勇士 题解【同余】【exgcd】【CRT】

题目描述

输入格式

输出格式

样例输入

样例输出

样例解释

子任务

提示

题解：

Code：

相关文章

洛谷 P4774 / loj 2721 [NOI2018] 屠龙勇士题解【同余】【exgcd】【CRT】