5513
P5513 [CEOI2013] Board 题解
P5513 容易发现,每次等价于对一个二进制数进行操作。但是这个二进制数长为 \(n\),即需要高精。但是这样支持加一和减一是复杂度会退化为 \(\mathcal{O}(n^2)\),有一个很正常的做法就压位,仿照 bitset 的做法进行操作,复杂度 \(\mathcal{O}(\frac{n ^ ......
P5513 [CEOI2013] Board 题解
赛时(模拟赛)乱加优化写挂了,爬来写题解。 发现点的深度和路径长度都非常大,而且一个点有多种方式到达,考虑先用统一的方式存储两个点的位置,再进行求解。 存储 为了更好地表示当前的位置,考虑对每个点编号。首先想到类似线段树的编号方法:初始点编号为 \(1\),设当前点编号为 \(x\),则左儿子编号为 ......
P5513 [CEOI2013] Board
NOIP 模拟赛原题,赛时没切。 我们可以先考虑 \(30\) 分的部分分怎么打,\(n \le 50\)。对于每一个点去维护两个信息 \(pos\) 和 \(depth\) 分别表示当前这个点所在位置的编号是多少以及它在第几层,我们从两个点最后的状态往回考虑。然后用一个贪心的思想,深度大的点一定会 ......