Luogu P2421 [NOI2002]荒岛野人

最近上课时提到的一道扩欧水题。还是很可做的。

我们首先注意到,如果一个数\(s\)是符合要求的,那么那些比它大(or 小)的数不一定符合要求。

因此说,答案没有单调性,因此不能二分。

然后题目中也提到\(s\le 10^6\),因此我们直接从小到大枚举\(s\),然后考虑如何判断。

由于两个野人在有生之年不会相遇,因此只有两种情况:

  1. 这两个野人永远不会相遇。
  2. 这两个野人相遇的时候他们其中的一个(或两个)已经死了。

在处理的时候我们把\(c_i\)都减\(1\)方便处理。

我们接着枚举两个人\(i,j\)设它们\(x\)年后相遇,然后我们可以列出式子:

\(c_i+p_ix\equiv c_j+p_jx\ (mod\ s)\)

移项得

\((p_i-p_j)x-sy=c_j-c_i\)

然后就很明显了,我们扩欧解这个同余方程即可,再判断一下与\(min(l_i,l_j)\)的关系

但是注意一下枚举的下界,从\(min(c_i)\)(注意在减\(1\)之前计算)开始

CODE

#include<cstdio>
#include<cctype>
using namespace std;
const int N=20;
int n,c[N],p[N],l[N],mx;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(int &x)
{
x=0; char ch; while (!isdigit(ch=tc()));
while (x=(x<<3)+(x<<1)+ch-'0',isdigit(ch=tc()));
}
inline int min(int a,int b)
{
return a<b?a:b;
}
inline int exgcd(int a,int b,int &x,int &y)
{
if (!b) { x=1; y=0; return a; }
int d=exgcd(b,a%b,y,x); y-=a/b*x; return d;
}
inline bool check(int s)
{
register int i,j;
for (i=1;i<n;++i)
for (j=i+1;j<=n;++j)
{
int a=p[i]-p[j],b=s,k=c[j]-c[i],x,y;
if (a<0) a=-a,k=-k; int d=exgcd(a,b,x,y);
if (k%d) continue; x*=k/d; int r=b/d;
if ((x%r+r)%r<=min(l[i],l[j])) return 0;
}
return 1;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
register int i; read(n);
for (i=1;i<=n;++i)
read(c[i]),mx=c[i]>mx?c[i]:mx,--c[i],read(p[i]),read(l[i]);
for (i=mx;;++i)
if (check(i)) return printf("%d",i),0;
}
上一篇:数字盒子


下一篇:第一章 spring核心概念