1001

1002

1003

考察了多种博弈…

1004

1007

用最少的链覆盖一棵树的所有路径,并且使链的总长度尽量小
求链的最小长度

树形dp

通过观察,最小链覆盖数为 (leaf+1)/2

如果有子树有偶数个节点,那么从根延伸两条链,奇数个一条链
其余的节点可以相互配对

如果有偶数个叶节点,那么就可以直接得到答案
如果有奇数个,那么有一个叶子节点连向一个非叶子节点
我们枚举一下这个节点来自哪个子树,将他连到当前节点,即不再向上延伸
注意这个节点改变了子树的叶子节点的奇偶,所以要修改子树的贡献
(具体实现见代码)

复杂度 $O(n)$

1010

物理竞赛题…

$T = \frac{v_1a}{v_1^2 - v_2^2}$

刚开始试着用老庞给的式子来模拟
然而达到要求精度范围会TLE

1011

判断坐标范围在M内的N个点是否有曼哈顿距离相等的两对(可共享一个公共点)

直接暴力,统计曼哈顿距离
曼哈顿距离只有2M种,所以算法会在2M步内停止

复杂度 $O(min(n^2,m))$