第一场
1001 博弈
每个房间的先手并不一定追求在该房间获胜，所以考虑 anti-nim，也就是拿到最后一个石子的必败。
anti-nim 的结论是：若全部元素均为 \(1\)，偶数个 \(1\) 必败，奇数个 \(1\) 必胜；若存在大于 \(1\) 的堆，则异或和为 \(0\) 时必败，否则必胜。
先不考虑全为 \(1\) 的情况，发现如果异或和不为 \(0\)，先手可以控制自己下回合是先手还是后手，于是也就必胜了。否则，先手既不能控制获胜也不能控制失败，故先手必败。
接下来考虑全是 \(1\) 的情况，发现根据 \(1\) 的奇偶性，会改变先后手的顺序。于是枚举前缀中 \(1\) 的数量，即可判断要使先手必胜，下一个位置应该放哪种房间，然后接下来的部分就随便排。最后再把不会影响先后手顺序的全 \(1\) 房间插回去即可。
注意特判房间全为全 \(1\) 房间的情况。
1002 夜世界
先考虑没有回溯的情况，没经过一个金矿，可以获得 \(a_i-b_i\) 的金币，也就是 \(sum=\max(0,sum+a_i-b_i)\)。假设我对于每个段，预处理出以 \(0\) 的金币进入，会以多少金币离开。那么就只用考虑第一变成 \(0\) 金币的位置，大概就是二分找到前缀最小值的位置，在线段树上二分复杂度可以做到 \(O(n\log^2n)\)。回溯的话大概可以可持久化。
注意到本题可以离线，修改操作也是可逆操作，所以回溯的部分可以写成一个树形结构。在树上递归去做。
刚刚那个单侧递归的做法也不太对，这类问题貌似有个更简单的想法。