A Ancestor

题目大意

给定两颗根节点均为 $1$ 的树 $A, B$ 以及每个点的权值，对于一个包含 $k$ 个点的序列，求在序列中选取恰好一个点，除去该点剩下的点在 $A$ 上的 $l c a$ 的权值严格大于下的点在 $B$ 上的 $l c a$ 的权值

解题思路

Solution 1

由于只需要选取恰好一个点删除，考虑枚举要删除的点，然后求出剩下的点的 $l c a$ 。

通过 $l c a$ 的性质我们不难看出，设当前枚举到的点为 $k e y_{i}$ ，那么剩下的点的 $l c a$ 就是 $lca(lca(key_1,\;key_2, …,\;key_{i - 1}),\; lca(key_{i + 1},\;key_{i + 2}, …,\;key_k))$

这里两项，一项是 $k e y [1, i - 1]$ 的 $l c a$ ，一项是 $k e y [i + 1, k]$ 的 $l c a$ 。很显然的，可以想到前缀 $l c a$ 和 后缀 $l c a$ 。

设 $p r e_{i}$ 表示 $k e y [1, i]$ 的 $l c a$ ， $l s t_{i}$ 表示 $k e y [i, k]$ 的 $l c a$ ，则若当前点为 $k e y_{i}$ ，则剩余点的 $l c a$ 为 $lca(pre_{i - 1}, nxt{i + 1})$ 。

注意特判 $i = 1$ 和 $i = k$ 的情况。

Solution 2

通过观察可以发现，只有删除其中的某两个点才可能会对整体的 $l c a$ 产生影响。这两个点是 $l c a$ 深度最小的点。

显然，由于其他点对的 $l c a$ 的深度小于等于它们的 $l c a$ 的深度，所以只要它们还存在， $l c a$ 就不会改变。

因此，我们可以求出这两个点，讨论删除其中某一个和不删除的情况即可。

这两个点的求法可以 $O (n)$ 完成。

AC 代码

这题并不是我负责，所以没有考场 AC 代码。考后只写了 Solution 1 的代码：

#include<bits/stdc++.h>
#define MAXN 200010
using namespace std;
struct edge{
    int pre, to;
};
edge e[MAXN << 1];
int n, k, cnt, ans;
int fa[MAXN][20], deep[MAXN], head[MAXN], val[MAXN], key[MAXN], pre_lca[MAXN][2], lst_lca[MAXN][2];
bool vis[MAXN];
void add_edge(int u, int v){
    e[++cnt].pre = head[u];
    e[cnt].to = v;
    head[u] = cnt;
}
void bfs(int st){
    queue<int> q; q.push(st);
    vis[st] = true; deep[st] = 1;
    while(!q.empty()){
        int now = q.front(); q.pop();
        for(int i = head[now]; i; i = e[i].pre){
            if(!vis[e[i].to]){
                deep[e[i].to] = deep[now] + 1;
                if(!vis[e[i].to]){
                    vis[e[i].to] = true;
                    q.push(e[i].to);
                }
            }
        }
    }
}
void pre_work(){
    for(int j = 1; j <= 18; j++){
        for(int i = 1; i <= n; i++){
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
            fa[i + n][j] = fa[fa[i + n][j - 1]][j - 1];
        }
    }
}
int get_lca(int u, int v){
    if(deep[u] > deep[v]) swap(u, v);
    int lg = log2(deep[v] - deep[u]);
    for(int i = lg; i >= 0; i--){
        if(deep[fa[v][i]] >= deep[u]){
            v = fa[v][i];
            if(deep[v] == deep[u]) break;
        }
    }
    if(u == v) return u;
    lg = log2(deep[u]);
    for(int i = lg; i >= 0; i--){
        if(fa[v][i] != fa[u][i]){
            v = fa[v][i];
            u = fa[u][i];
        }
    }
    return fa[v][0];
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i = 1; i <= k; i++) scanf("%d",&key[i]);
    for(int i = 1; i <= n; i++) scanf("%d",&val[i]);
    for(int i = 2; i <= n; i++){
        scanf("%d",&fa[i][0]);
        add_edge(fa[i][0], i);
    }
    for(int i = 1; i <= n; i++) scanf("%d",&val[i + n]);
    for(int i = 2; i <= n; i++){
        scanf("%d",&fa[i + n][0]); fa[i + n][0] += n;
        add_edge(fa[i + n][0], i + n);
    }
    bfs(1); bfs(n + 1); pre_work();
    pre_lca[1][0] = key[1]; pre_lca[1][1] = key[1] + n;
    for(int i = 2; i <= k; i++){
        pre_lca[i][0] = get_lca(pre_lca[i - 1][0], key[i]);
        pre_lca[i][1] = get_lca(pre_lca[i - 1][1], key[i] + n);
    }
    lst_lca[k][0] = key[k]; lst_lca[k][1] = key[k] + n;
    for(int i = k - 1; i >= 1; i--){
        lst_lca[i][0] = get_lca(lst_lca[i + 1][0], key[i]);
        lst_lca[i][1] = get_lca(lst_lca[i + 1][1], key[i] + n);
    }
    for(int i = 2; i < k; i++){
        int lca1 = get_lca(pre_lca[i - 1][0], lst_lca[i + 1][0]);
        int lca2 = get_lca(pre_lca[i - 1][1], lst_lca[i + 1][1]);
        if(val[lca1] > val[lca2]) ans++;
    }
    if(val[lst_lca[2][0]] > val[lst_lca[2][1]]) ans++;
    if(val[pre_lca[k - 1][0]] > val[pre_lca[k - 1][1]]) ans++;
    printf("%d\n",ans);
    return 0;
}

