这次考试，难度还是不小的，先说一下考试过程，首先看一遍题，觉得开题顺序1 3 2，
然后我就先打了第一题，我当时可能是受到之前做题的限制了，觉得他只能每次走一
格，也就是一个单位长度，但是实际上，他甚至可以走一个曲线，因为题面并没有规定
必须走直线，或者必须走一个单位长度。我当时打了一个dfs，虽然没看懂题面，但还是
得到了10分。用了大概一个小时。然后是T3，暴力思路很简单，就是枚举每个点，然后
一直往上跳到根节点，输出最大值即可。最后是T2，我觉得这是个DP，但是我当时无法
保证正确性，因为应该是求最长的单调上升的序列，没什么思路，我就打了个dfs，
总体来说，这次是暴力分基本上打满了，这次考试的几道题我觉得都非常棒，可以很
好的拓展思路，还可以学到一些常见套路。
题解
T1
这道题思路真是......难以形容，假设我们把所有点连起来，再把上下边界分别看成一个
点，那么我们就可以得到一条线，我们到终点的路径必定会经过这条线上的一条，那么
我们要求得是最小的最大值，就可以利用最小生成树，最后输出最大的边的长度除以2即可
#include<bits/stdc++.h>
#define re register int
#define lc rt<<1
#define rc rt<<1|1
#define mid ((l+r)>>1)
using namespace std;
const int N=6100;
struct CUN
{
int x,y;
}use[N];
int n,m,k,cnt;
double maxx;
double d[N];
bool vis[N];
inline int read()
{
int x=0;
bool f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch^'-')
f=0;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return f?x:(-x);
}
inline double gett(int x,int y)
{
return (double)sqrt((((double)(use[x].x-use[y].x)*(use[x].x-use[y].x))+((double)(use[x].y-use[y].y)*(use[x].y-use[y].y))));
}
inline void pm()
{
cnt=k+1;
for(re i=1;i<cnt;i++)
d[i]=(double)use[i].y;
d[cnt]=(double)m;
for(re i=1;i<=cnt;i++)
{
int u=0;
for(re j=1;j<=cnt;j++)
{
if((!vis[j])&&(u==0||d[j]<d[u]))
u=j;
}
vis[u]=1;
maxx=max(maxx,d[u]);
if(u==cnt)
{
printf("%.10lf\n",maxx/2);
return;
}
for(re y=1;y<cnt;y++)
{
if(!vis[y])
d[y]=min(d[y],gett(u,y));
}
d[cnt]=min(d[cnt],(double)m-(double)use[u].y);
}
}
int main()
{
n=read();
m=read();
k=read();
for(re i=1;i<=k;i++)
{
use[i].x=read();
use[i].y=read();
}
pm();
return 0;
}
T2
我觉得这道题应该是最有思维含量的一道题了
首先说一个n^2的dp,（题解说了几句废话，还不如不看....）我们令 f[i] 表示，以 i 为
结尾的最长上升序列的最小权值，显然\(f_i=\min(f_i,f_j+c_j)\) , 但是，为了保证这是一
个极长的序列，我们就要利用一个 last 标记，这个没办法解释的很清楚，具体实
现看代码片段
for(int i=1;i<=n;i++)
s[i]=read();
for(int i=1;i<=n;i++)
val[i]=read();
las=INF;
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++)
if(las>s[i])
{
las=s[i];
f[i]=val[i];
}
for(int i=2;i<=n;i++)
{
int las=0;
for(int j=i-1;j>=1;j--)
if(s[j]<s[i]&&las<s[j])
{
f[i]=min(f[i],f[j]+val[i]);
las=s[j];
}
}
las=0;
for(int i=n;i>=1;i--)
{
if(s[i]<las) continue;
las=s[i];
ans=min(ans,f[i]);
}
printf("%lld",ans);
应该不难理解，好的，接下来我们就看这个线段树优化（我当时理解了好长时间），
大概说一下，线段树下标表示对岸的位置，权值存的是以对面那个点为结尾的极长上
升序列的dp值，mx表示当前区间内极长上升序列的最靠右的端点，加上代码注释应
该比较好理解
#include<bits/stdc++.h>
#define re register int
#define lc rt<<1
#define rc rt<<1|1
#define mid ((l+r)>>1)
using namespace std;
const int N=2e5+10;
const int INF=1e9+1;
int n,las,v;
int p[N],c[N],dp[N<<4],vl[N<<4],mx[N<<4];
struct Segment_tree
{
inline int ask(int rt,int l,int r,int la)
{
if(l==r)
return (mx[rt]>la)?dp[rt]:INF;
if(mx[rc]<=la)
return ask(lc,l,mid,la);
return min(vl[rt],ask(rc,mid+1,r,la));
}
inline void insert(int rt,int l,int r,int p,int pos,int w)
{
if(l==r)
{
dp[rt]=w; //dp是当前点的dp值
mx[rt]=pos;// mx 是当前点的最长上升序列的最小权的最右边的端点
return;
}
if(p>mid)
insert(rc,mid+1,r,p,pos,w);
else
insert(lc,l,mid,p,pos,w);
mx[rt]=max(mx[lc],mx[rc]);
vl[rt]=ask(lc,l,mid,mx[rc]); // vl 存储左区间的值
}
inline void query(int rt,int l,int r,int p)
{
if(p>=r)
{
v=min(v,ask(rt,l,r,las));
las=max(las,mx[rt]);//las不停往上跳，相当与 n^2 dp 里的last
return;
}
if(p>mid)
query(rc,mid+1,r,p);
query(lc,l,mid,p);
}
}T;
int main()
{
scanf("%d",&n);
for(re i=1;i<=n;i++)
scanf("%d",&p[i]);
for(re i=1;i<=n;i++)
scanf("%d",&c[i]);
for(re i=1;i<=n;i++)
vl[i]=INF;
for(re i=1;i<=n;i++)
{
las=0;
v=INF;
T.query(1,1,n,p[i]);
T.insert(1,1,n,p[i],i,((v<INF)?v:0)+c[i]);//更新值
}
v=INF,las=0;
T.query(1,1,n,n);
printf("%d\n",v);
return 0;
}
T3
好吧，这种存在上下比值的问题一般可以转化成斜率，就像本题,
\(\dfrac{c_v-c_u}{deep_u-deep_v}\),可以转化为 \(-\dfrac{c_v-c_u}{deep_v-deep_u}\)
这个可以看作斜率的形式，所以我们要求原式的最小值就是求斜率的最大值，这东西可以用一个倍增数组来实现，我们更新答案的同时修改父亲，具体实现见代码
#include<bits/stdc++.h>
#define re register int
#define lc rt<<1
#define rc rt<<1|1
#define mid ((l+r)>>1)
#define re register int
#define ii inline int
#define iv inline void
using namespace std;
const int N=5e5+10;
int t,n,m,tot,timi;
int fa[N],f[N][30],c[N];
int head[N],to[N<<1],next[N<<1],deep[N];
ii read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=0;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return (f)?x:(-x);
}
iv add(int x,int y)
{
to[++tot]=y;
next[tot]=head[x];
head[x]=tot;
}
inline bool pd(int k,int j,int i)
{
return 1ll*(c[i]-c[k])*(deep[i]-deep[j])>=1ll*(c[i]-c[j])*(deep[i]-deep[k]);
}
iv dfs(int st)
{
///cout<<"st="<<st<<endl;
deep[st]=deep[fa[st]]+1;
int x=fa[st],t;
for(re i=22;i>=0;i--)
{
t=f[x][i];
if(t<2)
continue;
if(pd(f[t][0],t,st))
x=t;
}
if(x!=1&&pd(f[x][0],x,st))
x=f[x][0];
f[st][0]=x;
for(re i=1;i<=22;i++)
f[st][i]=f[f[st][i-1]][i-1];
for(re i=head[st];i;i=next[i])
dfs(to[i]);
}
int main()
{
n=read();
for(re i=1;i<=n;i++)
c[i]=read();
for(re i=2;i<=n;i++)
{
fa[i]=read();
add(fa[i],i);
}
dfs(1);
for(re i=2;i<=n;i++)
printf("%.10lf\n",(double)(c[f[i][0]]-c[i])/(double)(deep[i]-deep[f[i][0]]));
return 0;
}