2022 牛客多校第三场 部分题解

比赛链接：

C题 Concatenation （贪心，排序）

给定 $nn$ 个仅包含 0-4 的字符串，问怎么将他们拼接起来，使得最后得到的字符串，其转换成数字的值最大？

$n\le 2\ast 10^6,\sum \mathrm{\mid }s\mathrm{\mid }\le 2\ast 10^{7}n\backslash leq\; 2*10^6,\backslash sum|s|\backslash leq\; 2*10^7$

出题人在题面里面刻意说了他卡了排序的做法，只允许线性的算法过，结果全场都是直接排序一遍秒，我还是 40 分钟的时候看了下群才发现，直接丢了半小时罚时。

关于排序可以参照 P1012 [NOIP1998 提高组] 拼数，也就是写一个如下的比较函数：

bool cmp(string &a, string &b) {
    return a + b > b + a;
}

以前感觉这个挺玄学的，今天比赛完了才清楚他的具体原理（第一行是字符串形式，后面就是纯数字了）：

这题排序的话有点卡常， cmp 要传引用，然后开一下读入优化啥的。

#include<bits/stdc++.h>
using namespace std;
vector<string> vec;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        string s;
        cin >> s;
        vec.push_back(s);
    }
    sort(vec.begin(), vec.end(), [](string &a, string &b) {
        return a + b < b + a;
    });
    for (auto &s : vec) cout << s;
    return 0;
}

优化到线性的话得用一下花里胡哨的，例如 Trie, 链表啥的，感兴趣看官方题解，或者去找耗时最少的代码康康。

A题 Ancestor（LCA，前缀和/ST表）

给定两棵节点数量为 $nn$ 的树（根为 1），每棵树的点都有自己对应的权值，分别是 $\{a_n\},\{b_n\}\backslash \{a\_n\backslash \},\backslash \{b\_n\backslash \}$。

现在给定一个集合 $S=\{x_k\}S=\backslash \{x\_k\backslash \}$，要求从中恰好删除一个点，然后第一棵树中的 $\mathrm{lca}(S)=s\backslash operatorname\{lca\}(S)=s$，第二棵树中的 $\mathrm{lca}(S)=t\backslash operatorname\{lca\}(S)=t$，并使得 $a_s>b_{t}a\_s>b\_t$，求方案数。

$2\le k\le n\le 10^5,1\le a_i,b_i\le 10^{9}2\backslash leq\; k\backslash leq\; n\backslash leq\; 10^5,1\backslash leq\; a\_i,b\_i\backslash leq\; 10^9$

暴力（求 LCA 用倍增，集合 LCA 直接一个个并）的复杂度是 $O(kn\log n)O(kn\backslash log\; n)$，显然是不可接受的。

我们注意到 $\mathrm{lca}(S\text{or}T)=\mathrm{lca}(\mathrm{lca}(S),\mathrm{lca}(T))\backslash operatorname\{lca\}(S\backslash or\; T)=\backslash operatorname\{lca\}(\backslash operatorname\{lca\}(S),\backslash operatorname\{lca\}(T))$，这也正是前面累计的原因。那么，我们能不能想办法优化一下，将一些常用的结果给累积起来，减少重复计算呢？

我想到了对于 $k=8k=8$ 的策略：先依次算出 $(1,2),(3,4),(5,6),(7,8)(1,2),(3,4),(5,6),(7,8)$，然后根据 $(1,2),(3,4)(1,2),(3,4)$ 得到 $(1,4)(1,4)$（同理得到 $(5,8)(5,8)$），十分类似归并排序，最后和并得到 $(1,8)(1,8)$。这样每次求 LCA 时候，只要找到对应的 $O(\log k)O(\backslash log\; k)$ 个区间即可。

直到我晚上写这个题解的时候，才想起来这就是线段树（区间信息可并），我下午直接奔着 ST 表去了（其实也一样）。

