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的博客！
相关推荐
2021-12-08
【HDU 5550 Game Rooms】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15662976.html 题目链接 题目 Your company has just constructed a new skyscraper, but you just noticed a terrible problem: there is only space to put one game room on each floor! The game rooms have not been furnished yet, so you can ...
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 包括首都的环肯定由一个生成树上一堆环并起来，也就是对于一棵生成树，我们把所有非树边对应的环丢入线性基中，然后求最大。 由于初始的图不变，所有生成树就可以不变了。 对于加边、删边、改边操作。改边相当于删+加。每条边有一个存活时间，显然线段树分治即可。 线性基...
2021-11-18
【P2340 [USACO03FALL]Cow Exhibition G】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15573796.html 题目链接 一道很好的01背包变形题。 首先看一眼题很明显可以发现是背包。 此题我当时的第一反应是二维费用背包，然而会TLE+MLE，于是打开题解思考01背包做法。 设 dpidp_idpi 代表智商和为 iii 时情商的最大值。 dpi=maxj=1n(dpi−sj+fj)dp_i=\max_{j=1}^n(dp_{i-s_j}+f_j) dpi=j=1maxn(dpi−sj+fj) 经典的01背包转移。 ...
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 ...
2023-09-07
异或和大小比较类问题——抓住最高位：CF1863F
异或和大小比较类问题——抓住最高位：CF1863F 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132629186 https://codeforces.com/contest/1863/problem/F 因为有等于，所以考虑异或和为0的合法区间，它可以随意切 现在考虑切开后左边大于右边，可以发现左右边最高位可以互相抵消，似乎不太可做？ 此时可以换个考虑，考虑大区间的异或和的最高位，这一位在左右两个区间 恰好 有一位为1，而为1的那个区间就是...