Solution 2 代码参见同队另一人的博客，这是他考场 AC 思路。

C Concatenation

题目大意

给定 $n$ 个字符串，把它们按照一定顺序拼接在一起，求拼接后字典序最小的字符串。

解题思路

朴素的想法是把 $n$ 个字符串按照字典序排列，然后从小到大输出。

但是这样是错的，比如样例就过不了，自己推一下应该能够发现原因。

正确的做法依旧是排序，但是排序的比较方式不同：

对于两个字符串 A 和 B，如果 A 后接 B 的字典序比 B 后接 A 的字典序更小，那么就把 A 放在 B 前面。

所以代码就很简单。

什么，你问我证明？这些东西不重要的（~~我是绝对不会告诉你我不会证的）~~

考场 AC 代码

重点：记得关输入流。

#include<bits/stdc++.h>
#define MAXN 2000010
using namespace std;
int n;
string s[MAXN];
bool cmp(string a, string b){
    return (a + b) < (b + a);
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> s[i];
    sort(s + 1, s + n + 1, cmp);
    for(int i = 1; i <= n; i++) cout << s[i];
    cout << endl;
    return 0;
}

F Fief

题目大意

给定一个无向图，每次询问两点x, y，求是否存在一个n的排列，使得第一个元素为x，最后一个元素为y，且排列的任意一个前缀，任意一个后缀都连通。

解题思路

~~像这种题目一看就是缩点之类的说~~

由于我们取出来最后是一个连通块，我们可以让取出来的是两条路径。这样的话，就是让两条路径覆盖这张图上的所有点。

我们让两个人分别再多选一座城，~~作为兄弟交流感情的地方~~，于是我们要求的就成了：

从两个点出发，各找一条路径到达对方，且两条路径没有公共点。

这像什么，是不是像点双联通分量？

只不过，点双连通分量是全称命题，而这里是存在命题。

这种情况，我们考虑把点双连通分量缩成一个点。毕竟不论从这个点双连通分量选那个点，都可以达成上面的条件。

缩点之后，这张图就变成了一棵树，接下来的处理方式就很简单了。想要有这种方案，就一定要满足下面三种情况：

缩点之后是一条链。
A 和 B 初始选的点是链的两端。
A 和 B 初始选的点不是割点。

