Codeforces R473

我这个代码能力下降到\rm{-INF}

并查集板子打了15分钟 还有谁??

气死了

算了赶紧写完赶紧睡觉

A. Mahmoud and Ehab and the even-odd game(真长)

就这题!!!卡了我五分钟!!我觉得它长的像SG,是它的错还是我的?!

一定注意a \leq n!!

然后你就会发现这游戏最多就一轮

B. Mahmoud and Ehab and the message(这个更长?)

然后并查集板子+map……能这个点打Cf的都能看出来也不说了……

C. Mahmoud and Ehab and the wrong algorithm(哇,还是这么长)

送分(ming)构造题

两问分别长这样

注意第一问只有n \geq 5才有解……原因是层数和两个点的解的限制(也就是说第二层最少3个点然后第三层必须有两个点及以上((一个点的话那个算法也是正确的)))

D. Mahmoud and Ehab and another array construction task(最长!)

这题,扫一下然后质因数分解

如果分解有重那么立即断开,前面的原样输出,后面的贪心地选一个质数输出

注意特判

E. Mahmoud and Ehab and the xor-MST(哈!变短了吧!)

我们考虑……有什么好考虑的。。。

那就……从高位来考虑?

当前考虑的,要求mst的点集的所有点权,在目前位上, 必然是n_1 \text{ — } n_x这一部分是0,然后n_{x+1} \text{ — } n_{last}1,那么点 x+1 \text{ — } last之间独立连边,1 \text{ — } x之间独立连边,这么做,可以保证对答案贡献都是0,是最优的。

·

但是如果当前确实有一个满足上述条件的x存在的话,

(其实也就是现在考虑的点集的最大点权的点,点权模掉2^{w-1}大于等于2^w,其中w是当前考虑的位数)

(也就是这一位上有1的出现,所以点被划成了这一位是0 \; , \; 1两个子点集)

那么还要把左右两个点集联通。先加上这样的代价 :2^w

·

我们其实并不关心这两个点集是怎么内部联通的,因为这个可以递归求解。把两个点集的点权模掉2^w之后就成为子问题了,对吧?

但是0集那个子问题是可以预处理的,要不然会T。

f[i]表示从02^i-1的贡献和。怎么转移?这个其实就是……你把它按照上面我说的拆一下点集就好了。然后方程在这儿:f[i]=2*f[i-1]+(1LL<<w-1)这个不难理解吧……

我希望我这题说明白了.

(我怕我long long的位运算出锅于是打了快速幂……)

F. Mahmoud and Ehab and yet another xor task

留坑

发表评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据