2018.2 月赛题解

oxx1108 edited 7 年，1 月前

A 坑爹的售票机

首先可以贪心直接计算出对于每次买 $i$ 张最少所需要的纸币数，这样就转换为一个背包问题。Hard 由于 $n$ 太大，不能直接 DP。

但 $k$ 较小，因此 $2520$ 张票的最优解一定为通过性价比最高的方式买。因此最终答案为 DP 算到 $min(n,nmod2520+2520)$（每种买票方式需要通过 DP 算的最多不超过 2520 张，若超过 2520 张则这 2520 张可以按性价比最优方式买，因此最多 DP 到 $k!k$ 即可），再加上剩余若干份 2520 张票。卡了几个假得不行的算法，优秀的假算法可能也能过……

验题人野鸡解法：大部分票肯定是 $m$ $(1\le m\le k)$ 张一买的，枚举 $m$。然后，剩下的票直接 DP 算。大部分是多少呢？就取 $n-1000$ 好了。证明？不会……

B 无聊的游戏

比较裸的 SG 函数，每次操作后等于将一棵树拆为若干棵树，可将一棵树看为 $Nim$ 问题里的一堆石子，因为相互独立的树之间没有联系。直接暴力算会超时，因此需要对树 Hash 一下再记忆化。

还有一种很套路的做法，就是记忆化搜索，对于点状压一下记录状态，然后保存必胜态和必败态也可以，复杂度 $O(2^{n}n)$，足已通过。

C 贪吃的xjj和贪心的oxx

无论什么情况答案都为 Yes，方法为将原序列从大到小排序，贪心地放两堆，每次往少的一堆里放新的一盒，最终取少的一堆即可。

D 黑心的出租车

因为题目保证无环，因此必为树或森林。

当图为一棵树时，答案为 $0,2(n-1)$。

当图为森林时，出租车次数判一下联通块即可，其实答案就是 $n-m$。而巴士站数，对于每个联通块，需要 $2$ 倍边的数量减去树的直径，然后求和即可。

注意慎用 memset，初始化仅需 DFS 所需要用的点，不然会 TLE。

E 出老千的xjj

当牌总数小于等于 $k$ 时，只需一张一张出即可，因此答案为 $0$。

当牌总数大于 $k$ 时，需要每次出 $x$ 张，且 $x$ 不整除 $k$，即加上万能牌后所有牌数量的$gcd$ 要不为 $k$ 的约数。

对于每次枚举的 $p$，通过前缀和可以求出数量在 $(p\cdot i,p(i+1)]$ 之间堆数的个数 $num$ 以及总数量和 $sum$，那么需要 $num\cdot p(i+1)-sum$ 张万能牌，最后求和即可。总复杂度 $O(n\log n)$。前缀和数组注意开到 $2\cdot {10}^6$。

还可以进行进一步优化：只需要枚举所有素数即可，对于 $k$ 的素因子 $p$，则取 $p^i$，最小的 $i$ 使得 $p^i$ 不能整除 $k$。

F 回家咯

三个方程可以解出 Xiamen 到中转站，中转站到 xjj 家和中转站到 oxx 家的时间，只要都为正数即有解，否则 Wrong。

Comments

神秘的bboy

7 年，1 月前

打扰一下，比赛后我删了一句话就AC了，对比之下，还是不明白，可能您错了。就是我感觉p可以是k的因子啊，因为在一方出完之前都是轮出的，所以即便是素数也得先验证是不是自己先走完吧。。。。呜呜，反正我就是这样WA的。代码： http://www.cnblogs.com/hua-dong/p/8447768.html 。

然后特别操蛋的是maxn<=2倍1e6，我觉得数据太水了吧。都是小于1e6，然后我以为和<=1e10左右。然后我就以为我是以为这个WA了。

回复 1 0

oxx1108

7 年，1 月前

当然可以啊，但是这可以归纳到第一种情况，通过计算可以知道需要sum(xi) / p <= k / p，即sum(xi) <= k。因为操作是增加sum的，所以原来sum就大于k的话，sum不会再变得小于k，所以可以归纳到第一种。我看了你的代码，不知为什么你的xx是n。
Cases里有大于1e6的啊，但是不超过2e6。

回复 1 0

huhst-邱毓稀

7 年，1 月前

F题的误差怎么没用咧？怎么知道时间是不是在误差范围之内呢？

回复 0 0

oxx1108

7 年，1 月前

你的代码好像编译没通过……

回复 0 0

maggch

7 年，1 月前

C…
:(

回复 0 0

oxx1108

7 年，1 月前

题目很“友好”吧

回复 4 2

guoshen

7 年，1 月前

群密码是多少啊。。。难道不是ECNU Online Judge吗？

回复 0 0

ultmaster

7 年，1 月前

不带空格的啊

回复 0 0

songtoy

7 年，1 月前

请问A,C的解法的正确性怎么证明？

回复 0 0

oxx1108

7 年，1 月前

A你写成方程组，把每一项都mod2520就可以了。C你按这个做法模拟操作一遍就知道了，因为如果不满足条件，多的那堆最少的是不会在多的那堆里的。

回复 2 0