这样就可以做了。

考场 AC 代码

虽然思路是我想的，但是代码给了同队的人打，代码就没有了。

J Journey

题目大意

给定一个城市有若干十字路口，右转需要等红灯，直行、左转和掉头都需要等红灯，求起点到终点最少等几次红灯

解题思路

这一题其实很简单，将每一条边当作一个节点，重新建图，右转边权为 $0$ ，其他情况边权为 $1$ 。之后在这张新的图上跑 Dijkstra 求最短路就好了。

注意题目中说了，正向的边和反向的边不能当作同一条边。通俗来讲就是不能逆行，所以每一条边会被拆分成两个节点。

题目很良心，直接给了怎么样算作右转，直接套公式就好了

最后，别用 map

考场 AC 代码

#include<bits/stdc++.h>
#define MAXN 500010
#define MAXM 2000010
#define INF 0x3f3f3f3f
using namespace std;
struct edge{
    int pre, to, w;
};
struct node{
    int id, dis;
};
bool operator < (node a, node b){ return a.dis < b.dis; }
bool operator > (node a, node b){ return a.dis > b.dis; }
pair<int, int> a, b, g[MAXM];
edge e[MAXM << 2];
int n, s, t, tot, cnt;
int head[MAXM], dis[MAXM], c[MAXN][5];
bool vis[MAXM];
void add_edge(int u, int v, int w){
    e[++cnt].pre = head[u];
    e[cnt].to = v; e[cnt].w = w;
    head[u] = cnt;
}
void dijkstra(int st){
    memset(dis, 0x3f, sizeof(dis));
    priority_queue<node, vector<node>, greater<node>> q;
    q.push((node){st, 0}); dis[st] = 0;
    while(!q.empty()){
        int now = q.top().id; q.pop();
        if(vis[now]) continue;
        vis[now] = true;
        for(int i = head[now]; i; i = e[i].pre){
            if(dis[e[i].to] > dis[now] + e[i].w){
                dis[e[i].to] = dis[now] + e[i].w;
                if(!vis[e[i].to]) q.push((node){e[i].to, dis[e[i].to]});
            }
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= 4; j++){
            scanf("%d",&c[i][j]);
            if(c[i][j] != 0){
                g[++tot] = make_pair(c[i][j], i);
            }
        }
    }
    sort(g + 1, g + tot + 1);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= 4; j++){
            pair<int, int> e1, e2;
            e1 = make_pair(c[i][j], i); e2 = make_pair(i, c[i][j % 4 + 1]);
            if(c[i][j % 4 + 1] != 0 && c[i][j] != 0){
                int u = lower_bound(g + 1, g + tot + 1, e1) - g, v = lower_bound(g + 1, g + tot + 1, e2) - g;
                add_edge(u, v, 0);
            }
            for(int k = 2; k <= 4; k++){
                int tmp = (j + k) % 4;
                if(tmp == 0) tmp = 4;
                e1 = make_pair(c[i][j], i); e2 = make_pair(i, c[i][tmp]);
                if(c[i][j] == 0 || c[i][tmp] == 0) continue;
                int u = lower_bound(g + 1, g + tot + 1, e1) - g, v = lower_bound(g + 1, g + tot + 1, e2) - g;
                add_edge(u, v, 1);
            }
        }
    }
    scanf("%d%d%d%d",&a.first,&a.second,&b.first,&b.second);
    s = lower_bound(g + 1, g + tot + 1, a) - g; t = lower_bound(g + 1, g + tot, b) - g;
    dijkstra(s);
    if(dis[t] == INF) printf("-1\n");
    else printf("%d\n",dis[t]);
    return 0;
}

"蔚来杯"2022牛客暑期多校训练营题解

A Ancestor

题目大意

解题思路

Solution 1

Solution 2

AC 代码

C Concatenation

题目大意

解题思路

考场 AC 代码

F Fief

题目大意

解题思路

考场 AC 代码

J Journey

题目大意

解题思路

考场 AC 代码