[2018.12.13]BZOJ1407 [Noi2002]Savage

考虑枚举山洞数量,问题变为判断一定数量的山洞是否合法。

设山洞数量为\(k\),即使得对于任意\(i,j\),满足

\(C_i+P_ix\equiv C_j+P_jx(mod\ k)\)

的最小正整数解(即两者相遇的最小天数)不存在或大于\(min(L_i,L_j)\)。

化简方程

\(C_i+P_ix\equiv C_j+P_jx(mod\ k)\)

\((P_i-P_j)x\equiv P_j-P_i(mod\ k)\)

\((P_i-P_j)x+ky\equiv P_j-P_i\)

扩展欧几里得求解即可。

(注:需要将\(P_i-P_j\)变为不影响答案的正整数,即\(((P_i-P_j)mod\ k+k)mod\ k\))

code:

#include<bits/stdc++.h>
using namespace std;
int n,c[20],p[20],l[20],mnn,sv,mnv,tmp;
int exgcd(int a,int b,int &solx,int &soly){//a*solx+b*soly=sv
    if(!b){
        if(sv%a)return 0;
        solx=sv/a;
        soly=0;
        return a;
    }
    int sx,sy,t=exgcd(b,a%b,sx,sy);
    if(t){
        solx=sy;
        soly=sx-(a/b)*sy;
        return t;
    }else return 0;
}
bool Solve(int d){
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            sv=c[j]-c[i];
            int t=exgcd(((p[i]-p[j])%d+d)%d,d,mnv,tmp);
            if(!t)continue;
            int mod=d/t;
            mnv=(mnv%mod+mod)%mod;
            if(!mnv)mnv+=mod;
            if(mnv<=min(l[i],l[j]))return false;
        }
    }
    return true;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d%d",&c[i],&p[i],&l[i]),mnn=max(mnn,c[i]);
    for(int i=mnn;i<=1000000;i++)if(Solve(i))return printf("%d",i),0;
    return 0;
}

[2018.12.13]BZOJ1407 [Noi2002]Savage

原文：https://www.cnblogs.com/xryjr233/p/BZOJ1407.html