2022牛客网OI赛前集训营提高组（第四场）

原题原题场。

题面在牛客，自己搜。

博弈

先手必胜的条件是：路径上存在至少一种权值的计数为奇数。考虑异或，给每一个边赋值一个不会冲突的权值计算到根结点的异或值进行统计即可。不知道为什么自然溢出才行，取模挂掉了。

跳跃

最优条件是，在某一个区间反复跳跃几次后前往下一个更优区间，以此类推直到最优区间，可以 。也可以进行 优化暴力艹过去，如果当前已经不需要跳跃转移（也就是处于最优区间），就可以不需要转移，直接暴力计算之后的答案即可。

大陆

洛谷有原题，叫皇室联邦。

考虑直接维护连通块，从叶结点到根结点遍历，如果当前栈中点数 就直接弹出并将当前的 作为首都，这样即使最后会剩下一些点，连通块大小也不会超过 。

排列

用 维护二元关系是否存在以及前驱后继最值进行转移即可，至于修改操作直接交换区间即可。