[CF1225G]To Make 1

这个题考试的时候没时间看了,结束时候花了好长时间才会,只能说明我太菜了…
看到这个题首先一脸懵逼,感觉无从下手,爆搜剪枝记忆化肯定会TLE,状压又压不了,数据范围还这么小,一定有什么神奇的性质。
那我随便想想吧,首先可以把合并的过程画成一棵二叉树,一个叶节点对应着一个$a_i$,父亲的权值是将其两个儿子取出合并再插回去之后的值。
感觉直接画上去没什么思路,然后可以转化一下模型,我们不妨令这棵二叉树变为多叉树且规定父亲的权值必须是其所有儿子权值的和除以k。
我们可以证明这两个模型是等价的,已知其中一个一定可以构造出一组另外一个。
现在这个层次结构就出来了,深度为i的元素对答案的贡献就要除以$k^i$,显然这个贡献加起来要等于1。
然后,我们可以用归纳法证明第i层的所有元素之和一定能被k整除。
考虑从下到上考虑构造方案,每次把深度最大的元素不断合并,如果被k整除了那就在前面的层中开一个点记录下合并后的结果(能被k整除几次就向上几层),由于该层所有元素的和一定能被k整除,所以这一层的元素一定可以通过这样的方式抵消完。
我们发现,只要构造出一组合法的深度方案,就能构造出一组合法的合并方案,而如果没有合法的深度方案,显然没有合法的合并方案。
所以我们只需要尝试构造深度方案。
显然直接用一个背包来做就好了。
然后这道题就切掉了。时间复杂度O(玄学),因为这个背包比较神奇,反正能过。

Tagged with:

发表评论