某NOIP模拟赛题解

prog

考虑用并查集维护，相等的变量在同一个连通块中。

维护每个不等关系$(x, y)$为以$x$为根的连通块与以$y$为根的连通块不等，这样合并以$x$, $y$为根的连通块的时候，我们以和每个连通块相关的不等关系个数作为它的rank，使用按秩合并的思想合并。假设我们把以$y$为根的连通块合并到以$x$为根的连通块，我们枚举每一个与$y$相关的不等关系$(y, z)$，将其改为$(x, z)$，如果遇到$(y, x)$，则说明出现不合法情况，退出即可。不等关系$(x, y)$可以用链表维护与并查集一同合并。

复杂度$O(N\log N)$。

manager

考虑中序遍历不唯一的情况，易得一个节点只有一个儿子时，无法确定其是左儿子还是右儿子，并且这是唯一可能出现不唯一的情况。我们统计出这样节点的个数为cnt，则答案为2的cnt次方。可以用压位高精度算出。

一个小技巧是，浮点数类型可以精确输出2的幂次方的整数。我们在C++中使用long double存储，用printf (“%.0Lf”, ans)输出即可。

复杂度$O(N^2)$。（若采用压位高精度）

dinner

发现题目若用常规思路则难以解决，但是题目中的强制在线存在明显的漏洞，即，其用一个$[1, n]$中的整数去加密一个$[0, 2^{64})$的数，这是十分不合理的，而题目给出的$f(x)$分布又十分随机，则我们可以枚举最后一个询问的答案，往回带入即可得到答案。

时间复杂度$O(N+Q)$。