CCPC-Wannafly Winter Camp Day8 (Div2, onsite)

咕咕咕。 camp补题。

传送门：https://www.zhixincode.com/contest/29/problems

A.Aqours

题意：有一棵有根树，根节点为1，给出每个结点的父亲节点。其中根节点是 1 号点。i号结点的父亲为pi。保证1<=pi，而且对于2<=i<j<=n，有pi<=pj。

问对于每一个叶子节点，与编号比他小的叶子结点的最近距离是什么？

分析：根据题意可以将给定的点序列看为BFS序。对于每一个结点u，可以维护一个f[u]代表距离点u的最近叶子结点的距离。

那么，每次遇到一个叶子结点，就暴力向上搜，在搜的过程中，更新f值，直至搜到一个被更新过的结点，即被其他叶子结点搜过的点。

每碰到一个被搜过的点xx，那么对于当前这个叶子节点来说，答案就是f[xx]+搜到xx的步数。

同时还需要在回溯的过程中，更新每个点的距离叶子节点的最短距离。

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e6+10; 
const int inf=0xfffffff;
int outd[maxn],f[maxn],fa[maxn],vis[maxn];
int ff;
int dfs(int xx,int step){
    if (vis[xx]){ff=f[xx]+step;return f[xx]+1;}
    vis[xx]=1; f[xx]=step;
    int tmp=inf;
    if (xx!=1) tmp=dfs(fa[xx],++step);
    f[xx]=min(f[xx],tmp);
    return f[xx]+1;
}
int main(){
    int n,x; scanf("%d",&n);
    memset(outd,0,sizeof(outd));
    for (int i=2;i<=n;i++){
        scanf("%d",&x);
        fa[i]=x;
        outd[x]++;
    }
    for (int i=1;i<=n;i++) vis[i]=0; 
    for (int i=1;i<=n;i++){
        if (outd[i]==0){
            ff=0;
            dfs(i,0);
            if (ff!=0) printf("%d %d
",i,ff);
            else printf("%d -1
",i);
        }
    } 
    return 0;
} 


/*反例： 
10
1 1 1 2 2 2 5 7 8

答案:
3 -1
4 2
6 3
9 3
10 4
*/

A.Aqours

C.御坂妹妹

题意：有n条直线，以y=kx+b的形式给出。求解一个垂直于x轴的线段，要求和这n条直线都有交点。问所求线段的最短距离了是多少。

分析：通过画图，可以观察到，可以维护这n条直线所形成的，一个在直线上方的凸包，一个在直线下方的凸包。答案一定是在所求的凸包点的x值处。

（也不完全是凸包，eg.样例。。类似于凸壳。

题解还有一种做法是：

不是很懂扫描线的操作。（雾

另：（男朋友是神仙.jpg

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=5e5+10;
 4 struct line{
 5     double k,b;
 6 }ll[maxn],sta1[maxn],sta2[maxn];
 7 double st1[maxn],st2[maxn];
 8 int n;
 9 bool cmp1(line p,line q){return p.k<q.k || p.k==q.k && p.b>q.b;}
10 bool cmp2(line p,line q){return p.k>q.k || p.k==q.k && p.b<q.b;}
11 double calc(line l1,line l2){return (l2.b-l1.b)/(l1.k-l2.k);}
12 bool check(line a,line b,line L){
13     if (calc(a,L)<=calc(a,b)) return true;
14     return false;
15 }
16 void solve(line sta[],double st[],int &num){
17     int top=0;
18     for (int i=0;i<n;i++){
19         if (top<1){sta[++top]=ll[i]; continue;}
20         if (ll[i].k==ll[i-1].k) continue;
21         while (top>1 && check(sta[top-1],sta[top],ll[i])) top--;
22         sta[++top]=ll[i];
23     }
24     num=0;
25     for (int i=2;i<=top;i++){
26         double xx=calc(sta[i],sta[i-1]);
27         st[++num]=xx;
28     }
29     st[++num]=1e9;
30 }
31 set<double> aa;
32 int main(){
33     scanf("%d",&n);
34     double max_=-1e9,min_=1e9;
35     for (int i=0;i<n;i++) scanf("%lf%lf",&ll[i].k,&ll[i].b),aa.insert(ll[i].k),
36     max_=max(ll[i].b,max_),min_=min(ll[i].b,min_);
37     if (aa.size()==1) return printf("%.10f
",max_-min_),0; 
38     //
39     sort(ll,ll+n,cmp1); int num1=0;
40     solve(sta1,st1,num1);    
41     //
42     sort(ll,ll+n,cmp2); int num2=0;
43     solve(sta2,st2,num2);
44     
45     double ans=1e20;
46     for (int i=1;i<num1;i++){
47         int xx=upper_bound(st2+1,st2+1+num2,st1[i])-st2;
48         double tmp=fabs(sta1[i].k*st1[i]+sta1[i].b-sta2[xx].k*st1[i]-sta2[xx].b);
49         ans=min(ans,tmp);
50     }
51     for (int i=1;i<num2;i++){
52         int xx=upper_bound(st1+1,st1+1+num1,st2[i])-st1;
53         double tmp=fabs(sta2[i].k*st2[i]+sta2[i].b-sta1[xx].k*st2[i]-sta1[xx].b);
54         ans=min(ans,tmp);
55     }
56     printf("%.10f
",ans);
57     return 0;
58 }

（wa了好多发的题。傻逼错误。我是智障.jpg