「NOI2018」屠龙勇士解题报告

「NOI2018」屠龙勇士

首先对于每个龙用哪个剑砍，我们可以用set随便模拟一下得到。

然后求出拿这个剑砍这条龙的答案

\[atk_ix-p_iy=a_i
\]

其中\(atk_i\)是砍第\(i\)条龙的剑的攻击力，\(p_i\)是龙的回复系数，\(a_i\)是初始生命值，然后\(x\)就是单独考虑这个剑砍这个龙的答案。

我们可以拿exgcd去解这个方程，但是冷静分析一波，我们发现回复次数\(y\)需要非负。

然后我们再冷静一波，发现\(p_i\not=1\)的数据都有一个叫性质\(1\)的东西是\(a_i\le p_i\)

在性质\(1\)的情况下，因为\(atk_i\)和\(x\)都是非负的，所以\(y<0\)的时候显然是无解的

然后发现\(p_i\)都等于\(1\)的时候，我们只需要取最大的生命值就可以了

然后快乐的解一下这个方程

注意一件事，可以得到通解\(x\)是在\(\pmod {\frac{p_i}{\gcd(p_i,atk_i)}}\)下的

这样我们就得到了很多个同余方程，然后excrt合并就可以了

Code:

#include <cstdio>

#include <cctype>

#include <algorithm>

#include <set>

#define ll long long

using std::max;

const int SIZE=1<<21;

char ibuf[SIZE],*iS,*iT;

#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),iS==iT?EOF:*iS++):*iS++)

//#define gc() getchar()

template <class T>

void read(T &x)

{

	x=0;char c=gc();

	while(!isdigit(c)) c=gc();

	while(isdigit(c)) x=x*10+c-'0',c=gc();

}

std::multiset <ll> s;

std::multiset <ll>::iterator it;

const int N=1e5+10;

int n,m;

ll hp[N],p[N],atk[N],A[N],B[N];

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,x,y);

	ll tmp=x;

	x=y;

	y=tmp-a/b*y;

}

ll mul(ll d,ll k,ll p)

{

    ll f=0;

    while(k)

    {

        if(k&1) (f+=d)%=p;

        (d+=d)%=p;

        k>>=1;

    }

    return f;

}

void work()

{

    ll mx=0;

	s.clear();

	read(n),read(m);

	for(int i=1;i<=n;i++) read(hp[i]);

	for(int i=1;i<=n;i++) read(p[i]);

	for(int i=1;i<=n;i++) read(atk[i]);

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

	{

		ll x;

		read(x);

		s.insert(x);

	}

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

	{

		ll a,b,c,x,y;

		it=s.upper_bound(hp[i]);

		if(it==s.begin())

		{

			b=*it;

			s.erase(it);

		}

		else

		{

			it--;

			b=*it;

			s.erase(it);

		}

		a=b,b=p[i],c=hp[i];

		ll d=gcd(a,b);

		if(c%d!=0)

		{

			puts("-1");

			return;

		}

        mx=max(mx,(c-1)/a+1);

		exgcd(a,b,x,y);

		x=mul(x,c/d,b/d);

		x=(x%(b/d)+b/d)%(b/d);

		A[i]=x,B[i]=b/d;

		s.insert(atk[i]);

	}

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

	{

		if(A[i]==A[i-1])

		{

			B[i]=B[i]/gcd(B[i],B[i-1])*B[i-1];

			continue;

		}

		if(A[i]<A[i-1]) std::swap(A[i],A[i-1]),std::swap(B[i],B[i-1]);

		ll a=B[i-1],b=B[i],c=A[i]-A[i-1],d=gcd(a,b),x,y;

		if(c%d!=0)

		{

			puts("-1");

			return;

		}

		exgcd(a,b,x,y);

		x=mul(x,c/d,b/d);

		B[i]=a/d*b;

		A[i]=((A[i-1]+mul(x,B[i-1],B[i]))%B[i]+B[i])%B[i];

	}

	printf("%lld\n",max(A[n],mx));

}

int main()

{

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

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

	int T;read(T);

	while(T--) work();

	return 0;

}

2019.4.30

巴特西

「NOI2018」屠龙勇士解题报告

「NOI2018」屠龙勇士

最新文章

热门文章

巴特西

「NOI2018」屠龙勇士 解题报告

「NOI2018」屠龙勇士

最新文章

热门文章

「NOI2018」屠龙勇士解题报告