Fork me on GitHub

提高失联测D9

版权原因,题面不公开

蔡老板

这道题题解里的二分的$check$到底是怎么想出来的啊….
我们考虑到对于某个数$i$,在它的二进制表示下,对于某个确定的$2^i$的物品,你取还是不取是不影响$2^j(j<i)$的物品拿还是不拿的.
然后发现显然钱数这个东西是满足单调性的所以显然可以爬山所以我们可以二分钱数然后$check$.
但是发现这个东西貌似不怎么好$check$.我们想一下我们之前说的性质,可以发现对于每一位,如果在二进制表示下是$1$,那么如果不拿就一定亏了(确信).
但是拿的话只拿这个价格的东西显然不会更优.我们想一下,对于这一位之前的某一维,我们选之后(或者根本没选)剩下的,如果直接扔掉显然会浪费掉.
然后我们又会发现,因为每个东西的价格都是用二的幂次方表示的,而两个价格为$2^i$的物品可以合并为一个$2^{i+1}$的物品.而这个操作显然需要我们按照钱数从小到大进行.
那么我们的贪心思路就比较明显了,我们对于每一个二分出来的钱数$mid$,我们从低到高考虑这个钱数的每一位,如果是$1$的话,那么我们就选择当前维护的最大的一个值.然后把其他的从大到小两两合并成一个新的.
而对于二进制考虑下是$0$的情况,我们直接合并即可.

唯一睿酱

我们设$f_{l,r}$表示$l,r$这段区间一共有多少种方案,而且$l-1,r+1$是边界或者大于其中的所有数字.那么转移的话,我们可以考虑在$l,r$中枚举一个$k$,使得$l+r_k=k$或者$k+r_k=r$,然后转移就好了.
但是这样转移的话发现时间复杂度是$O(n^3)$的,我们还得考虑怎么优化:我们发现,对于某个确定的$k$,它只能转移到$l=k-r_k$或者$r=k+r_k$的区间.所以我们不再枚举$k$,而是对于每一个$k$,我们都选择枚举它能转移到哪里.
时间复杂度为$O(n^2)$.

波波🐮

蔡老板牛逼!

因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:提高失联测D9

文章作者:KRrrrrrrrr

发布时间:2019年11月04日 - 08:11

最后更新:2019年11月04日 - 15:11

原始链接:http://krrrr.xyz/2019/11/04/提高失联测D9/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。