宣?
T1 证明已补。
Upd on 2024/9/13:估分无误,静待上榜。
直接看编程题。话不多说,上题面。
T1:手套配对
T2:美丽路径
T1
本题为数学题,但是直接去推式子还是有一定难度的。
实际上可以瞪眼法先推一个“看起来比较正确”的式子。这个时候大概率会有问题,可以再用 dfs
打一张绝对正确的表(我用的是 n=5,m∈[1,10],k∈[1,5] 的表)。随后看看式子和表有什么区别(比如多乘了 2 的几次方,少了一项组合数之类的。)
相信我这么写大家都不会同意的,所以补个场后证明。
首先一个显然的结论:当 m<2×k 时,无可行方案,因为 k 对手套至少需要选择 2k 件手套才够。
排除这种情况,我们逐点考虑。首先在 n 对手套中选择完整 k 对的方案数为 Cnk。还剩下 m−2×k 件手套是可选的,而这些手套可以从剩下的 n−k 对手套中选择。左右手比较难办,我们暂时设剩下这些手套都只有左手,那么方案数就要再乘上 n−k 件手套中选 m−2×k 件手套的方案数,也就是 Cn−km−2×k。然后补上每一件手套都有左右手两种可能,就是再乘 2m−2×k。
最后放出结论,答案为:
{(Cnk×Cn−km−2×k×2m−2×k)mod(109+7)0, m−2×k≥0;, otherwise.
组合数和 2 的幂用递推公式预处理即可,数据范围再大组合数可以用模意义下的乘法逆元或者 Lucas 定理处理。时空复杂度 O(n2)。
T2
显然本题为树形 dp。按照树形 dp 的套路,我们令根为 1,ans(i) 为以 x 为根的子树中的最长美丽路径长度,dp(i) 为以 x 为根的子树且路径的一端为 x 的最长美丽路径长度,则答案为 ans(1)。容易得到转移方程:
dp(x)=⎩⎨⎧1y∈sonxandc(x)=c(y)max{dp(y)+1}, sonx=∅;, otherwise.
ans(x)={1max{y∈sonxmax{ans(y)},maxlen+seclen+1}, sonx=∅;, otherwise.
其中 maxlen,seclen 分别为异色儿子 y 中 dp(y) 的(非严格)最大、次大值。
翻译:若节点 x 为叶子节点,则 dp(x)=ans(x)=1;否则 dp(x) 为其所有异色子节点 y 中最大的 dp(y)+1,ans(x) 为其所有子节点 y 中最大的 ans(y),再与其所有异色子节点 y 中 dp(y) 的(非严格)最大、次大值之和加一取最大值。
用 dfs 转移,时间复杂度 O(n)。
后记
估分 90pts 以上嘿嘿。
看了官网答案,vocal,I AK GESP 8级!!!
有帮助,赞一个