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-12-16
背包+根号分治：loj6089
背包+根号分治：loj6089 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135032303 https://loj.ac/p/6089 考虑根号分治，前面是个多重背包，直接分组部分和优化。 然后后面是个完全背包，直接做容易炸，但直接上整数划分dp即可。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455...
2021-12-08
【CF577B Modulo Sum】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15664786.html 题目链接 题目 You are given a sequence of numbers a1, a2, …, an, and a number m. Check if it is possible to choose a non-empty subsequence aij such that the sum of numbers in this subsequence is divisible by m. 给出 111 ...
2023-12-27
环异或 + bitset线性基 +线段树分治 ： P3733
环异或 + bitset线性基 +线段树分治 ： P3733 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135240352 https://www.luogu.com.cn/problem/P3733 包括首都的环肯定由一个生成树上一堆环并起来，也就是对于一棵生成树，我们把所有非树边对应的环丢入线性基中，然后求最大。 由于初始的图不变，所有生成树就可以不变了。 对于加边、删边、改边操作。改边相当于删+加。每条边有一个存活时间，显然线段树分治即可。 线性基...
2022-02-17
【一本通OJ 1601：【例 5】Banknotes】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15905471.html 题目链接 题目 原题来自：POI 2005 Byteotian Bit Bank (BBB) 拥有一套先进的货币系统，这个系统一共有 nnn 种面值的硬币，面值分别为 b1,b2,⋯ ,bnb_1, b_2,\cdots , b_nb1,b2,⋯,bn 。但是每种硬币有数量限制，现在我们想要凑出面值 kkk，求最少要用多少个硬币。 思路 首先不考虑时间复杂度，这个问题应该是可以用多重背包求解的。 同时，我们也可以把...