8.26 T3日记和二叉搜索树（背包 + bitset优化 + 分治）
8.26 T3日记和二叉搜索树（背包 + bitset优化 + 分治）
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141610732
http://cplusoj.com/d/senior/p/NOD2301C
很容易转化为对于一个节点的儿子们要尽量平均分
这是经典的背包问题
然后这个背包又可以经典bitset优化
但是bitset开太大也会死掉，所以你可以手动分治
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2024-01-15
原根 + 背包 + bitset优化 + 二进制分组：0115B
原根 + 背包 + bitset优化 + 二进制分组：0115B 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135609260 http://47.92.197.167:5283/contest/451/problem/2 原根： g1,…,gp−1g^1,\dots,g^{p-1}g1,…,gp−1 在 mod p\bmod pmodp 意义下取遍 1∼p−11\sim p-11∼p−1 。在 ppp 为质数时， ggg 不超过 p14p^{\fr...
2021-11-14
【洛谷P2079 烛光晚餐】 题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15552456.html 题目链接 看到什么价值的什么喜爱度的明显是背包。 然而题目还要考虑小明的感受，所以弄个二维费用背包。 设 dp(i,j,k)dp(i, j, k)dp(i,j,k) 为前 iii 道菜，用 jjj 元，且小明的喜爱程度为 kkk 时小红的最大喜爱度。 如果不选，则 dp(i,j,k)=dp(i−1,j,k)dp(i, j, k)=dp(i-1, j, k)dp(i,j,k)=dp(i−1,j,k)。 如果选，则 dp(i...
2023-09-24
可删除背包（计数类）=＞转移数组进行展开：ABC321F
可删除背包（计数类）=＞转移数组进行展开：ABC321F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133219375 https://atcoder.jp/contests/abc321/tasks/abc321_f 还真没见过这个套路，呜呜┭┮﹏┭┮ 首先加就正常加，从后往前 但删的话应该是从前往后减 为什么呢？ 先写一下自己的理解，加要从后往前加是为了防止加多次 减的话为了保证每个被删的数只减一次，应该从前往后。 考虑前 iii 个已经被还原了，那...
2021-12-22
【CF2B The least round way】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15720399.html 题目链接 题目 There is a square matrix n × n, consisting of non-negative integer numbers. You should find such a way on it that starts in the upper left cell of the matrix; each following cell is to the right or down ...
2022-09-11
多重背包优化小结
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16576747.html 普通多重背包 外层枚举哪个包，中层枚举容量，内存枚举数量 1234for(i=1; i<=n; ++i) for(j=m; j>=0; --j) for(k=1; k*w[i]<=j && j<=s[i]; ++k) f[j]=max(f[j], f[j-k*w[i]]+k*v[i]); 二进制优化 相当于把每个包拆成 logloglog 个包然后分别01背包 123456...
2023-12-16
背包+根号分治：loj6089
背包+根号分治：loj6089 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135032303 https://loj.ac/p/6089 考虑根号分治，前面是个多重背包，直接分组部分和优化。 然后后面是个完全背包，直接做容易炸，但直接上整数划分dp即可。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455...