整体难度不大,但是因为前期冲的太猛了,15分钟做了3道题,后期跟风做题,看着别人都6题甚至AK了,就有点慌张,后期基本上没有深入思考,状态很浮躁,导致最终结果很差。因为后一个小时都靠直觉做题,有一些简单的问题反而没有思考,而且很容易被带偏方向。
博弈论SG函数不会做也是一个硬伤。
\(E\)
给一个二元序列\(<a_i,b_i>\)和\(n,tot\),求最大的\(k\)使得选出\(k\)个二元组满足\(k\times\sum b_j+\max a_j<= tot\),其中\(a_j\)和\(b_j\)是选出来的元素。
容易想到,对\(a\)排序后,枚举到当前的第\(i\)个元素则当作当前的最大的\(a_i\),然后看这个总和是否超限,如果超限,先除去最大的\(b_j\)(已经选过的那部分当中的最大的),以此类推。可以发现,这样的选法一定是最优的。用堆来维护选出来的\(b\)即可。然后每一步的\(k\)取一个最大值就是答案了。
\(F\)
博弈论,SG函数
n堆石子,可以把某一堆均分成2堆,也可以拿走一堆,或者拿走一堆中的一个,问谁赢?
写出SG函数推式子即可。因为注意到\(SG_{n/2}\ xor\ SG_{n/2}=0\)这个性质,是和\(SG_0=0\)是完全一致的,所以均分两堆石子这个操作是没有作用的,可以被其他操作等效掉,所以不考虑均分,然后就是简单的递推一下,发现奇数的SG是1,偶数的SG是2,然后异或起来即可。