尧图网页设计 
【题目描述】原题来自NOI 2002克里特岛以野人群居而著称。岛上有排列成环行的 M 个山洞。这些山洞顺时针编号为 1,2,⋯,M。岛上住着 N 个野人一开始依次住在山洞 C[1],C[2],⋯,C[N] 中以后每年第 i 个野人会沿顺时针向前走 P[i]个洞住下来。每个野人 i 有一个寿命值 L[i] 即生存的年数。下面四幅图描述了一个有 6 个山洞住有三个野人的岛上前四年的情况。三个野人初始的洞穴编号依次为 1,2,3每年要走过的洞穴数依次为 3,7,2寿命值依次为 4,3,1。奇怪的是虽然野人有很多但没有任何两个野人在有生之年处在同一个山洞中使得小岛一直保持和平与宁静这让科学家们很是惊奇。他们想知道至少有多少个山洞才能维持岛上的和平呢【输入】第一行为一个整数 N即野人的数目第二行到第 N1 每行为三个整数 C[i],P[i],L[i] 表示每个野人所住的初始洞穴编号每年走过的洞穴数及寿命值。【输出】仅包含一个数 M即最少可能的山洞数。输入数据保证有解且 M 不大于 10^6。【输入样例】3 1 3 4 2 7 3 3 2 1【输出样例】6【提示】样例说明该样例对应于题目描述中的例子。数据范围与提示对于全部数据1≤N≤15,1≤C[i],P[i]≤100,0≤L[i]≤10^6。1. 题意转换剥开“荒岛”、“野人”、“寿命”这层奇妙的包装这道题本质上是在求寻找一个最小的模数 MM≥max(C[i])使得对于任意两个野人 i 和 j线性同余方程 (P[i]−P[j])*x≡Cj−Ci (mod M) 的最小非负整数解 x 都满足 xmin(L[i],L[j])即在有生之年无解。这道题是“相遇问题”在模运算体系下的经典建模核心模型为从小到大枚举 扩展欧几里得算法。2. 思考过程与解题思路第一直觉的暴力解法面对“每年走 P[i] 步”的设定初学者最容易想到的就是开一个数组模拟岛上的山洞用一个外层大循环遍历年份 x逐年模拟每个野人的位置并检查是否冲突。为什么会超时野人的最大寿命 L[i]≤10^6山洞数 M 最多也会到10^6。如果一年年去模拟不仅每次都要判定 O(N^2) 对野人还会因为无法确定 M 的上限陷入死循环。推导正解的破局之路遇到环形相遇问题我们要形成条件反射——用同余方程代替步步模拟。 假设野人 i 和野人 j 在第 x 年相遇说明他们此时所处的洞穴编号在模 M 意义下是相等的C[i]x⋅P[i]≡C[j]x⋅P[j] (mod M)移项化简把未知数 x 放在左边已知常数放在右边(P[i]−P[j])*x≡C[j]−C[i] (mod M)这瞬间就变成了一个标准的二元一次不定方程(P[i]−P[j])*xM⋅yC[j]−C[i]既然能够通过扩展欧几里得算法瞬间算出两人相遇的年份 x那我们还需要枚举年份吗完全不需要 观察一下数据范围野人数量 N≤15 是一个极其诡异且明显的暗示。这意味着野人两两配对的总数最多只有 15×14/2105 对 于是思路豁然开朗我们只要从小到大枚举山洞总数 M对于每个 M利用 exgcd 校验这 105 对野人会不会在有生之年相撞。一旦发现有相撞的立刻毙掉当前 M 并M。第一个让所有野人都相安无事的 M就是我们的答案。3. 算法设计与样例推演算法执行流程与核心校验逻辑确定起点山洞总数 M 绝对不能小于岛上的野人数 N更不能小于任何一个野人初始居住的洞穴编号物理限制。所以枚举起点 nummax(N,max(C[i]))。双重循环枚举野人对 (i,j)令 aP[i]−P[j]bnumcC[j]−C[i]。为了防止负数干扰 exgcd 的计算若 a0只需等式两边同乘 −1即 a−a, c−c。呼叫exgcd(a,b,x,y)得到最大公约数 d。如果c能被d整除说明方程有解两人有可能相遇。将基础解通过缩放和黄金转正句型转化为最小非负相遇年份 x0。终极审判如果 x0≤min(L[i],L[j])说明两人在活着的时候撞车了当前山洞数 num 失败跳出循环继续检验 num1。极简数据手玩推演带入题目样例 假设校验到了样例中的山洞数 num6。 取出野人 2 和野人 3野人 2C[2]2,P[2]7,L[2]3野人 3C[3]3,P[3]2,L[3]1构建方程(P[2]−P[3])*x6yC[3]−C[2]⟹(7−2)x6y3−2⟹5x6y1。调用 exgcd解得基础解 x0−1dgcd(5,6)1。计算放大倍数times1/11。计算模数周期mod6/16。转正最小年份x0( (−1×1) (mod 6)6) (mod 6)5。 两人如果要相遇最早是在第 5 年。寿命校验野人 2 活 3 年野人 3 活 1 年min(3,1)1。相遇年份 51因此两人在有生之年完美错开不会冲突4. 时空复杂度分析时间复杂度O(M[ans]⋅N^2⋅log(maxP))。 最坏情况下我们要枚举约 10^6 次 M。每次校验需要 O(N^2) 次单次 exgcd 的复杂度是 O(logP)。表面上看 10^6×105×log2(100)≈7×10^8 可能会卡常。但实际上这是一个极度宽松的上限。因为绝大多数不合法的 M 在前几次野人配对校验中就会立刻break常数极小实际运行时间都在 10ms 级别对于 1s 的时限极其安逸。空间复杂度O(N)。只需几个长度为 20 的数组来存储 15 个野人的信息空间占用几乎为 0不可能MLE。5. 坑点与易错总结物理界限的盲区很多同学知道 M 至少从 N 开始枚举却忘了如果 1 号野人一开始就住在 10 号洞山洞总数绝不可能少于10。因此 M 的枚举下界必须是 max(C[i])。符号颠倒的负数陷阱在推导 (P[i]−P[j])*x 时P[i]−P[j] 完全可能是负数。直接送进同余系统中C 的%运算对负数处理极易出错。巧妙的解法是如果 P[i]−P[j]0让等号左右两端同时取反强行转正。周期必须除以最大公约数在求最终年份时扩欧求出的局部周期必须是 num/gcd千万不能直接%num。乘法防爆习惯培养虽然本题数据范围小P[i],C[i]≤100int乘法x0 * times不会溢出但在正规比赛中凡是扩欧的放大步数计算建议肌肉记忆般地使用long long或__int128防止“死在数据类型上”。6. 完整代码//数据量n小于等于15 非常小 所以可以直接暴力求解 //直接从最小可能山洞数开始枚举最小山洞数肯定不能小于野人数 //然后每次枚举的山洞数num //如果两个野人要相遇 代表 //c[i]x0*p[i]≡c[j]x[0]*p[j] (mod num) //移项 变成x0*(p[i]-p[j])≡c[j]-c[i] (mod num) //再变成 x0*(p[i]-p[j])num*y0c[j]-c[i] //扩欧求解x0 //x0代表年数如果算出来的x0比l[i]和l[j](野人寿命都小 //则代表第i个野人和第j个野人有生之年会住进同一个山洞 //就直接continue 然后增加山洞数 //直到所有野人有生之年都不会相遇 这个山洞数就OK #include iostream using namespace std; int n; int c[20];//c[i]代表第i个野人所住的初始洞穴编号 int p[20];//p[i]代表第i个野人每年走过的洞穴数 int l[20];//l[i]代表第i个野人的寿命 int num;//山洞数量 从最小山洞数n开始最小山洞数肯定不能小于野人数 //扩欧 int exgcd(int a,int b,int x,int y){ if(b0){ x1; y0; return a; } int dexgcd(b,a%b,x,y); int tmpx; xy; ytmp-(a/b)*y; return d; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinn; numn;//最小山洞数肯定不能小于野人数 //存储每个野人的信息 for(int i1;in;i){ cinc[i]p[i]l[i]; nummax(n,c[i]);//山洞数目不能小于最开始野人居住的山洞位置 } //遍历洞穴数量 从最小山洞数n开始最小山洞数肯定不能小于野人数 while(1){ bool flag1;//标记 当前山洞数量能否满足要求 //枚举所有野人两两比对 for(int i1;in;i){ for(int ji1;jn;j){ int x0; int y0; int ap[i]-p[j]; int weishuc[j]-c[i]; //确保a不能为负数 //如果a0 等式左右两边同时乘以-1 保持平衡 if(a0){ a0-a; weishu0-weishu; } int dexgcd(a,num,x0,y0); //根据裴蜀定理 如果有解 if((weishu%d)0){ //算出放大倍数 实际常数是基础常数gcd的多少倍 int timesweishu/d; //算出新的模数周期 方程同除以d后 模数也要随之缩小 int modnum/d; //算出非负最小寿命 即两人相遇的最小非负整数年 x0((x0*times)%modmod)%mod; //如果第i个野人和第j个野人寿命都比x0大 //代表有生之年会住进一个山洞 //代表肯定不行 把标记改为0 if(l[i]x0l[j]x0){ flag0; break; } } } //如果标记已经为0 直接num 退出本轮循环 if(flag0){ num; break; } } //如果遍历完所有野人 flag为1代表当前num满足条件 if(flag1){ coutnum; return 0; } } return 0; } 荒岛野人（信息学奥赛一本通- P1637）（洛谷-P2421）
【题目描述】原题来自NOI 2002克里特岛以野人群居而著称。岛上有排列成环行的 M 个山洞。这些山洞顺时针编号为 1,2,⋯,M。岛上住着 N 个野人一开始依次住在山洞 C[1],C[2],⋯,C[N] 中以后每年第 i 个野人会沿顺时针向前走 P[i]个洞住下来。每个野人 i 有一个寿命值 L[i] 即生存的年数。下面四幅图描述了一个有 6 个山洞住有三个野人的岛上前四年的情况。三个野人初始的洞穴编号依次为 1,2,3每年要走过的洞穴数依次为 3,7,2寿命值依次为 4,3,1。奇怪的是虽然野人有很多但没有任何两个野人在有生之年处在同一个山洞中使得小岛一直保持和平与宁静这让科学家们很是惊奇。他们想知道至少有多少个山洞才能维持岛上的和平呢【输入】第一行为一个整数 N即野人的数目第二行到第 N1 每行为三个整数 C[i],P[i],L[i] 表示每个野人所住的初始洞穴编号每年走过的洞穴数及寿命值。【输出】仅包含一个数 M即最少可能的山洞数。输入数据保证有解且 M 不大于 10^6。【输入样例】3 1 3 4 2 7 3 3 2 1【输出样例】6【提示】样例说明该样例对应于题目描述中的例子。数据范围与提示对于全部数据1≤N≤15,1≤C[i],P[i]≤100,0≤L[i]≤10^6。1. 题意转换剥开“荒岛”、“野人”、“寿命”这层奇妙的包装这道题本质上是在求寻找一个最小的模数 MM≥max(C[i])使得对于任意两个野人 i 和 j线性同余方程 (P[i]−P[j])*x≡Cj−Ci (mod M) 的最小非负整数解 x 都满足 xmin(L[i],L[j])即在有生之年无解。这道题是“相遇问题”在模运算体系下的经典建模核心模型为从小到大枚举 扩展欧几里得算法。2. 思考过程与解题思路第一直觉的暴力解法面对“每年走 P[i] 步”的设定初学者最容易想到的就是开一个数组模拟岛上的山洞用一个外层大循环遍历年份 x逐年模拟每个野人的位置并检查是否冲突。为什么会超时野人的最大寿命 L[i]≤10^6山洞数 M 最多也会到10^6。如果一年年去模拟不仅每次都要判定 O(N^2) 对野人还会因为无法确定 M 的上限陷入死循环。推导正解的破局之路遇到环形相遇问题我们要形成条件反射——用同余方程代替步步模拟。 假设野人 i 和野人 j 在第 x 年相遇说明他们此时所处的洞穴编号在模 M 意义下是相等的C[i]x⋅P[i]≡C[j]x⋅P[j] (mod M)移项化简把未知数 x 放在左边已知常数放在右边(P[i]−P[j])*x≡C[j]−C[i] (mod M)这瞬间就变成了一个标准的二元一次不定方程(P[i]−P[j])*xM⋅yC[j]−C[i]既然能够通过扩展欧几里得算法瞬间算出两人相遇的年份 x那我们还需要枚举年份吗完全不需要 观察一下数据范围野人数量 N≤15 是一个极其诡异且明显的暗示。这意味着野人两两配对的总数最多只有 15×14/2105 对 于是思路豁然开朗我们只要从小到大枚举山洞总数 M对于每个 M利用 exgcd 校验这 105 对野人会不会在有生之年相撞。一旦发现有相撞的立刻毙掉当前 M 并M。第一个让所有野人都相安无事的 M就是我们的答案。3. 算法设计与样例推演算法执行流程与核心校验逻辑确定起点山洞总数 M 绝对不能小于岛上的野人数 N更不能小于任何一个野人初始居住的洞穴编号物理限制。所以枚举起点 nummax(N,max(C[i]))。双重循环枚举野人对 (i,j)令 aP[i]−P[j]bnumcC[j]−C[i]。为了防止负数干扰 exgcd 的计算若 a0只需等式两边同乘 −1即 a−a, c−c。呼叫exgcd(a,b,x,y)得到最大公约数 d。如果c能被d整除说明方程有解两人有可能相遇。将基础解通过缩放和黄金转正句型转化为最小非负相遇年份 x0。终极审判如果 x0≤min(L[i],L[j])说明两人在活着的时候撞车了当前山洞数 num 失败跳出循环继续检验 num1。极简数据手玩推演带入题目样例 假设校验到了样例中的山洞数 num6。 取出野人 2 和野人 3野人 2C[2]2,P[2]7,L[2]3野人 3C[3]3,P[3]2,L[3]1构建方程(P[2]−P[3])*x6yC[3]−C[2]⟹(7−2)x6y3−2⟹5x6y1。调用 exgcd解得基础解 x0−1dgcd(5,6)1。计算放大倍数times1/11。计算模数周期mod6/16。转正最小年份x0( (−1×1) (mod 6)6) (mod 6)5。 两人如果要相遇最早是在第 5 年。寿命校验野人 2 活 3 年野人 3 活 1 年min(3,1)1。相遇年份 51因此两人在有生之年完美错开不会冲突4. 时空复杂度分析时间复杂度O(M[ans]⋅N^2⋅log(maxP))。 最坏情况下我们要枚举约 10^6 次 M。每次校验需要 O(N^2) 次单次 exgcd 的复杂度是 O(logP)。表面上看 10^6×105×log2(100)≈7×10^8 可能会卡常。但实际上这是一个极度宽松的上限。因为绝大多数不合法的 M 在前几次野人配对校验中就会立刻break常数极小实际运行时间都在 10ms 级别对于 1s 的时限极其安逸。空间复杂度O(N)。只需几个长度为 20 的数组来存储 15 个野人的信息空间占用几乎为 0不可能MLE。5. 坑点与易错总结物理界限的盲区很多同学知道 M 至少从 N 开始枚举却忘了如果 1 号野人一开始就住在 10 号洞山洞总数绝不可能少于10。因此 M 的枚举下界必须是 max(C[i])。符号颠倒的负数陷阱在推导 (P[i]−P[j])*x 时P[i]−P[j] 完全可能是负数。直接送进同余系统中C 的%运算对负数处理极易出错。巧妙的解法是如果 P[i]−P[j]0让等号左右两端同时取反强行转正。周期必须除以最大公约数在求最终年份时扩欧求出的局部周期必须是 num/gcd千万不能直接%num。乘法防爆习惯培养虽然本题数据范围小P[i],C[i]≤100int乘法x0 * times不会溢出但在正规比赛中凡是扩欧的放大步数计算建议肌肉记忆般地使用long long或__int128防止“死在数据类型上”。6. 完整代码//数据量n小于等于15 非常小 所以可以直接暴力求解 //直接从最小可能山洞数开始枚举最小山洞数肯定不能小于野人数 //然后每次枚举的山洞数num //如果两个野人要相遇 代表 //c[i]x0*p[i]≡c[j]x[0]*p[j] (mod num) //移项 变成x0*(p[i]-p[j])≡c[j]-c[i] (mod num) //再变成 x0*(p[i]-p[j])num*y0c[j]-c[i] //扩欧求解x0 //x0代表年数如果算出来的x0比l[i]和l[j](野人寿命都小 //则代表第i个野人和第j个野人有生之年会住进同一个山洞 //就直接continue 然后增加山洞数 //直到所有野人有生之年都不会相遇 这个山洞数就OK #include iostream using namespace std; int n; int c[20];//c[i]代表第i个野人所住的初始洞穴编号 int p[20];//p[i]代表第i个野人每年走过的洞穴数 int l[20];//l[i]代表第i个野人的寿命 int num;//山洞数量 从最小山洞数n开始最小山洞数肯定不能小于野人数 //扩欧 int exgcd(int a,int b,int x,int y){ if(b0){ x1; y0; return a; } int dexgcd(b,a%b,x,y); int tmpx; xy; ytmp-(a/b)*y; return d; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinn; numn;//最小山洞数肯定不能小于野人数 //存储每个野人的信息 for(int i1;in;i){ cinc[i]p[i]l[i]; nummax(n,c[i]);//山洞数目不能小于最开始野人居住的山洞位置 } //遍历洞穴数量 从最小山洞数n开始最小山洞数肯定不能小于野人数 while(1){ bool flag1;//标记 当前山洞数量能否满足要求 //枚举所有野人两两比对 for(int i1;in;i){ for(int ji1;jn;j){ int x0; int y0; int ap[i]-p[j]; int weishuc[j]-c[i]; //确保a不能为负数 //如果a0 等式左右两边同时乘以-1 保持平衡 if(a0){ a0-a; weishu0-weishu; } int dexgcd(a,num,x0,y0); //根据裴蜀定理 如果有解 if((weishu%d)0){ //算出放大倍数 实际常数是基础常数gcd的多少倍 int timesweishu/d; //算出新的模数周期 方程同除以d后 模数也要随之缩小 int modnum/d; //算出非负最小寿命 即两人相遇的最小非负整数年 x0((x0*times)%modmod)%mod; //如果第i个野人和第j个野人寿命都比x0大 //代表有生之年会住进一个山洞 //代表肯定不行 把标记改为0 if(l[i]x0l[j]x0){ flag0; break; } } } //如果标记已经为0 直接num 退出本轮循环 if(flag0){ num; break; } } //如果遍历完所有野人 flag为1代表当前num满足条件 if(flag1){ coutnum; return 0; } } return 0; }