NOI 2002 荒岛野人
人生第一次做NOI的题祭!!!
大概是NOI最简单的一道题
克里特岛以野人群居而著称。岛上有排列成环行的M个山洞。这些山洞顺时针编号为1,2,…,M。岛上住着N个野人,一开始依次住在山洞C1,C2,…,CN中,以后每年,第i个野人会沿顺时针向前走Pi个洞住下来。
每个野人i有一个寿命值Li,即生存的年数。
下面四幅图描述了一个有6个山洞,住有三个野人的岛上前四年的情况。三个野人初始的洞穴编号依次为1,2,3;每年要走过的洞穴数依次为3,7,2;寿命值依次为4,3,1。
(图片就不考了)
我们发现这道题奇怪的给了答案的数据规模,这就说明我们可以枚举答案。
然后我们发现n的数据规模很小,n^2*m似乎可以过。
我们对于每一个答案,枚举任意两个人是否不会相遇。
对于每两个野人,我们可以根据他们的C和P列出同余方程:
Ci+Pi*x≡Cj+Pj*x(mod b) 其中x是年数,b是枚举的答案。
然后,将这个同余方程转化为不定方程,然后求解。
Ci+Pi*x=Cj+Pj*x+b*-y(-y是一个构造的新的未知数)
(Pi-Pj)*x+b*y=Cj-Ci
然后用拓展欧几里得求解(这是解析)求解
最后一定要注意!!!(因为在这里卡了几个小时)求完特解以后,要保证最终解为正。
通常情况,只需要(x*(Cj-Ci)/d(最小公约数)+b/d)%b/d就可以了。
但是注意Cj-Ci可能为负,而且c++的负数取模的机制是取决于被模数,被模数为正则余数为正,为负则反之。
而因为Cj-Ci可能为负,可能导致最终答案依然为负。
故此,我们将x*(Cj-Ci)/d先模b/d,保证其绝对值是小于b/d的,但是,b/d也可能为负(因为d可能为负),所以即使加上一个b/d也不能保证结果为正。
因此,我们把最后加上的b/d变成一个它的倍数且保证它为正的,可以替换为b或者b/d的绝对值。
代码如下:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN 10010
#define in(a) a=read()
#define REP(i,k,n) for(int i=k;i<=n;i++)
using namespace std;
inline int read(){
int x=,f=;
char ch=getchar();
for(;!isdigit(ch);ch=getchar())
if(ch=='-')
f=-;
for(;isdigit(ch);ch=getchar())
x=x*+ch-'';
return x*f;
}
int n,m;
int c[],p[],l[];
int t;
inline void exgcd(int a,int b,int &d,int &x,int &y){
if(b==) x=,y=,d=a;
else exgcd(b,a%b,d,x,y),t=x,x=y,y=t-a/b*y;
}
inline bool check(int k){
REP(i,,n)
REP(j,i+,n){
int a=p[i]-p[j],b=k,x,y,d;
exgcd(a,b,d,x,y);
if((c[j]-c[i])%d!=) continue;
x=((x*(c[j]-c[i])/d)%(b/d)+(abs(b/d)))%(b/d);//保证x为正
if(x<=min(l[i],l[j])) return ;
}
return ;
}
int main(){
in(n);
REP(i,,n) in(c[i]),in(p[i]),in(l[i]),m=max(m,c[i]);
REP(i,m,) if(check(i)){ cout<<i<<endl; return ;}
return ;
}
最新文章
- iOS之访问权限以及跳转到系统界面
- 【Java EE 学习 78 中】【数据采集系统第十天】【Spring远程调用】
- C++ string类的实现
- Android 开发必备
- [转] KVM Internals, code and more
- jQuery基于ajax实现星星评论代码
- Vim的snipMate插件
- Oracle表管理
- SVN提交忽略*.class、.classpath、.mymetadata、.project、.settings、.myeclipse和其他非版本控制文件
- springmvc配置aop
- 如何在Oracle中复制表结构和表数据 【转载】
- Java 运行期数据区
- UDP和TCP的差异
- Ubuntu 自动选择最快的镜像源
- 操作系统下cache的几个概念
- our happy ending(状压dp)
- 关于python中pika模块的问题
- dos脚本
- NPM(包管理器)作用是什么?
- sql server 数字字符串的排序