当前位置: 首页 > news >正文

洛谷题单指南-进阶数论-P2421 [NOI2002] 荒岛野人

原题链接:https://www.luogu.com.cn/problem/P2421

题意解读:一个环形坐标轴,n个点初始位于C1、C2...Cn,每个点每次逆时针移动P1、P2...Pn步,每个点分别最多只能移动L1、L2...Ln步,要求n个点能移动的点每次同时移动,且不能有任意两个点相遇,求满足要求的环形坐标轴最小的长度。

解题思路:

要求环形坐标轴的最小长度,不妨从小到大枚举这个长度,设为m

要求不能有任意两点相遇,可以枚举任意两点i,j在移动t次之后的位置,那么

应该有(Ci + Pi * t) % m != (Cj + Pj * t) % m,

转化成等式表达,即(Ci + Pi * t) % m = (Cj + Pj * t) % m 在t <= min(Li, Lj)时没有正整数解

进一步转化,设未知数s,Ci + Pi * t + m * s = Cj + Pj * t 在t <= min(Li, Lj)时没有正整数解

移项:(Pi - Pj) * t + m * s = Cj - Ci,另a = |Pi - Pj|, b = m, c =  (Pi > Pj ? 1 : -1) * (Cj - Ci)

用扩展欧几里得算法求a * t + b * s = c的关于t的最小正整数解t0,如果gcd(a,b)不能被c整除(表示无正整数解)或者求出的t0 > min(Li, Lj)则表示满足要求。

如果所有的点对都满足要求,则此时的m即为答案。

不难发现,对于每两个点的处理就是P1516青蛙的约会

100分代码:

#include <bits/stdc++.h>
using namespace std;const int N = 20, M = 1000000;int C[N], P[N], L[N];
int maxc;
int n;int exgcd(int a, int b, int &x, int &y)
{if(b == 0){x = 1, y = 0;return a;}int d = exgcd(b, a % b, y, x);y -= a / b * x;return d;
}int main()
{cin >> n;for(int i = 1; i <= n; i++) {cin >> C[i] >> P[i] >> L[i];maxc = max(maxc, C[i]);}for(int m = maxc; m <= M; m++){int yes = true;for(int i = 1; i < n; i++){for(int j = i + 1; j <= n; j++){int a = abs(P[i] - P[j]);int b = m;int c = (P[i] > P[j] ? 1 : -1) * (C[j] - C[i]);int t, s;int d = exgcd(a, b, t, s);if(c % d) continue;t *= (c / d);t = (t % (b / d) + b / d) % (b / d); //t的最小正整数解if(t > min(L[i], L[j])) continue;yes = false;break;}if(!yes) break;}if(!yes) continue;cout << m;break;}return 0;
}

 

http://www.hskmm.com/?act=detail&tid=28816

相关文章:

  • 2025粉末涂料厂家最新推荐榜:环保高效与色彩持久的行业佼佼
  • Idea摸鱼看小说插件(YsQy-Book)-免费使用
  • 贴牛皮纸铝卷生产商推荐/铝卷生产厂家/铝卷哪家好
  • 2025浇注型聚氨酯厂家口碑排行榜:品质与服务双优之选
  • RAFT 共识算法
  • 2025氧化镁厂家最新推荐榜:高纯度与优质服务并重的行业先锋
  • contenteditable 深度交互教程
  • 距离和
  • 2025风机盘管厂家口碑推荐榜:高效节能与稳定性能的行业首选
  • 痞子衡嵌入式:在i.MXRT下测试启动特性时可改写OTP Shadow寄存器而不烧OTP
  • 直流微电网运行控制仿真算法设计与实现
  • 基于MATLAB的多棵树分类器(随机森林)
  • 车载360环视平台:米尔RK3576开发板支持12路低延迟推流
  • 2025双氧水厂家最新推荐榜:品质卓越与环保安全的首选品牌!
  • TDengine 3.3.6.0 使用Docker部署3节点集群
  • 05-字符设备驱动之ioctl
  • 2025氧化镁厂家最新推荐榜:高纯度与稳定性能的行业佼佼者!
  • 从“视频孤岛”到“统一视界”:解析视频汇聚平台EasyCVR的核心功能与应用场景
  • 个人博客作业 1:就《现代软件工程》提 5 个问题
  • 2025 年锅炉优质厂家最新推荐榜单:高效节能与环保性能全方位剖析,助您选到靠谱锅炉供应商
  • 2025 年商用洗碗机源头厂家最新推荐榜:聚焦实力企业,为餐饮及企事业单位选购提供可靠参考
  • EHOME平台EasyCVR视频诊断功能指南:一文读懂其可识别的所有视频质量问题
  • html介绍+运用
  • 2025 年 氨糖软骨素厂家哪家好?傦力宝产品选购指南,解析研发实力与品质优势
  • 【SPIE出版】2025年信息工程、智能信息技术与人工智能国际学术会议(IEITAI 2025)
  • go读取二进制文件编译信息
  • 2025锯床厂家最新推荐榜:精准切割与高效性能的行业首选!
  • 2025.10.10 图论
  • xshell把界面转发到xming
  • 使用AI创建angular项目