NOI2014 Day1

起床困难综合症

题目描述：给出(n)个操作，每个操作包含一种运算((XOR、OR、AND))和一个数，已知一开始的数字为([0, m])，问经过(n)次操作后最大为多少

solution：
按二进制位从高位开始枚举，能算出(1)的，答案的这一位就为(1),否则为(0)。

时间复杂度：(O(30n))

魔法森林

题目描述：给出一个包含(n)个结点与(m)条边的无向图，每条边有两个值(A、B)，求从(1)号点到(n)号点经过的边的(A)的最大值+(B)的最大值最小。

solution：
因为路径的值由组成的边的最大值来衡量，所以应该用最小生成树的做法。按照(A)为关键字把边从小到大排序，枚举第(i)条边，加入图中维护最小生成树（以(B)为权值的最小生成树，用Link-cut-tree维护），询问(1)号点到(n)号点的最大值的最小（(B)），加上当前第(i)条边的(A)更新答案。
这里需要理解一下为什么直接加第(i)条边的(A)，因为如果经过了第(i)条边，因为边按(A)从小到大排序了，所以第(i)条边一定是图中的最大值，如果不经过第(i)条边，算出来的值也不能更新答案，所以这样做是正确的。

时间复杂度：(O(mlogm))