CFR599

CFR599 div1

CF1242A Tile Painting

code

CF1242B 0-1 MST

请先思考后再展开

正解做法长这样,推荐学习一下

vp的时候还写了个启发式合并维护联通块的出边,其实本质上是一样的,就是复杂了很多,code

CF1242C Sum Balance

题意:给出$K \le 15$个里面分别有$n_i \le 5e3$个数的盒子,构造一个方案,在每个孩子选一个数,得出K个数后重排,给每个盒子塞回一个数,使得每个盒子内数和相等

来自看题小王子的提醒:数字互不相同

请先思考后再展开

注意到所有数是不同的,那么如果知道某个盒子取出的数是什么,那么能放回这个盒子的数最多一个,可以直接找到

考虑到K个数的置换是若干个轮换组成,那么通过搜索找出以每个数开头的环($\sum n_i*k$),以二进制表示后做个子集卷积搞起来即可,$O(3^K)$,code

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/fd989168.html
转载请注明出处,谢谢!