某位 CSP-S 二等的蒟蒻选手,试图用类似线段树的结构维护本题的树,然后他在删除节点时这样写,调了几分钟:
del(u << 1, l, mid, dep + 1, tdep, rnk);
del(u << 1, mid + 1, r, dep + 1, tdep, rnk);
希望大家能够在写数据结构时注意自己在写什么,有最基本的视力,而不是乱写一气。此外,不要什么都用数据结构做,容易出问题。
以下是这位同学的代码,可以看出来非常不优雅:
#include<bits/stdc++.h>
using namespace std;
struct node{
int dep, x, y, l, r, stk, sstk;
bool del;
}tr[200005];
int n, m, delt, lin[821 * 6];
queue<int> q;
void build(int u, int l, int r, int dep){
tr[u].dep = dep;
tr[u].l = l;
tr[u].r = r;
if (l == r)
return;
int mid = (l + r) >> 1;
build(u << 1, l, mid, dep + 1);
build(u << 1 | 1, mid + 1, r, dep + 1);
}
void del(int u, int l, int r, int dep, int tdep, int rnk){
if (dep == tdep){
// cout << u << " " << (1 << dep - 1) - 1 << "\n";
if (u - (1 << dep - 1) + 1 == rnk)
tr[u].del = 1;
return;
}
int mid = (l + r) >> 1;
del(u << 1, l, mid, dep + 1, tdep, rnk);
del(u << 1 | 1, mid + 1, r, dep + 1, tdep, rnk);
}
void ini(int u, int l, int r, int dep){
if (dep == n){
int pir = (l - 1) / 2;
tr[u].y = 6 * pir + 1 + 4 * (l & 1 ^ 1);
tr[u].x = 2147483647;
tr[u].stk = tr[u].sstk = 1;
return;
}
int mid = (l + r) >> 1;
ini(u << 1, l, mid, dep + 1);
ini(u << 1 | 1, mid + 1, r, dep + 1);
tr[u].x = tr[u << 1].x - tr[u << 1].stk;
tr[u].stk = tr[u << 1].sstk + (n - dep);
tr[u].sstk = tr[u << 1].sstk + tr[u].stk;
tr[u].y = tr[u << 1].y + tr[u << 1].stk + 1;
}
void delta(int u, int l, int r){
tr[u].x -= delt;
if (l == r)
return;
int mid = (l + r) >> 1;
delta(u << 1, l, mid);
delta(u << 1 | 1, mid + 1, r);
}
void print(int dep){
int stkl = tr[1 << dep].stk;
vector<int> tmp;
while (!q.empty() && tr[q.front()].dep == dep){
tmp.push_back(q.front());
if (!tr[q.front() << 1].del)
q.push(q.front() << 1);
if (!tr[q.front() << 1 | 1].del)
q.push(q.front() << 1 | 1);
q.pop();
}
int ny = 1;
for (auto u : tmp){
while (ny < tr[u].y){
cout << " ";
++ny;
}
cout << "o";
++ny;
}
cout << "\n";
if (dep == n)
return;
for (int i = 1; i <= stkl; i++){
int ny = 1;
for (auto u : tmp){
while (ny < tr[u].y - i){
cout << " ";
++ny;
}
if (tr[u << 1].del)
cout << " ";
else
cout << "/";
++ny;
while (ny < tr[u].y + i){
cout << " ";
++ny;
}
if (tr[u << 1 | 1].del)
cout << " ";
else
cout << "\\";
++ny;
}
cout << "\n";
}
print(dep + 1);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> m;
build(1, 1, 1 << n - 1, 1);
for (int i = 1; i <= m; i++){
int dep, rnk;
cin >> dep >> rnk;
del(1, 1, 1 << n - 1, 1, dep, rnk);
}
ini(1, 1, 1 << n - 1, 1);
delt = tr[1].x - 1;
delta(1, 1, 1 << n - 1);
q.push(1);
print(1);
return 0;
}
然后是这位同学的警示后人:如果你这题挂了,还有可能是式子推的不对,左移右移的时候加一减一没有写正确,请好好检查。