头像

jackrrr




离线:3天前



jackrrr
8天前

’‘’

include [HTML_REMOVED]

using namespace std;

const int N = 40;
int pre[N], post[N], n;

int build(int preL, int preR, int postL, int postR, string& res){
int cnt = 0;
if(preL > preR) return 1;
if(pre[preL] != post[postR]) return 0;

for(int i = preL; i <= preR ; i++){
    string lstr, rstr;
    int lcnt, rcnt;
    lcnt = build(preL + 1, i, postL, postL + (i-preL -1), lstr);
    rcnt = build(i + 1, preR, postL + (i-preL), postR - 1, rstr);

    if(!lcnt || !rcnt) continue;
    res = lstr + to_string(pre[preL]) + " " + rstr;
    cnt += lcnt * rcnt;
    if(cnt > 1) break;
}
return cnt;

}

int main(){
cin >> n;
for(int i = 0; i < n; i) cin >> pre[i];
for(int i = 0; i < n; i
) cin >> post[i];

string res;
int cnt;
cnt = build(0, n - 1, 0, n - 1, res);

if(cnt == 1) puts("Yes");
else puts("No");

res.pop_back();
cout << res << endl;
return 0;

}
‘’‘



活动打卡代码 AcWing 1552. AVL树的根

jackrrr
8天前

’‘’

include [HTML_REMOVED]

using namespace std;

const int N = 30;
int l[N], r[N], w[N], ind;
int n, h[N];

void update(int u){
h[u] = max(h[l[u]], h[r[u]]) + 1;
}

int gb(int u){
return h[l[u]] - h[r[u]];
}

void R(int& u){
int p = l[u];
l[u] = r[p], r[p] = u;
update(u), update(p);
u = p;
}

void L(int& u){
int p = r[u];
r[u] = l[p], l[p] = u;
update(u), update(p);
u = p;
}

void insert(int& u, int v){
if(!u){
u = ++ind;
w[u] = v;
}
else if(v < w[u]){
insert(l[u], v);
if(gb(u) >= 2){
if(gb(l[u]) == 1) R(u);
else L(l[u]), R(u);
}
}else{
insert(r[u], v);
if(gb(u) == -2){
if(gb(r[u]) == -1) L(u);
else R(r[u]), L(u);
}
}
update(u);
}

int main(){
cin >> n;
int v, root = 0;
for(int i = 0; i < n; i++){
cin >> v;
insert(root, v);
}
cout << w[root] << endl;
return 0;
}

’‘’



活动打卡代码 AcWing 1631. 后序遍历

jackrrr
11天前
//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

’‘’

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

const int N = 50010;
int in[N], pre[N];
unordered_map[HTML_REMOVED] pos;
int post, n;

void build(int il, int ir, int pl, int pr){
int root = pre[pl];
int k = pos[root];
if(il < k) build(il, k-1, pl+1, pl+1+(k-1-il));
if(k < ir) build(k+1, ir, pl+1+(k-il), pr);
if(!post) post = root;
}

int main(){
cin >> n;
for(int i = 0; i < n; i)cin >> pre[i];
for(int i = 0; i < n; i
){
cin >> in[i];
pos[in[i]] = i;
}

build(0, n-1, 0, n-1);
cout << post << endl;
return 0;

}’‘’




jackrrr
11天前

’‘’

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

const int N = 40;
int in[N], post[N];
unordered_map[HTML_REMOVED] l, r, pos;
int q[N];
int n;

int build(int il, int ir, int pl, int pr){
int root = post[pr];
int k = pos[root];
if(il < k) l[root] = build(il, k-1, pl, pl + (k-1-il));
if(k < ir) r[root] = build(k+1, ir, pl + (k-il), pr-1);
return root;
}

