2018.2 月赛题解

oxx1108 edited 6 年,1 月前

A 坑爹的售票机

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

但 $k$ 较小,因此 $2520$ 张票的最优解一定为通过性价比最高的方式买。因此最终答案为 DP 算到 $\min(n, n \bmod 2520+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

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

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

oxx1108

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

songtoy

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

oxx1108

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

huhst-邱毓稀

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

oxx1108

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

maggch

C…
:(

oxx1108

题目很“友好”吧

guoshen

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

ultmaster

不带空格的啊