2022牛客暑期多校训练营3(总结+补题)

总结：

好消息：队伍过了4题rk100出头；

坏消息：我过了0题。

题解：

A - Ancestor

题意：

给你两棵以 $1$ 为根的 $n$ 个点的树 $a,b$ ，$a,b$ 树中的每个点都有一个点权，再给你 $m$ 个点 $c_i(1\le i\le n)$ ，问：每次从 $a$ 树和 $b$ 树中删除一个 $m$ 个点中的点 $c_i$ ，问 $a,b$ 树剩余 $m-1$ 个点中公共祖先的点权满足 $a>b$ 的数量是多少。

做法：

对于点集 $c$ ,我们可以分别对 $a$ 树和 $b$ 树中的点集 $c$ 做一次前缀 $lca$ 以及后缀 $lca$ ，对于每个 $c_i$ ，我们只需要判断 $a[lca(prea[i-1],sufa[i+1])]$ 是否大于 $b[lca(preb[i-1],sufb[i+1])]$ ，是则 $ans$++ ，最后输出答案即可。

代码：

/*
 author:wuzx
 */

#include
#define ll long long
#define int long long
#define endl "\n"
#define P pair<int,int>
#define f first
#define s second
using namespace std;
const int inf = 0x3f3f3f3f;
int t;
int n,m,k;
struct slpf{
    const int nn;
    vector<int> fa,dep,son,siz,top,dfn,w;
    vector<int> v;
    vector<vector<int>> g;
    int tim;
    slpf(int n1):nn(n1),fa(n1+1),dep(n1+1),son(n1+1,0),siz(n1+1),top(n1+1),dfn(n1+1),w(n1+1),v(n1+1),g(n1+1),tim(0){}
    void add(int uu,int vv)
    {
        g[uu].push_back(vv);
    }
    void dfs1(int now,int fr)
    {
        fa[now]=fr;
        dep[now]=dep[fr]+1;
        siz[now]=1;
        int max_size=-1;
        for(int x:g[now])
        {
            if(x==fr)
                continue;
            dfs1(x,now);
            siz[now]+=siz[x];
            if(siz[x]>max_size)
            {
                max_size=siz[x];
                son[now]=x;
            }
        }
    }
    void dfs2(int now,int tp)
    {
        dfn[now]=++tim;
        top[now]=tp;
        w[tim]=v[now];
        if(!son[now])
            return;
        dfs2(son[now],tp);
        for(int x:g[now])
        {
            if(x==fa[now]||x==son[now])
                continue;
            dfs2(x,x);
        }
    }
    void make_tree(int root,vector<int> &arr)
    {
        v=arr;
        dfs1(root,root);
        dfs2(root,root);
        // build(1,1,nn);
    }
    int lca(int x,int y)
    {
        while(top[x]!=top[y])
        {
            if(dep[top[x]]>=dep[top[y]])
                x=fa[top[x]];
            else
                y=fa[top[y]];
        }
        return dep[x]<dep[y]?x:y;
    }
};
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    vector<int> c(m+2);
    vector<int> a(n+1),b(n+1);
    for(int i=1;i<=m;i++)
        cin>>c[i];
    slpf tr1(n),tr2(n);
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=2;i<=n;i++)
    {
        cin>>k;
        tr1.add(k,i);
    }
    for(int i=1;i<=n;i++)
        cin>>b[i];
    for(int i=2;i<=n;i++)
    {
        cin>>k;
        tr2.add(k,i);
    }
    tr1.make_tree(1,a);
    tr2.make_tree(1,b);
    vector<int> pre1(m+1),pre2(m+1);
    vector<int> suf1(m+1),suf2(m+1);
    pre1[1]=pre2[1]=c[1];
    suf1[m]=suf2[m]=c[m];
    for(int i=2;i<=m;i++)
    {
        pre1[i]=tr1.lca(pre1[i-1],c[i]);
        pre2[i]=tr2.lca(pre2[i-1],c[i]);
    }
    for(int i=m-1;i>=1;i--)
    {
        suf1[i]=tr1.lca(suf1[i+1],c[i]);
        suf2[i]=tr2.lca(suf2[i+1],c[i]);
    }
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        if(i==1)
        {
            if(a[suf1[i+1]]>b[suf2[i+1]])
                ans++;
        }
        else if(i==m)
        {
            if(a[pre1[i-1]]>b[pre2[i-1]])
                ans++;
        }
        else
        {
            if(a[tr1.lca(pre1[i-1],suf1[i+1])]>b[tr2.lca(pre2[i-1],suf2[i+1])])
                ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

C - Concatenation

题意：

给你 $n$ 个字符串，要求你把 $n$ 个字符串按字典序最小的方式连接起来并输出.

做法：

手写 $cmp$ 函数，排序后输出即可.

代码：

/*
 author:wuzx
 */

#include
#define ll long long
#define int long long
#define endl "\n"
#define P pair<int,int>
#define f first
#define s second
using namespace std;
const int inf = 0x3f3f3f3f;
int t;
int n,m,k;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    vector<string> a(n);
    for(auto &x:a)
        cin>>x;
    auto cmp = [&](string& aa,string bb)   
    {
        return aa+bb<bb+aa;
    };
    sort(a.begin(),a.end(),cmp);
    for(auto x:a)
        cout<<x;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32