T1 改造二叉树 题面 洛谷上的数据有水，过了不代表正确； 这题还是比较难想的（至少我是这么认为的） 首先如果我们对一颗平衡树进行中序遍历，得到的一个遍历的序列是单调上升的。 于是我们这道题就转化成一个这样的问题： 给一棵二叉树，让它的中序遍历序列变为严格单调上升序列，最少需要多少次修改 《算法竞赛进阶指南（第二版）》的263面提过一个思考题： 把…

T1 增援前线 实锤乱搞题，考试的时候写了一个错误的dp，只拿了一半的分。 实际上这一题应该属于贪心吧 我们用f[i]表示i号点能站多少人。 显然，前l个点的f[i]=a[i]； 对于其他情况，f[i]应由i-l到i-1这段区间内的点更新而来。 具体来说，就是“能跳则跳，满员为止” 我们优先选择距离当前点较远的点来更新，下面将证明这一结论。 我们每…

题目描述 H 国有 n个城市，这 n 个城市用 n−1条双向道路相互连通构成一棵树，1号城市是首都，也是树中的根节点。 H国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。但特别要注…