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
显然,我们要优先安排区间结束早的女朋友。
而对于一个女朋友,我们应该尽量选择离结束时间最远的鸡来带它。
因为比较靠前的鸡,可能后面还是有用处的。
这样的话,分别对两个排序,然后对于当前女朋友二分查找是否有符合要求的,贪心选鸡即可。