【數據結構機試】樹
存儲 & 訪問
一般的樹
vector<int> v[N];
void dfs(int u) {
for(auto x : v[u]) {
...
dfs(x);
}
}
二叉樹
int L[N], R[N]; // 表示左右兒子的值分別是多少
至于編號，結點 \(i\) 的左兒子 \(2i\)，右兒子 \(2i+1\)
樹的遍歷
一般的數
分為先根（先訪問根，后訪問兒子）、后根（先訪問兒子，后訪問根）。
二叉樹
先序遍歷（根左右）、中序遍歷（左根右）、后序遍歷（左右根）。
題意
給你先序和后序遍歷序列，判斷二叉樹形態是否唯一。
解答
首先知道先序的構成：序列第一個數是根，然后依次是根的左子樹和右子樹，根在后序序列中位于最后一個；
先序第二個元素，是根的左兒子（除非根沒有左兒子，那么是根的右兒子）；
我們可以找到在后序序列中 先序第二個元素的位置 \(p\)，在先序序列中，從 \(p-1\) 到正數第二個，這些都是根的左子樹， \(p + 1\) 到先序最末尾，這些都是根的右子樹，我們由此遞歸建樹。
形態不唯一的情況：對某棵子樹的根來說，它只有左兒子無右兒子 或者 只有右兒子無左兒子，那么無論它到底有的是哪個兒子，你會發現，這兩種情況對應的先序和后序序列一樣，即無法判斷，此時就是不唯一的
code
點擊查看代碼
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3000 + 10;
int n, pre[N], post[N], tem[N];
int rt, L[N], R[N];
map<int, int> mp, Map;
int dfn, ans[N];
bool f = 1;
int solve(int l1, int r1, int l2, int r2) {
if(l1 > r1 || l2 > r2) return 0;
if(l1 == r1) return pre[l1];
int now_rt = pre[l1];
int now_l = pre[l1 + 1], pos = mp[now_l];
int cnt_l = pos - l2 + 1, cnt_r = r2 - pos - 1;
L[now_rt] = solve(l1 + 1, l1 + cnt_l, l2, l2 + cnt_l - 1);
R[now_rt] = solve(l1 + cnt_l + 1, r1, l2 + cnt_l, r2 - 1);
if(f && (!L[now_rt] || !R[now_rt]) && (L[now_rt] || R[now_rt])) f = 0;
return pre[l1];
}
void dfs(int rt) {
if(L[rt]) dfs(L[rt]);
ans[++dfn] = rt;
if(R[rt]) dfs(R[rt]);
}
signed main(){
ios::sync_with_stdio(false);
cin >> n;
for(int i = 1; i <= n; i++) cin >> pre[i], tem[i] = pre[i];
for(int i = 1; i <= n; i++) cin >> post[i];
sort(tem + 1, tem + n + 1);
for(int i = 1; i <= n; i++) {
int x = pre[i];
pre[i] = lower_bound(tem + 1, tem + n + 1, pre[i]) - tem;
Map[pre[i]] = x;
post[i] = lower_bound(tem + 1, tem + n + 1, post[i]) - tem;
mp[post[i]] = i;
}
if(n == 1) {
cout << "Yes" << '\n';
cout << Map[pre[1]] << endl;
return 0;
}
rt = solve(1, n, 1, n);
dfs(rt);
cout << (f ? "Yes" : "No") << endl;
for(int i = 1; i <= dfn; i++) {
ans[i] = Map[ans[i]];
if(i == 1) cout << ans[i];
else cout << ' ' << ans[i];
}cout << '\n';
return 0;
}
LCA
單次詢問 \(O(n)\) 復雜度的做法不再贅述。
并查集
當我們只關心結點之間有沒有關系時使用
分享一個板子：
點擊查看代碼
//并查集模板 親戚
#include<cstdio>
using namespace std;
int father[5005];
//路徑壓縮
int f(int x){
return x == father[x] ? x : (father[x] = f(father[x]));
}
int add(int x,int y){
int fx=f(x);
int fy=f(y);
return father[fx]=fy; //x.y無序，因為不是按樹的結構存儲，而是按集合
}
int main(){
int n,m,p;
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=n;i++) father[i]=i;
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
if(f(x)!=f(y)){
add(x,y);
}
}
for(int i=1;i<=p;i++){
int x,y;
scanf("%d%d",&x,&y);
if(f(x)==f(y)){
puts("Yes");
}
else puts("No");
}
return 0;
}
題意
\(m\) 通電話，給出通話雙方和時長（注意，兩人之間可能有多次通話），通話過的人屬于同一幫人。找到 人數>=3 且 通話總時間（幫派中每兩人之間）>=K 的幫派的人數和首領（和其他人通話最長的）
解答
并查集維護，注意要字符串轉數字編號，累加兩人通話總時間
code
點擊查看代碼
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2000 + 10;
int m, k;
map<string, int> mp;
string a, b;
int tem[N], dfn, ori[N];
struct node{
int u, v, t;
}peo[N];
int g[N][N];
bool vis[N][N];
int fa[N], sz[N], cnt[N];
vector<int> v[N];
int ans[N], id[N];
vector<int> prin;
inline int f(int x){
return x == fa[x] ? x : (fa[x] = f(fa[x]));
}
void add(int u, int v) {
int w = g[u][v];
u = f(u); v = f(v);
if(u != v) {
fa[u] = v;
sz[v] += sz[u] + w;
cnt[v] += cnt[u];
}
else {
sz[u] += w;
}
return;
}
int main(){
// ios::sync_with_stdio(false);
cin >> m >> k;
for(int i = 1; i <= m; i++) {
cin >> a >> b;
if(!mp[a]) mp[a] = (a[0] - 'A') * 26 * 26 + (a[1] - 'A') * 26 + (a[2] - 'A') + 1, tem[++dfn] = mp[a];
if(!mp[b]) mp[b] = (b[0] - 'A') * 26 * 26 + (b[1] - 'A') * 26 + (b[2] - 'A') + 1, tem[++dfn] = mp[b];
peo[i].u = mp[a]; peo[i].v = mp[b]; cin >> peo[i].t;
}
// cout << "dfn: " << dfn << endl;
sort(tem + 1, tem + dfn + 1);
for(int i = 1; i <= m; i++) {
int x = peo[i].u;
peo[i].u = lower_bound(tem + 1, tem + dfn + 1, peo[i].u) - tem;
ori[peo[i].u] = x;
x = peo[i].v;
peo[i].v = lower_bound(tem + 1, tem + dfn + 1, peo[i].v) - tem;
ori[peo[i].v] = x;
// cout << peo[i].u << ' ' << peo[i].v << endl; ////
g[peo[i].u][peo[i].v] += peo[i].t; g[peo[i].v][peo[i].u] += peo[i].t;
}
for(int i = 1; i <= dfn; i++) fa[i] = i, cnt[i] = 1, sz[i] = 0;
for(int i = 1; i <= m; i++) {
if(vis[peo[i].u][peo[i].v]) continue;
vis[peo[i].u][peo[i].v] = vis[peo[i].v][peo[i].u] = 1;
add(peo[i].u, peo[i].v);
// cout << peo[i].u << ' ' << peo[i].v << ' ' << g[peo[i].u][peo[i].v] << endl; ////
}
set<int> st;
for(int i = 1; i <= dfn; i++) {
int p = f(i);
// cout << p << ' ' << cnt[p] << ' ' << sz[p] << endl;
if(cnt[p] > 2 && sz[p] > k) st.insert(p), v[p].push_back(i);
}
cout << st.size() << endl;
if(st.empty()) return 0;
memset(ans, -1, sizeof(ans));
for(auto i : st) { // i: predecessor
for(auto x : v[i]) { // x: son
int res = 0;
for(int j = 1; j <= dfn; j++) {
res += g[x][j];
}
if(res > ans[i]) ans[i] = res, id[i] = x;
}
prin.push_back(id[i]);
}
sort(prin.begin(), prin.end());
for(auto i : prin) {
int tmp = ori[i] - 1;
string s;
s += (char)(tmp / (26 * 26) + 'A'); tmp %= (26 * 26);
s += (char)(tmp / (26) + 'A'); tmp %= (26);
s += (char)(tmp + 'A');
cout << s << ' ' << cnt[f(i)] << endl;
}
return 0;
}
浙公網安備 33010602011771號