讲一个目光呆滞的笑话
查看原帖
讲一个目光呆滞的笑话
906320
Milky_Cat楼主2024/11/24 20:57

某位 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;
}

然后是这位同学的警示后人:如果你这题挂了,还有可能是式子推的不对,左移右移的时候加一减一没有写正确,请好好检查。

2024/11/24 20:57
加载中...