2019 ECNU XCPC March Selection #1
A.Game
考虑所有空的格子排成一串，相邻两个空的格之间设为一级台阶（从左到右逐级降低），这级台阶上的石子数量即为这两空格之间的棋子数量
为了方便处理，我们把数组倒序排放
可以看出一次棋子移动等价于把第\(n+1\)号台阶上的任意颗石子移动到第\(n\)级。我们从\(0\)开始编号
那么，我们可以发现，其实奇数位是没有影响的，显然，移到\(0\)位置的时候会出现败态
从奇数位到偶数位，我们在移回来即可
但是可以发现，偶数位的移动\(x\)颗棋子，相当于去掉了这\(x\)颗棋子
也就是，现在转化成了nim取石子了
那么，我们判断偶数位的\(xor\)值便可以得到先手的胜败态
现在要求的是先手胜利，第一步的方案数
显然，就是要求让每一个偶数位经过更改，使得\(xor=0\)的情况
而\(xor\)的性质就是，只有相等的时候才\(=0\)，且\(xor\)可逆，那么直接\(O(n)\)枚举即可
不过要注意一些边界的情况
B.The Bridge
显然，对于一个人\(x\)，他有两种最有的方法过桥：
1、选择时间最少的\(a[1]\)与他过去，\(a[1]\)回去，\(t=a[x]+a[1]\)
2、选择一个时间和他差不多的过去，在让另一个小的回来，\(t=a[x+1]+a[1]+a[2]*2\)
注意特判\(n=1\)的情况
C.Spies
贪心地选择当前点\(x\)为观察员，那么\(a[x]\)为\(spy\)，则，下一个观察员为\(a[a[x]]\)
用拓扑排序来实现。显然，当没有读入为\(0\)的点时，剩下的为环，那么，继续在环上贪心的找即可
D.The xor-longest Path
E.Football
签到题。
就简单的两种情况需要直接传球给他。
1）没人传球给他，QQ小方必须传给他。
2）是一个两个人构成的死循环，QQ小方必须传给其中一个人。
F.Cross
显然，我们要优先安排区间结束早的女朋友。
而对于一个女朋友，我们应该尽量选择离结束时间最远的鸡来带它。
因为比较靠前的鸡，可能后面还是有用处的。
这样的话，分别对两个排序，然后对于当前女朋友二分查找是否有符合要求的，贪心选鸡即可。