大致尝试了一下并查集,记忆化搜索,最小生成树
最小生成树是正解,跑最小生成树然后找到最大的值
prim楞跑
至于为什么跑最小生成树不是跑最大生成树,你跑最大生成树连的边可能会^%$&$%!#
感性理解手膜吧,我理解但说不清楚,稍微手膜就出来了,你可以举出一万种反例
代码实现细节比较多,技巧也比较多
注意边界处理,我们可以以一个边界为0,另一个边界权值为m,比较上下边界时不用再比较横坐标
#include<bits/stdc++.h> using namespace std; #define ll long long #define A 1010010 double cal(ll x1,ll y1,ll x2,ll y2){ return sqrt((double)((x1-x2)*(x1-x2))+(double)((y1-y2)*(y1-y2))); } ll n,m,k; double ans; ll x[A],y[A]; double dis[A]; bool vis[A]; int main(){ scanf("%lld%lld%lld",&n,&m,&k); for(ll i=1;i<=k;i++){ scanf("%lld%lld",&x[i],&y[i]); dis[i]=y[i]; } dis[k+1]=m; while(1){ ll mi=0; for(ll j=1;j<=k+1;j++) if(!vis[j]&&(mi==0||dis[j]<dis[mi])) mi=j; // printf("mi=%lld\n",mi); ans=max(ans,dis[mi]); vis[mi]=1; if(mi==k+1){ printf("%.10lf\n",ans/2); return 0; } for(ll j=1;j<=k;j++) dis[j]=min(dis[j],cal(x[j],y[j],x[mi],y[mi])); dis[k+1]=min(dis[k+1],(double)(m-y[mi])); } }
题目中说的很明显是一个斜率单调栈维护一下
然而这是树上问题,你暴力退栈你会被卡成$n^2$于是我又学习了一下可持久化栈
我用的是二分方法,好理解又好打
大致就是$dfs$时传一个$top$指针,然后你每次找到符合祖先链且斜率最大的地方,每次向下搜时只需要将当前对应位置栈设为$x$然后再回溯
这样我们就可以不用退栈
直接口胡肯定不能理解
| |<---你当前栈顶指向
| |
| |<---符合的位置,你只需要将当前栈指针指向当前,,,,,最后再回溯即可
| |
| |
或者换种方式理解
维护凸包
你若当前可以更新那么赋成当前值斜率更新更大
代码实现
void dfs(ll x,ll pre,ll de,ll top){ deep[x]=de; ll k=get(x,top)+1,t1=sta[k],t2=sta[k-1]; if(x==1) k=1; ans[x]=-1.0*(cal(t2,x)); sta[k]=x; for(ll i=head[x];i;i=nxt[i]){ ll y=ver[i]; if(y==pre) continue; dfs(y,x,de+1,k); } sta[k]=t1; }
#include<bits/stdc++.h> using namespace std; #define ll long long #define A 1010101 ll n,tot; double ans[A]; ll deep[A],head[A],nxt[A],ver[A],c[A],sta[A]; void add(ll x,ll y){ nxt[++tot]=head[x],head[x]=tot,ver[tot]=y; } double cal(ll x,ll y){ return (double)(c[x]-c[y])/(1.0*(double)(deep[x]-deep[y])); } ll get(ll x,ll h){ ll l=2,r=h,mid; double k1,k2; while(l<=r){ mid=(l+r)>>1; k1=-1.0*(cal(sta[mid],sta[mid-1])); k2=-1.0*(cal(x,sta[mid])); if(k1<k2)r=mid-1; else l=mid+1; } return l-1; } void dfs(ll x,ll pre,ll de,ll top){ deep[x]=de; ll k=get(x,top)+1,t1=sta[k],t2=sta[k-1]; if(x==1) k=1; ans[x]=-1.0*(cal(t2,x)); sta[k]=x; for(ll i=head[x];i;i=nxt[i]){ ll y=ver[i]; if(y==pre) continue; dfs(y,x,de+1,k); } sta[k]=t1; } int main(){ scanf("%lld",&n); for(ll i=1;i<=n;i++){ scanf("%lld",&c[i]);//printf("***\n"); } for(ll i=2,a;i<=n;i++){ scanf("%lld",&a); add(a,i); } dfs(1,0,1,0); for(ll i=2;i<=n;i++){ printf("%lf\n",ans[i]); } }
NOIP模拟测试24「star way to hevaen·lost my music」
原文：https://www.cnblogs.com/znsbc-13/p/11370216.html
