P5513

P5513 容易发现，每次等价于对一个二进制数进行操作。但是这个二进制数长为 \(n\)，即需要高精。但是这样支持加一和减一是复杂度会退化为 \(\mathcal{O}(n^2)\)，有一个很正常的做法就压位，仿照 bitset 的做法进行操作，复杂度 \(\mathcal{O}(\frac{n ^ ......

赛时（模拟赛）乱加优化写挂了，爬来写题解。 发现点的深度和路径长度都非常大，而且一个点有多种方式到达，考虑先用统一的方式存储两个点的位置，再进行求解。 存储 为了更好地表示当前的位置，考虑对每个点编号。首先想到类似线段树的编号方法：初始点编号为 \(1\)，设当前点编号为 \(x\)，则左儿子编号为 ......

NOIP 模拟赛原题，赛时没切。 我们可以先考虑 \(30\) 分的部分分怎么打，\(n \le 50\)。对于每一个点去维护两个信息 \(pos\) 和 \(depth\) 分别表示当前这个点所在位置的编号是多少以及它在第几层，我们从两个点最后的状态往回考虑。然后用一个贪心的思想，深度大的点一定会 ......

70分做法非常容易想到，使用高精度对经过的点编号，令 \(pos\) 为点的编号，初始为 \(1\) ，则： 1 ：\(pos<<=1\) 2 ：\(pos<<=1|1\) U ：\(pos>>=1\) L ：\(pos--\) R ：\(pos++\) #include<bits/stdc++.h ......