不过，实际上也没那么复杂：如果删除 $x_{i}x\_i$，那么我们只需要查询 $[1,i-1][1,i-1]$ 上的 LCA 和 $[i+1,k][i+1,k]$ 上的 LCA，然后对他们再求一次 LCA 即可，而这两个都是经典的前缀后缀查询，直接前缀和走起。

查到了 LCA 后，直接比较就行了，复杂度 $O((n+k)\log n)O((n+k)\backslash log\; n)$。

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int lg[N];
int n, k, x[N];
struct Tree {
    int a[N];
    vector<int> G[N];
    void read() {
        for (int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        for (int i = 2, f; i <= n; ++i) {
            scanf("%d", &f);
            G[i].push_back(f), G[f].push_back(i);
        }
    }
    //LCA
    //这题里面，lg数组是定义在外面的
    //但我复制板子的时候一并搞过来了，导致了3发罚时和半小时debug
    //鬼知道样例是咋过的
    int depth[N], fa[N][20];
    void dfs(int x, int f) {
        depth[x] = depth[f] + 1;
        fa[x][0] = f;
        for (int i = 1; (1 << i) <= depth[x]; i++)
            fa[x][i] = fa[fa[x][i - 1]][i - 1];
        for (int y : G[x])
            if (y != f) dfs(y, x);
    }
    int lca(int x, int y) {
        if (depth[x] < depth[y]) swap(x, y);
        while (depth[x] > depth[y])
            x = fa[x][lg[depth[x] - depth[y]]];
        if (x == y) return x;
        for (int t = lg[depth[x]]; t >= 0; t--)
            if (fa[x][t] != fa[y][t])
                x = fa[x][t], y = fa[y][t];
        return fa[x][0];
    }
    //Pre & Suf
    int pre[N], suf[N];
    void Pre_build() {
        pre[1] = x[1];
        for (int i = 2; i <= k; ++i)
            pre[i] = lca(pre[i - 1], x[i]);
        suf[k] = x[k];
        for (int i = k - 1; i >= 1; --i)
            suf[i] = lca(suf[i + 1], x[i]);
    }
    int query(int i) {
        if (i == 1) return suf[2];
        if (i == k) return pre[k - 1];
        return lca(pre[i - 1], suf[i + 1]);
    }
    void build() { read(); dfs(1, 0); Pre_build(); }
} A, B;
int main()
{
    lg[1] = 0;
    for (int i = 2; i < N; ++i) lg[i] = lg[i / 2] + 1;
    //read & build
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= k; ++i)
        scanf("%d", &x[i]);
    //solve
    A.build(), B.build();
    int ans = 0;
    for (int i = 1; i <= k; ++i)
        if (A.a[A.query(i)] > B.a[B.query(i)]) ++ans;
    printf("%d\n", ans);
    return 0;
}

J题 Journey（建模，最短路/01 BFS）

不想概括了，建议直接读题面。

这题的建模十分鸡贼：要求从某条道路到某条道路，而且还必须指定方向，那么每条边必须拆成两个点（例如 $a,ba,b$ 点之间的这条边，就得拆成 两个点）。直接 pair 映射到 map 里面的话复杂度太大，还是化成 long long 后存 unordered_map 里面靠谱。

接着，就是点和点之间的转移关系了。假定第 $ii$ 行里面给定了 $ii$ 和 $a,b,c,da,b,c,d$ 四个点相连，而 $a,b,c,da,b,c,d$ 按照逆时针排序，那么就有：

1. 可以向 连边，边权为 0（右转），同理 向 连边权为 1 的边
2. 向 连边权为 1 的边（掉头），同理， 也向 连一下
3. 向 连边权为 1 的边（直行），同理， 也向 连一下
4. 向 连边权为 1 的边（左转），其实不用，因为当 开始连右转边的时候会把这个加上

总的来说，就是考虑各种情况，把所有可能出现的边都加进来。实际上方法有很多，而且经常重复，所以边的数组要开大一些。

