比赛链接:
https://ac.nowcoder.com/acm/contest/33188
A.Ancestor
题意:
已知两棵有 \(n\) 个节点的树 \(A\) 和 \(B\),每个节点都有自己对应的权重,有一个长为 \(k\) 的序列 \(x\),表示树中的关键节点,第 \(i\) 轮删除 \(x_i\) 这个关键节点,问 \(A\) 树中剩余关键节点的最近公共祖先的权重是否大于 \(B\) 树种剩余关键节点的最近公共祖先的权重。
思路:
删除了第 \(i\) 个节点,剩余节点的 \(lca\) 其实就是 \(lca(lca(a_1, a_2, ..., a_{i - 1}), lca(a_{i + 1}, ..., a_n))\)。所以先处理所有关键节点的一个前缀的 \(lca\),和一个后缀的 \(lca\),然后比较权重即可。
代码:
#include <bits/stdc++.h> using namespace std; #define LL long long struct Tree{ vector <int> top, son, dep, parent, sz; vector < vector<int> > e; Tree(int n) : top(n + 1), son(n + 1), dep(n + 1), parent(n + 1), sz(n + 1), e(n + 1) {} void add(int u, int v){ e[u].push_back(v); e[v].push_back(u); } void init(int s){ dfs1(s); dfs2(s, s); } void dfs1(int u){ //计算子树大小、深度、父亲和重儿子 sz[u] = 1; dep[u] = dep[parent[u]] + 1; for (auto v : e[u]){ if (v == parent[u]) continue; parent[v] = u; dfs1(v); sz[u] += sz[v]; if (!son[u] || sz[son[u]] < sz[v]){ son[u] = v; } } } void dfs2(int u, int up){ //计算链的头部节点 top[u] = up; if (son[u]) dfs2(son[u], up); for (auto v : e[u]){ if (v == parent[u] || v == son[u]) continue; dfs2(v, v); } } int lca(int u, int v){ while(top[u] != top[v]){ if (dep[top[u]] >= dep[top[v]]){ u = parent[top[u]]; } else{ v = parent[top[v]]; } } return (dep[u] < dep[v] ? u : v); } }; int main(){ ios::sync_with_stdio(false);cin.tie(0); LL n, k; cin >> n >> k; vector <LL> x(k), a(n + 1), b(n + 1); for (int i = 0; i < k; i ++ ) cin >> x[i]; Tree A(n), B(n); for (int i = 1; i <= n; i ++ ) cin >> a[i]; for (int u = 2; u <= n; u ++ ){ LL v; cin >> v; A.add(u, v); } for (int i = 1; i <= n; i ++ ) cin >> b[i]; for (int u = 2; u <= n; u ++ ){ LL v; cin >> v; B.add(u, v); } A.init(1); B.init(1); vector <LL> preA(k), preB(k); for (int i = 0; i < k; i ++ ){ //处理前缀 if (!i){ preA[i] = x[i]; preB[i] = x[i]; } else{ preA[i] = A.lca(preA[i - 1], x[i]); preB[i] = B.lca(preB[i - 1], x[i]); } } vector <LL> sufA(k), sufB(k); for (int i = k - 1; i >= 0; i -- ){ //处理后缀 if (i == k - 1){ sufA[i] = x[i]; sufB[i] = x[i]; } else{ sufA[i] = A.lca(sufA[i + 1], x[i]); sufB[i] = B.lca(sufB[i + 1], x[i]); } } LL ans = 0; for (int i = 0; i < k; i ++ ){ if (!i){ if (a[sufA[1]] > b[sufB[1]]){ ans ++ ; } } else if (i == k - 1){ if (a[preA[k - 2]] > b[preB[k - 2]]){ ans ++ ; } } else{ if (a[A.lca(preA[i - 1], sufA[i + 1])] > b[B.lca(preB[i - 1], sufB[i + 1])]){ ans ++ ; } } } cout << ans << "\n"; return 0; }
C.Concatenation
题意:
给定 \(s\) 个字符串,输出将它们拼接起来后字典序最小的字符串。
思路:
直接 \(sort\),stable_sort 较稳定。
代码:
#include <bits/stdc++.h> using namespace std; #define LL long long int main(){ ios::sync_with_stdio(false);cin.tie(0); LL n; cin >> n; vector <string> s(n); for (int i = 0; i < n; i ++ ) cin >> s[i]; sort(s.begin(), s.end(), [](string a, string b){ return a + b < b + a; }); for (int i = 0; i < n; i ++ ) cout << s[i]; return 0; }