void bfs(int u){
q[0] = u;
int hh, tt;
hh = tt = 0;
int layer = 0;

while(hh <= tt){
    int head = hh;
    int tail = tt;
    while(hh <= tail){
        int t = q[hh++];
        if(l.count(t)) q[++tt] = l[t];
        if(r.count(t)) q[++tt] = r[t];
    }
    if(++layer % 2) reverse(q + head, q + tail + 1);
}

cout << q[0];
for(int i = 1; i < n; i++) cout << " " << q[i];
cout << endl;

}

int main(){
cin >> n;

for(int i = 0; i < n; i++){
    cin >> in[i];
    pos[in[i]] = i;
}
for(int i = 0; i < n; i++) cin >> post[i];

int root = build(0, n-1, 0, n-1);

bfs(root);
return 0;

}

’‘’




jackrrr
11天前

’‘’

include [HTML_REMOVED]

using namespace std;

const int N = 1010;
int l[N], r[N], w[N], ind;
int cnt[N], maxd;
int n;

void insert(int& u, int v, int depth){
if(!u){
u = ind;
w[u] = v;
cnt[depth]
;
maxd = max(maxd, depth);
return;
}
if(v <= w[u]) insert(l[u], v, depth + 1);
else insert(r[u], v, depth + 1);

}

int main(){
cin >> n;

int root = 0;
for(int i = 0; i < n; i++){
    int v;
    cin >> v;
    insert(root, v, 0);
}

int a = cnt[maxd], b = cnt[maxd-1];
printf("%d + %d = %d\n", a, b, a + b);
return 0;

}

’‘’



活动打卡代码 AcWing 1600. 完全二叉树

jackrrr
11天前

’‘’

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

const int N = 30;
int l[N], r[N], maxk, maxid;
bool hf[N];
int n;

void dfs(int u, int k){
if(u == -1) return;
if(k > maxk){
maxk = k;
maxid = u;
}
dfs(l[u], k * 2);
dfs(r[u], k * 2 + 1);
}

int main(){
cin >> n;

memset(l, -1, sizeof l);
memset(r, -1, sizeof r);

for(int i = 0; i < n; i++){
    string a, b;
    cin >> a >> b;
    if(a != "-") l[i] = stoi(a), hf[l[i]] = true;
    if(b != "-") r[i] = stoi(b), hf[r[i]] = true;
}

int root = 0;
while(hf[root]) root++;

dfs(root, 1);

if(maxk != n) printf("NO %d\n", root);
else printf("YES %d\n", maxid);

return 0;

}

’‘’



活动打卡代码 AcWing 1592. 反转二叉树

jackrrr
11天前

’‘’#include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

const int N = 20;
int l[N], r[N];
bool hf[N];
int n;
int q[N];

void dfs_r(int u){
if(l[u] != -1) dfs_r(l[u]);
if(r[u] != -1) dfs_r(r[u]);
swap(l[u], r[u]);
}

void dfs(int u, int& i){
if(u == -1) return;
dfs(l[u], i);
if(++i != n) cout << u << ” “;
else cout << u << endl;
dfs(r[u], i);
}

void bfs(int u){
q[0] = u;
int hh, tt;
hh = tt = 0;
while(hh <= tt){
int top = q[hh];
if(l[top] != -1) q[
tt] = l[top];
if(r[top] != -1) q[tt] = r[top];
}
cout << q[0];
for(int i = 1; i < hh; i
) cout << ” ” << q[i];
cout << endl;
}

int main(){
cin >> n;

memset(l, -1, sizeof l);
memset(r, -1, sizeof r);
for(int i = 0; i < n; i++){
    char a, b;
    cin >> a >> b;
    if(a != '-') l[i] = a - '0', hf[l[i]] = true;
    if(b != '-') r[i] = b - '0', hf[r[i]] = true;
}

int root = 0;
while(hf[root]) root++;

dfs_r(root);

bfs(root);

int i = 0;
dfs(root, i);

}’‘’




jackrrr
14天前
#include <iostream>
#include <unordered_map>
#include <algorithm>

using namespace std;

const int N = 110;

unordered_map<int, int> l, r;
int temp[N];
int n;
int q[N], res[N];
int cnt;

