警示后人
查看原帖
警示后人
544520
liugh_楼主2024/4/27 13:41

如果你也像我这么写,并且除#25外全WA,可以看看这两点有没有做:

第一,同一水平线上的点若是最低点不能加入,但若是最高点则需要删除,可以考虑下面这样做。复杂度有保证吗?这个 for 每次只执行当前水平线上的点,所以一共最多执行 O(N)O(N) 遍。

for (int j = now; j <= N && pt[j].y == i; ++j) {
	if (pt[j].y == top[pt[j].x] && bit.query(pt[j].x) - bit.query(pt[j].x - 1) == 1)
		bit.modify(pt[j].x, -1);
}

第二,在最后记得特判一开始就有的黑点,比如这个 hack:

5
0 2
2 0
-2 0
0 -2
0 0
2024/4/27 13:41
加载中...