HZOI20190817模拟24

题面：https://www.cnblogs.com/Juve/articles/11369181.html

A：Star Way To Heaven

考场上以为只能走直线，于是挂掉了。

有一种方法是二分，二分答案

给每个点一个半径r，如果我们发现这个矩形被几个圆截断，那么说明没有路可走，不符合情况，

如果符合，就更新答案。

具体实现可以用并查集。

joe巨佬的二分：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<stack>

#include<cmath>

#include<algorithm>

#define int long long

#define rint register int

using namespace std;

int n,m,k,tot,first[60003],fa[6003];

int yh[6003][4];

bool vis[60003];

struct node{int x,y;}p[60003];

inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

inline double dist(int uu,int vv)

{

	return (p[uu].x-p[vv].x)*(p[uu].x-p[vv].x)+(p[uu].y-p[vv].y)*(p[uu].y-p[vv].y);

}

inline bool check(double x)

{

	for(rint i=0;i<=k+1;++i)fa[i]=i;

	for(rint i=1;i<=k;++i)

		for(rint j=0;j<=3;++j)

		{

			if(!yh[i][j])continue;

			if(dist(i,yh[i][j])<4*x*x)

			{

				int lx=find(i),ly=find(yh[i][j]);

				if(lx!=ly)fa[lx]=ly;

			}

		}

	for(rint i=1;i<=k;++i)

	{

		if(p[i].y<2*x)

		{

			int lx=find(0),ly=find(i);

			if(lx!=ly)fa[lx]=ly;

		}

		if(p[i].y+2*x>m)

		{

			int lx=find(k+1),ly=find(i);

			if(lx!=ly)fa[lx]=ly;

		}

	}

	return find(0)!=find(k+1);

}

signed main()

{

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

	for(rint i=1;i<=k;++i)

		scanf("%lld %lld",&p[i].x,&p[i].y);

	for(rint i=1;i<=k;++i)

		for(rint j=1;j<=k;++j)

		{

			if(i==j)continue;

			int dis=dist(i,j);

			if(p[j].x<=p[i].x&&p[j].y<=p[i].y)

				yh[i][0]=(dis<dist(yh[i][0],i))?j:yh[i][0];

			if(p[j].x>=p[i].x&&p[j].y<=p[i].y)

				yh[i][1]=(dis<dist(yh[i][1],i))?j:yh[i][1];

			if(p[j].x>=p[i].x&&p[j].y>=p[i].y)

				yh[i][2]=(dis<dist(yh[i][2],i))?j:yh[i][2];

			if(p[j].x<=p[i].x&&p[j].y>=p[i].y)

				yh[i][3]=(dis<dist(yh[i][3],i))?j:yh[i][3];

		}

	double l=1,r=1e6,mid;

	while(r-l>1e-11)

	{

		mid=(l+r)/2;

		if(check(mid))l=mid;

		else r=mid;

	}

	printf("%.8lf\n",mid);

	return 0;

}

当然这样有可能被卡，所以上我们的正解：最小生成树

我们发现上面的题解可以转化为一个最小生成树，答案就是树上的最大边权

kruskal会炸内存，这时就看出prim在稠密图上的作用了：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define MAXN 6005

#define inf 0x7ffffffffffffff

using namespace std;

int n,m,k;

double x[MAXN],y[MAXN],dis[MAXN],ans=0;

bool vis[MAXN];

double max(double a,double b){

	return a>b?a:b;

}

double get_dis(int i,int j){

	if(i>k||j>k) return sqrt((y[i]-y[j])*(y[i]-y[j]));

	return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));

}

void prim(int x){

	for(int i=1;i<=k+2;i++)

		dis[i]=inf;

	dis[x]=0;

	for(int i=1;i<=k+2;i++){

		double minn=inf;

		int p=0;

		for(int j=1;j<=k+2;j++){

			if(dis[j]<minn&&!vis[j]){

				minn=dis[j];

				p=j;

			}

		}

		ans=max(ans,dis[p]);

		if(p==k+2) break;

		vis[p]=1;

		for(int j=1;j<=k+2;j++){

			if(dis[j]>get_dis(p,j))

			    dis[j]=get_dis(p,j);

		}

	}

}

int main(){

	scanf("%d%d%d",&n,&m,&k);

	for(int i=1;i<=k;i++)

		scanf("%lf%lf",&x[i],&y[i]);

	x[k+1]=y[k+1]=0,x[k+2]=0,y[k+2]=m;

	prim(k+1);

	printf("%0.9lf\n",ans/2.0);

	return 0;

}

B：God Knows

先咕了

C:Lost My Music

凸包？这个确实是一个凸包

我们观察这个式子：设$dep[i]$表示i的深度，那么式子可以写成：$-\frac{c[u]-c[v]}{dep[u]-dep[v]}$

就是斜率的形式，所以维护凸包。

如果是单纯的序列，那么非常好做，但是这是在树上，有父子关系，所以比较麻烦

我们需要维护一个可持久化栈，维护凸包，

每次暴力弹栈显然会TLE，所以我们用到倍增

其实并不需要真正搞出来一个栈，只需要用倍增维护当前节点前2ⁱ的栈的元素即可

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<queue>

#define ForzaJuve return 0

using namespace std;

const int MAXN=5e5+5;

int n,c[MAXN],fa[MAXN];

vector<int>son[MAXN];

int dep[MAXN],f[MAXN][21];

double ans[MAXN];

queue<int>q;

double calc(int i,int j){

	return (double)(c[i]-c[j])/(dep[i]-dep[j]);

}

int main(){

	scanf("%d",&n);

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

		scanf("%d",&c[i]);

	for(int i=2;i<=n;i++){

		scanf("%d",&fa[i]);

		son[fa[i]].push_back(i);

	}

	dep[1]=1;

	for(int i=1;i<=n;i++){

		int N=son[i].size();

		for(int j=0;j<N;j++)

			dep[son[i][j]]=dep[i]+1;

	}

	q.push(1);

	while(!q.empty()){

		int x=q.front();q.pop();

		int N=son[x].size();

		for(int i=0;i<N;i++)

			q.push(son[x][i]);

		if(x<=1) continue;

		int y=fa[x];

		for(int i=18;i>=0;i--){

			if(f[y][i]<=1) continue;

			if(calc(x,f[y][i])<=calc(x,f[f[y][i]][0]))

				y=f[f[y][i]][0];

		}

		if(y>1&&calc(x,y)<=calc(x,f[y][0]))

			y=f[y][0];

		f[x][0]=y;

		ans[x]=-calc(x,y);

		for(int i=1;i<=18;i++)

			f[x][i]=f[f[x][i-1]][i-1];

	}

	for(int i=2;i<=n;i++)

		printf("%.9lf\n",ans[i]);

	ForzaJuve;

}

巴特西

HZOI20190817模拟24

最新文章

热门文章