bzoj1407[Noi2002] Savage

本文主要是介绍bzoj1407[Noi2002] Savage，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：bzoj1407

题目大意：

有n个野人，野人各自住在第c[i]个山洞中（山洞成环状），每年向前走p[i]个山洞，到这个山洞住下来。
每个野人的寿命为l[i]，问至少需要多少个山洞，才能让野人在有生之年永远不住在同一个山洞。

题解：
拓展欧几里德
n≤15，所以直接从小到大枚举答案。
然后再枚举每对野人看看是否合法。

设野人$i$、$j$相遇的时间为第k年
据题意可得：

$$c[i]+p[i]\times k=c[j]+p[j]\times k \mod ans$$
求解 $k$即求解该不定方程：
$$(p[i]-p[j])\times x+ans\times y = c[j]-c[i]$$
若该方程无解或 $k>min(l[i],l[j])$，则该对野人是合法的。

如此的一道题，我WA完TLE，TLE完WA如此来去两三遍才AC。How much I can say【摊手

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 20int n,l[maxn],c[maxn],p[maxn];
int mymin(int x,int y){return (x<y)?x:y;}
int mymax(int x,int y){return (x>y)?x:y;}
int myabs(int x){return (x<0)?-x:x;}
void exgcd(int a,int b,int &d,int &x,int &y)
{if (b==0){x=1,y=0;d=a;return;}exgcd(b,a%b,d,x,y);int t=x;x=y,y=t-a/b*y;
}
bool check(int B)
{for (int i=1;i<n;i++)for (int j=i+1;j<=n;j++){int lim=mymin(l[i],l[j]);int A=p[i]-p[j],C=c[j]-c[i],d,x,y;exgcd(A,B,d,x,y);if (C%d) continue;x=x*C/d;x=x%(B/d);if (x<0) x+=myabs(B/d);// x=(x%(B/d)+(B/d))%(B/d);if (x<=lim) return 0;}return 1;
}
int main()
{//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);scanf("%d",&n);int ans=n;for (int i=1;i<=n;i++){scanf("%d%d%d",&c[i],&p[i],&l[i]);ans=mymax(ans,c[i]);}for (ans;ans<=1000000;ans++)if (check(ans)) {printf("%d\n",ans);break;}return 0;
}

这篇关于bzoj1407[Noi2002] Savage的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---