void dfs(int root){
    if(l.count(root)) dfs(l[root]);
    res[root] = temp[cnt++];
    if(r.count(root)) dfs(r[root]);
}

void bfs(int root){
    q[0] = root;
    int h, t;
    h = t = 0;
    while(h <= t){
        int top = q[h++];
        if(l.count(top)) q[++t] = l[top];
        if(r.count(top)) q[++t] = r[top];
    }
    cout << res[q[0]];
    for(int i = 1; i < h; i++) cout << " " << res[q[i]];
    cout << endl;
}

int main(){
    cin >> n;
    int a, b;
    for(int i = 0; i < n; i++){
        cin >> a >> b;
        if(a != -1) l[i] = a;
        if(b != -1) r[i] = b;
    }
    for(int i = 0 ; i < n; i++) cin >> temp[i];
    sort(temp, temp + n);

    dfs(0);
    bfs(0);

    return 0;


}


活动打卡代码 AcWing 1576. 再次树遍历

jackrrr
14天前

r1. 方法一: 在build()里面填充l, r. 之后dfs()

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

const int N = 100;

int pre[N], in[N];
unordered_map[HTML_REMOVED] l, r, pos;
stack[HTML_REMOVED] stk;
vector[HTML_REMOVED] res;
int n;

int build(int il, int ir, int pl, int pr){
int root = pre[pl];
int k = pos[root];
if(il < k) l[root] = build(il, k-1, pl+1, pl+1+(k-1-il));
if(k < ir) r[root] = build(k+1, ir, pl+1+(k-il), pr);
return root;
}

void dfs(int a){
if(l.count(a)) dfs(l[a]);
if(r.count(a)) dfs(r[a]);
res.push_back(a);
}

void print(){
cout << res[0];
for(int i = 1; i < n; i++) cout << ” ” << res[i];
cout << endl;
return;
}

int main(){
cin >> n;

int pi = 0;
int ii = 0;
for(int i = 0; i < 2*n; i++){
    char type[10];
    int node;
    cin >> type;
    if(type[1] == 'u'){
        cin >> node;
        stk.push(node);
        pre[pi++] = node;
    }
    else{
        int top = stk.top();
        stk.pop();
        in[ii] = top;
        pos[top] = ii++;
    }

}

int root = build(0, n-1, 0, n-1);
dfs(root);
print();
return 0;

}
r2. 方法二: 直接在build()里面后序遍历填充

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

const int N = 100;

int pre[N], in[N];
unordered_map[HTML_REMOVED] l, r, pos;
stack[HTML_REMOVED] stk;
vector[HTML_REMOVED] post;
int n;

void build(int il, int ir, int pl, int pr){
if(il > ir) return;
int root = pre[pl];
int k = pos[root];
build(il, k-1, pl+1, pl+1+(k-1-il));
build(k+1, ir, pl+1+(k-il), pr);
post.push_back(root);
}

void print(){
cout << post[0];
for(int i = 1; i < n; i++) cout << ” ” << post[i];
cout << endl;
return;
}

int main(){
cin >> n;

int pi = 0;
int ii = 0;
for(int i = 0; i < 2*n; i++){
    char type[10];
    int node;
    cin >> type;
    if(type[1] == 'u'){
        cin >> node;
        stk.push(node);
        pre[pi++] = node;
    }
    else{
        int top = stk.top();
        stk.pop();
        in[ii] = top;
        pos[top] = ii++;
    }

}

build(0, n-1, 0, n-1);
print();
return 0;

}




jackrrr
14天前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;
int a[N], b[N];
int n;
int k;

void dfs(int u){
    int l = u * 2, r = l + 1;
    if(l <= n) dfs(l);
    b[u] = a[k++]; //b[k++] = a[u];
    if(r <= n) dfs(r);
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);

    dfs(1);

    cout << b[1];
    for(int i = 2; i <= n; i++) cout << " " << b[i];
    cout << endl;
    return 0;
}