这里给出我比赛时候想出来的构造方式，和上面的思路一致（另外一种简单的放在最后的总体代码里面）：

for (int i = 1; i <= n; ++i) {
    int a[4];
    for (int j = 0; j < 4; ++j) {
        scanf("%d", &a[j]);
        if (a[j]) {
            LL A = ff(a[j], i), B = ff(i, a[j]);
            if (!vis[A]) vis[A] = ++cnt;
            if (!vis[B]) vis[B] = ++cnt;
        }
    }
    for (int j = 0; j < 4; ++j) {
        if (a[j] == 0) continue;
        addEdge(gg(a[j], i), gg(i, a[j]), 1);
        addEdge(gg(i, a[j]), gg(a[j], i), 1);
    }
    for (int j = 0; j < 4; ++j) {
        int x = a[j], y = a[(j + 1) % 4];
        if (x && y) {
            addEdge(gg(x, i), gg(i, y), 0);
            addEdge(gg(y, i), gg(i, x), 1);
        }
    }
    for (int j = 0; j < 4; ++j) {
        int x = a[j], y = a[(j + 2) % 4];
        if (x && y) {
            addEdge(gg(x, i), gg(i, y), 1);
            addEdge(gg(y, i), gg(i, x), 1);
        }
    }
}

建立好了边，接下来就是跑最短路了。考虑到点的规模是 $4\ast 10^{6}4*10^6$ 的级别，边可能直接奔着千万去了，所以最好别用朴素的最短路算法，而是使用 01 BFS 来处理（不过出题人给的空间和时间都相当宽容，所以 Dijkstra 能 AC，不过 SPFA TLE了，虽然出题人说他没有刻意去卡）。

01 BFS 是普通广搜的变形，当碰到边权为 0 的情况，就把点塞到队头，反正塞入队尾，保证了决策正确性。很遗憾，比赛的时候，我搁那边调了将近 40 分钟的代码都没能 A（一份自己写的，一份网上找的板子，居然都有问题，麻了）。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn = 500010;
int n, s, t;
//
int cnt;
unordered_map<LL, int> vis;
//
const int N = maxn << 3, M = maxn << 6;
int tot = 0;
int Head[N], ver[M], edge[M], Next[M];
void addEdge(int x, int y, int v) {
    ver[++tot] = y, edge[tot] = v;
    Next[tot] = Head[x], Head[x] = tot;
}
inline LL ff(LL x, LL y) { return x * n + y; }
inline int gg(int x, int y) { return vis[ff(x, y)]; }
void getST() {
    int a, b, c, d;
    scanf("%d%d%d%d", &a, &b, &c, &d);
    s = gg(a, b), t = gg(c, d);
}
//
int dis[N], visit[N];
deque<int> q;
int solve() {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0, q.push_back(s);
    while (!q.empty()) {
        int x = q.front(); q.pop_front();
        if (visit[x]) continue;
        visit[x] = 1;
        for (int i = Head[x]; i; i = Next[i]) {
            int y = ver[i], v = edge[i];
            if (dis[y] > dis[x] + v) {
                dis[y] = dis[x] + v;
                if (v) q.push_back(y);
                else q.push_front(y);
            }
        }
    }
    return dis[t] == 0x3f3f3f3f ? -1 : dis[t];
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        int a[4];
        for (int j = 0; j < 4; ++j) {
            scanf("%d", &a[j]);
            if (a[j]) {
                LL A = ff(a[j], i), B = ff(i, a[j]);
                if (!vis[A]) vis[A] = ++cnt;
                if (!vis[B]) vis[B] = ++cnt;
            }
        }
        for (int j = 0; j < 4; ++j) {
            if (a[j] == 0) continue;
            int u = a[j];
            for (int k = 0; k < 4; ++k) {
                int v = a[(j + k) % 4];
                if (!v) continue;
                addEdge(gg(u, i), gg(i, v), k != 1);
            }
        }
    }
    getST();
    printf("%d\n", solve());
    return 0;
}