2022牛客多校第三场

C Concatenation

题意：

给定 n 个仅包含 0，1，2，3，4的字符串，问怎么将他们拼接起来，使得最后得到的字符串，字典序最小。

思路：

出题人在题面里面刻意说了他卡了排序的做法，只允许线性的算法过。但最后用sort,再加了读入的优化就可以过了。

代码：

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

A Ancestor

题意：

给你两棵树A和B，点的编号从1到n，根结点是1,且每个点都有一个权重，现在给你k个点，删掉其中一点，分别求剩下的点在两棵树上的最近公共祖先fa, fb，问存在多少种情况满足A树上fa的价值大于B树上fb的价值。

思路： 用倍增的方法求lca，删掉一点的lca，那么我们只需要查询 [1,i−1]上的 lca 和 [i+1,k] 上的 lca，然后对他们再求一次 lca 即可，用前缀和即可。

代码

#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);
        }
    }
  
    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;
    
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= k; ++i)
        scanf("%d", &x[i]);
    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;
}