BZOJ1407 [Noi2002]Savage

Description

Input

第1行为一个整数N(1<=N<=15)，即野人的数目。

第2行到第N+1每行为三个整数Ci, Pi, Li表示每个野人所住的初始洞穴编号，每年走过的洞穴数及寿命值。

(1<=Ci,Pi<=100, 0<=Li<=10^6 )

Output

仅包含一个数M，即最少可能的山洞数。输入数据保证有解，且M不大于10^6。

Sample Input

3
1 3 4
2 7 3
3 2 1

Sample Output

6
//该样例对应于题目描述中的例子。

HINT

Source

鸣谢刘汝佳先生授权使用

正解：搜索+扩展欧几里得

解题报告：

　　今天上午考试的T2，一上来一看，这不是板子题吗？然后就没有然后了...

　　考虑枚举一共有多少个山洞，每次对于当前的山洞个数，两两check一下，看一下是否会冲突。check的方式很简单，就是直接解他们相遇的不定方程，很容易根据他们的信息得到一个方程，看一下最小正整数解是否在他们的寿命范围内。可以发现这样做的理论复杂度是TLE的，但是很显然我们每次check复杂度远远不到n^2，所以不会T。

 //It is made by jump~
 #include <iostream>
 #include <cstdlib>
 #include <cstring>
 #include <cstdio>
 #include <cmath>
 #include <algorithm>
 #include <ctime>
 #include <vector>
 #include <queue>
 #include <map>
 #include <set>
 using namespace std;
 typedef long long LL;
 const int inf = (<<);
 const int MAXN = +;
 int n,minl,a,b,c;
 int ini[MAXN],p[MAXN],L[MAXN];
 //c[i]+p[i]*x=c[j]+p[j]*x-now*y   ==>  (c[i]-c[j])*x+now*y=c[j]-c[i]

 inline int getint()
 {
     int w=,q=; char c=getchar();
     while((c<'' || c>'') && c!='-') c=getchar(); if(c=='-') q=,c=getchar();
     while (c>='' && c<='') w=w*+c-'', c=getchar(); return q ? -w : w;
 }

 inline int gcd(int x,int y){
     if(y==) return x;
     return gcd(y,x%y);
 }

 inline void extend_gcd(int a,int b,int &x,int &y){
     if(b==) {
     x=;
     y=;
     return ;
     }
     extend_gcd(b,a%b,x,y);
     int lin=x; x=y;
     y=lin-(a/b)*y;
 }

 inline void check(int now){//两两检查合法性
     int gong,x,y;
     for(int i=;i<n;i++)
     for(int j=i+;j<=n;j++) {
         a=(p[i]-p[j]); b=now; c=(ini[j]-ini[i]);  gong=gcd(a,b);
         if(c%gong!=) continue; //无解
         a=a/gong; b=b/gong; c=c/gong;
         extend_gcd(a,b,x,y);
         if(b<) b=-b;
         x=x*c; x%=b; x+=b; x+=b; x%=b;
         if(x<=L[i] && x<=L[j]) return ;
     }
     printf("%d",now);
     exit();
 }

 inline void work(){
     n=getint();  for(int i=;i<=n;i++) ini[i]=getint(),p[i]=getint(),L[i]=getint();
     for(int i=;i<=n;i++) minl=max(minl,ini[i]);//至少是ini[i]的最大值
     for(;;minl++) check(minl);
 }

 int main()
 {
     work();
     return ;
 }