UOJ Logo zgjkt的博客

博客

【bzoj1407】荒岛野人Savage

2015-11-07 12:40:42 By zgjkt

题目大意

给出$n$只野人,第$i$只野人一开始会住在山洞$pos_i$里,每年会顺时针往前走$step_i$个山洞住下来,寿命是$age_i$

假设山洞是环形排布,且野人在有生之年都不会见到他的同类,询问山洞的最少个数

数据范围

$1\leqslant n\leqslant 15,1\leqslant pos_i,step_i<=100, 0\leqslant age_i\leqslant 106$

数据保证有解,且不超过106


题解

拓展欧几里得,学习感谢大神系列

P.S.大神的代码是贴错了吧,不用看代码,看题解即可


程序

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
       int x=0,f=1;char ch=getchar();
       while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
       while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
       return x*f;
}

int n,mx;
int pos[20],step[20],age[20];
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
void exgcd(int a,int b,int &x,int &y){ 
    if (b==0){x=1;y=0;return;}
    exgcd(b,a%b,x,y);
    int t=x;x=y;y=t-a/b*y; 
}

inline int judge(int m){
    int a,b,c,g,x,y;
    For(i,1,n-1) For(j,i+1,n){
        a=step[i]-step[j],b=m,c=pos[j]-pos[i];
        g=gcd(a,b);
        if (c%g==0){
            a/=g,b/=g,c/=g;
            exgcd(a,b,x,y);
            b=abs(b);
            x=((c*x)%b+b)%b;
            if (!x) x+=b;
            if (x<=min(age[i],age[j])) return 0; 
        }
    }
    return 1;
} 

int main(){
    n=read();
    For(i,1,n){
        pos[i]=read(),step[i]=read(),age[i]=read();
        mx=max(pos[i],mx);
    }
    For(i,mx,inf)
        if (judge(i)) {printf("%d\n",i);return 0;} 
    return 0;
}

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。