Bzoj 1150
Bzoj 1145

Bzoj 1407

coc youyl posted @ 2015年7月02日 20:03 in bzoj , 1063 阅读

题目分类:数学,扩展gcd

题意:

给出n个野人的初始位置,速度和寿命,求出一个最小的环使得野人在有生之年不会相遇【野人神奇的活了1000000岁?】

题解:

枚举答案之后转化为求同余方程的最小自然数解,可以用扩展gcd解决。

程序:

#include<cstdio>
#include<algorithm>
using namespace std;
inline int extgcd(int a,int b,int &x,int &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	int xx,yy,d=extgcd(b,a%b,xx,yy);
	x=yy;
	y=xx-a/b*yy;
	return d;
}
int n;
int c[20],p[20],l[20];
inline bool judge(int x,int y,int mm,int xx,int yy)
{
	int tx,ty;
	int td=extgcd(x,mm,tx,ty);
	if(y%td!=0)return false;
	tx*=y/td;
	while (tx>mm/td)tx-=mm/td;
	while (tx<0)tx+=mm/td;
	if(tx<=l[xx]&&tx<=l[yy])return true;
	return false;
}
inline bool check(int mm)
{
	for (int i=1;i<n;i++)
	{
		for (int j=i+1;j<=n;j++)
		{
			int tx=p[i]-p[j],ty=c[j]-c[i];
			if(tx<0)
			{
				tx=-tx;
				ty=-ty;
			}
			if(judge(tx,ty,mm,i,j))return true;
		}
	}return false;
}
int ans;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d %d %d",&c[i],&p[i],&l[i]);
		ans=max(ans,c[i]);
	}
	for (;check(ans);ans++);
	printf("%d\n",ans);
	return 0;
}
Grade 8 Result madra 说:
2022年8月31日 14:56

Madrasah Education Board is most popular in the country of Bangladesh, and they have successfully conducted the Junior Dakhil Certificate examination tests for Grade 8 level students at all education boards at all divisions in district wise across in the country, and there are lakhs of students are appeared from all Madhrasah’s of the country, and the Secondary Education Board also completed the JDC terminal exams 2022 successfully based on JDC routine 2022. Grade 8 Result madrasah The Class 8th Grade student who has appeared to the annual final terminal exams they are waiting to check JDC Result 2022 Madrasah Board with full mark sheet, the student who is qualified in this examination they are promoted to higher class in Mass education board, every student who has appeared to the JDC exams 2022 are waiting to check their result with subject wise marks along with final GPA grade point.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter