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

http://xiejiadong.com/?p=434


E.Football

签到题。

就简单的两种情况需要直接传球给他。

1)没人传球给他,QQ小方必须传给他。

2)是一个两个人构成的死循环,QQ小方必须传给其中一个人。


F.Cross

显然,我们要优先安排区间结束早的女朋友。

而对于一个女朋友,我们应该尽量选择离结束时间最远的鸡来带它。

因为比较靠前的鸡,可能后面还是有用处的。

这样的话,分别对两个排序,然后对于当前女朋友二分查找是否有符合要求的,贪心选鸡即可。

You may also like

LEAVE A COMMENT

Statistics

  • 1
  • 2,003

Categories

Archive