BZOJ 1407: [Noi2002]Savage

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

Solution

枚举 $m$，每次枚举两个野人，将他们的 $c_i,p_i$ 相减，记为 $c,p$，那么如果有一个 $k$ 在他们的年龄范围内，且 $c+pk\bmod m=0$，则这个 $m$ 不能取，$k$ 的最小值可以用扩展欧几里得求出。
预处理每两个野人的 $c_i,p_i$ 之差，$l_i$ 的最小值，可以优化时间。

Code

#include<cstdio>

int n,c[15],p[15],l[15],c2[105],p2[105],l2[105],n2=0;

inline int min(int a,int b)
{
    if(a<b)return a;else return b;
}

inline int max(int a,int b)
{
    if(a>b)return a;else return b;
}

int sol,gcd;

void exgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x=sol/a;y=0;
        gcd=a;
        return;
    }
    exgcd(b,a%b,y,x);
    y-=x*(a/b);
}

inline int safeexgcd(int a,int b,int &x,int &y)
{
    if(a<b)exgcd(b,a,y,x);else exgcd(a,b,x,y);
}

int main()
{
    int maxc=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d%d%d",c+i,p+i,l+i),maxc=max(c[i],maxc);
    for(int i=0;i<n;i++)
        for(int j=0;j<i;j++)
        {
            c2[n2]=c[i]-c[j];
            p2[n2]=p[i]-p[j];
            l2[n2]=min(l[i],l[j]);
            n2++;
        }
    for(int i=maxc;1;i++)
    {
        bool flag=true;
        int x,y;
        for(int j=0;j<n2;j++)
        {
            sol=-c2[j];
            safeexgcd(p2[j],i,x,y);
            if(p2[j]*x+i*y!=sol)continue;
            int tmp=i/gcd;
            x%=tmp;
            if(x<0)x+=tmp;
            if(x<=l2[j])
            {
                flag=false;
                break;
            }
        }
        if(flag)
        {
            printf("%d\n",i);
            return 0;
        }
    }
}

另外随便写的代码就第 4 了。

日期： 2016-09-14

标签： BZOJ 扩展gcd

这是一篇旧文，原始文章及评论可在 https://oldblog.mcfx.us/archives/27/ 查看。