MCPC 2016

@晴川大爷 说要带我飞,我们去打一个澳洲大学的校赛,虐虐大雪参,轻松AK轻松夺冠辣(flag),于是我们果然轻松狗带辣。T_T。

这个比赛一共有六个水题,题目在这里

赛中晴川大爷强行拿了全场一血,然后我们就开始了持续懵逼之路。

A

这是一个水题,判一下(i & 1) ^ (j & 1)不过有个trick容易wrong answer。

B

这是一个模拟题。

C

这题是一个约瑟夫变种,因为$k$不大,所以可以直接快速模拟。

D

题目大意就是给一个100,000边5000点的无向图,两个人分别从两个起点$u, v$出发到一个地方$c$
第一个人单独走速度是$1$秒一条边,第二个人单独走速度是5秒一条边,两人相遇之后一起走是2秒一条边,求最少时间。
那么这个就是分别以$u, v, c$为起点跑一次单源点最短路,枚举一下相遇点就好了。

E

这题验证一个8e18范围内的数字是不是square free的。
我们知道这个数如果有两个相同因子,那么一定有两个相同的素因子;
而且容易知道如果这个素因子超过2e6,那么另一部分必然小于2e6
所以我们枚举2e6以内的素因子,并判断一下是不是所有的素因子都只有一个。
剩下的部分再判断一下是不是完全平方数就可以了。

F

就是对机器做无限背包,对人做01背包。因为要输出一个可行解,同时还有一些其他小细节,这个题不怎么好写。

赛中只做出来前五题,赛后补了一下F,感觉码力太弱了。T_T。

我的B、C、E、F的代码