【BZOJ 4374】Little Elephant and Boxes

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4374
神犇题解:http://www.cnblogs.com/clrs97/p/6371735.html

解题报告

这题如果钱的总数小一点就可以直接DP了
于是我就想到了这个题:BZOJ 2749
于是我们就可以把钱给离散化到900以内啦!
但这样我们没有办法进行转移,然后就不会了 QwQ

不过万能的Claris告诉我们,物品只有30个
于是我们可以折半暴搜,这样的话就不需要转移了
直接枚举左侧的值,右侧搞一个指针跟着动一动就好
时间复杂度: $O(nm{2^{\frac{n}{2}}} + n{m^2})$

【BZOJ 4722】由乃

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4722
神犇题解Ⅰ:http://blog.csdn.net/werkeytom_ftd/article/details/54429577
神犇题解Ⅱ:http://www.cnblogs.com/wxxlouisa/p/6139165.html

解题报告

这题看起来一眼不可做啊!
仔细想一想,发现确实不会做

看完题解后:果然是乱搞题!
先不管修改操作的话,如果询问的区间长度超过13的话,一定有解
相关证明可以参见:http://blog.csdn.net/werkeytom_ftd/article/details/54429577

现在考虑修改操作
因为单次询问最多涉及13个数
所以只需要支持单点查询+区间修改就可以了
于是用线段树打标记什么的就可以啦!

然而我们惊讶的发现,我们打的Tag在最后计算的时候会很大
More Formally:次数会爆 $ long long$
于是用不了快速幂了 QwQ
然后又不会了

于是接着去膜拜题解
发现我们可以用类似快速幂一样的东西搞出来
我们最终要求的是:$ {a_i}^{{3^x}}$
于是我们预处理出 $ f(i,j)$ 表示 $ {a_i}^{{3^{{2^j}}}}$
于是像快速幂一样搞一搞就可以啦!

最后我们求出了这13个数是什么,怎么判断有没有解呢?
我们可以 Meet in middle !