题目

分析

考虑二分答案，

二分小数显然是不可取的，那么我们将所有可能的答案求出来，记录在一个数组上，排个序（C++调用函数很容易超时，手打快排，时间复杂度约为\(O(>8*10^7)\),但相信梦想的力量）。

剩下就简单了，将二分出的值判断是否可以获得k分以上，

这里可以用多种方法，spfa、dp

dp：

\(dp_i\)表示移动到了第i个点的最大分数

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

const long long maxlongint=2147483647;

const long long mo=1000000007;

const long long N=2005;

using namespace std;

long long ans,a[N][3],n,m,tot,f[N];

double sum[N][N];

struct ddx

{

	long long a,b,c;

	double ans;

}d[N*N];

double cale(ddx x)

{

	return 1.0*x.a*sqrt(x.b)/x.c;

}

bool cmp(ddx x,ddx y)

{

	return x.ans<y.ans;

}

void q(int l,int r)

{

	int i=l,j=r,e1;

	double mid=d[(l+r)/2].ans;

	double e;

	while(i<j)

	{

		while(d[i].ans<mid) i++;

		while(d[j].ans>mid) j--;

		if(i<=j)

		{

			e1=d[i].a;

			d[i].a=d[j].a;

			d[j].a=e1;

			e1=d[i].b;

			d[i].b=d[j].b;

			d[j].b=e1;

			e1=d[i].c;

			d[i].c=d[j].c;

			d[j].c=e1;

			e=d[i].ans;

			d[i].ans=d[j].ans;

			d[j].ans=e;

			i++;

			j--;

		}

	}

	if(i<r) q(i,r);

	if(l<j) q(l,j);

}

bool ok(double x)

{

	memset(f,0,sizeof(f));

	for(long long i=1;i<=n;i++)

	{

		for(long long j=0;j<=i-1;j++)

		{

			if(sum[i][j]<=x)

			{

				f[i]=max(f[i],f[j]+1);

			}

		}

		if(f[i]>=m)

			return true;

	}

	return false;

}

long long gcd(long long x,long long y)

{

    return x==0?y:gcd(y%x,x);

}

int work(int x)

{

	for(long long i=sqrt(d[x].b);i>=1;i--)

	{

		if(d[x].b%(i*i)==0)

		{

			d[x].b/=i*i;

			d[x].a*=i;

			break;

		}

	}

	long long k=gcd(d[x].a,d[x].c);

	if(!k) return 0;

	d[x].a/=k;

	d[x].c/=k;

}

double rf(long long l,long long r)

{

	while(l<r)

	{

		long long mid=(l+r)/2;

		if(ok(d[mid].ans))

			r=mid;

		else

			l=mid+1;

	}

	work(l);

	printf("%lld %lld %lld",d[l].a,d[l].b,d[l].c);

}

int main()

{

	scanf("%lld%lld",&n,&m);

	for(long long i=1;i<=n;i++)

		for(long long j=0;j<=2;j++)

		{

			scanf("%lld",&a[i][j]);

		}

	for(long long i=0;i<=n-1;i++)

		for(long long j=i+1;j<=n;j++)

		{

			d[++tot].a=1;

			d[tot].b=(a[j][1]-a[i][1])*(a[j][1]-a[i][1])+(a[j][2]-a[i][2])*(a[j][2]-a[i][2]);

			d[tot].c=a[j][0]-a[i][0];

			d[tot].ans=cale(d[tot]);

			sum[i][j]=sum[j][i]=d[tot].ans;

		}

	q(1,tot);

	rf(1,tot);

}

巴特西

【NOIP2016提高A组模拟9.15】Osu

题目

分析

最新文章

热门文章