首页 > 其他分享 >P2421-荒岛野人Savage题解

P2421-荒岛野人Savage题解

时间:2024-03-28 15:45:04浏览次数:27  
标签:Savage ch 题解 times 野人 le P2421 式子

好久没写题解了啊


洛谷P2421 荒岛野人

题目大意:有一个有很多洞的岛上,住了\(n\)个野人,每个野人的初始位置为\(c[i]\),换洞的速度为\(p[i]\),寿命为\(l[i]\)。要求求出洞的最少个数\(M\)满足每个野人在生存状态下不会在同一年和其他野人住在同一个山洞里。

概括版:很多个青蛙的约会。

首先根据题目 我们可以得出一个式子:

\[c[i]+p[i]\times t\equiv c[j]+p[j]\times t \pmod M (t\le min(l[i],l[j])) \]

其中 \(t\)为经过的年数,\(M\)为我们要求出的结果。

显然,如果上面的式子成立,说明这个结果食补满足题意的。

因此,我们的目的就可以简化为:求不满足上述式子的\(M\)的最小值。

当然,如果\(x>min(l[i],l[j])\),说明有野人已经死亡,之后式子恒成立。

题目给出 \(M\le 1e6\),所以直接枚举即可得出答案。

$check$函数部分推导过程

\[c[i]+p[i]\times t\equiv c[j]+p[j]\times t \pmod M (t\le min(l[i],l[j])) \]

\[c[i]-c[j]+t\times (p[i]-p[j])=k\times M \]

移项可得

\[t\times (p[j]-p[i])+k\times M=c[i]-c[j] \]

之后套入扩展欧几里得公式即可

$\large{code}$
#include<bits/stdc++.h>
#define fo(x,y,z) for(int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef long long ll;
inline int qr()
{
    char ch=getchar();int x=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
#define qr qr()
const int Ratio=0;
const int N=25;
const int maxx=INT_MAX;
int n,m=0,ans;
int s[N],p[N],l[N];
int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    int c=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return c;
}
bool check(int ii)
{
    // cout<<i<<endl;
    fo(i,1,n)
        fo(j,i+1,n)
        {
            int c=s[i]-s[j],b=ii,a=p[j]-p[i],x,y;
            int d=exgcd(a,b,x,y);
            if(c%d)
                continue;
            a/=d,b/=d,c/=d;
            if(b<0)
                b=-b;
            x=(x*c%b+b)%b;
            //找到解 如果这两个人都还活着 就false
            if(x<=l[i]&&x<=l[j])
                return false;
        }
    return true;
}
int main()
{
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    n=qr;
    fo(i,1,n)
        s[i]=qr,p[i]=qr,l[i]=qr,m=max(m,s[i]);
    for(int i=m;;i++)
        if(check(i))
        {
            // cout<<i<<endl;
            printf("%d\n",i);
            break;
        }
    return Ratio;
}

一些闲话

标签:Savage,ch,题解,times,野人,le,P2421,式子
From: https://www.cnblogs.com/Ratio-Yinyue1007/p/18101870

相关文章

  • 【题解】AGC007E | 二分答案 复杂度分析
    首先考虑题目要求每条边被经过两次,这说明了我们进入一个子树后一定会处理完子树内所有的叶子后离开该子树,否则子树上端那条边会进出至少两次,即经过至少四次。所以这说明了子树之间的独立性:某个子树在答案中一定是一个连续的区间,这引导我们从有根树信息自下向上拼接的角度考虑。我......
  • SP2426 PLD - Palindromes 题解
    题目传送门题目大意给定一个字符串,请你求出这个字符串中所有长度为kkk的回文串的个数。解题思路我们只需要枚举每个字串的起始位置......
  • [USACO24FEB] Bessla Motors G 题解
    题目大意对于每个充电站找它所能去到的非充电站的点TTT($C<T$同时两点的距离在RR......
  • 2006 年考研英语真题 - 翻译题解析
    2006 年考研英语真题 - 翻译题解析IsittruethattheAmericanintellectualisrejectedandconsideredofnoaccountinhissociety?[1] 翻译:难道美国的知识分子被嫌弃,在社会中不受重视吗?1.it 是形式主语,代指后面的 that 从句。2.Americanintellectual 美......
  • 2007 年考研英语真题 - 翻译题解析
    2007 年考研英语真题 - 翻译题解析ThestudyoflawhasbeenrecognizedforcenturiesasabasicintellectualdisciplineinEuropeanuniversities.[1]                  翻译:几个世纪以来,欧洲的各所大学一直认为法学学习是一门基础知识学科。1.......
  • P5470 [NOI2019]序列 题解
    P5470:NOI2019序列题意:给定两个长度\(n\)的序列\(a,b\)。要求各选出\(k\)个数,使得这\(2k\)个数之和最大,且两个序列选出的数至少有\(l\)个位置相同。\(n\le2\times10^5\)。command_block的题解但是这个貌似有一些小问题,后文有写。算法:模拟费用流。【费用流模......
  • 2003 年考研英语真题 - 翻译题解析
    2003 年考研英语真题 - 翻译题解析Humanbeingsinalltimesandplacesthinkabouttheirworldandwonderattheirplaceinit.[1]             翻译:各时期各地区的人们都思考各自的世界并想知道自己在其中的位置。1.Humanbeing 人;人类。2.inal......
  • 2002 年考研英语真题 - 翻译题解析
    2002年考研英语真题- 翻译题解析Almostallourmajorproblemsinvolvehumanbehavior,andtheycannotbesolvedbyphysicalandbiologicaltechnologyalone.[1]            翻译:几乎我们所有主要问题都涉及到人类行为,而这些问题仅靠物理和生物技术手......
  • 「CF1677D」Tokitsukaze and Permutations的题解
    「CF1677D」TokitsukazeandPermutations首先,若\(v\)的后\(k\)个数中有一个\(>0\),或有\(v_i>i-1(i\in[1,n])\),则无解。我们发现,每次对\(p\)进行了一次操作后,\(v\)也一定会对应的进行一次变化,所以统计\(p\)的个数就相当于统计\(v\)的个数。我们对于每一次冒泡排序......
  • [THUWC2018]城市规划的题解
    [THUWC2018]城市规划连通块问题,我们考虑树形DP。设\(f_{u,j}\)表示在以\(u\)为根的子树内,选的颜色集合为\(a_{u},j\)(两个颜色都必须选)且必须选点\(u\)的情况下的连通块个数。特殊的,\(f_{u,a_{u}}\)表示颜色只有\(a_{u}\)的情况数。对于\(v\inson_u\),有:若\(a_{u......