记GESP八级202409（AK祭

userId_undefined

暑 假 神（开学祭

秩序白银

2024-09-13 17:43:56

发布于：上海

122阅读
0回复
0点赞

宣？
T1 证明已补。

Upd on 2024/9/13:估分无误，静待上榜。

直接看编程题。话不多说，上题面。

T1：手套配对

T2：美丽路径

T1

本题为数学题，但是直接去推式子还是有一定难度的。

实际上可以瞪眼法先推一个“看起来比较正确”的式子。这个时候大概率会有问题，可以再用 dfs 打一张绝对正确的表（我用的是 n=5,m∈[1,10],k∈[1,5]n=5,m\in[1,10],k\in[1,5] 的表）。随后看看式子和表有什么区别（比如多乘了 22 的几次方，少了一项组合数之类的。）

相信我这么写大家都不会同意的，所以补个场后证明。

首先一个显然的结论：当 m<2×km<2\times k 时，无可行方案，因为 kk 对手套至少需要选择 2k2k 件手套才够。

排除这种情况，我们逐点考虑。首先在 nn 对手套中选择完整 kk 对的方案数为 CnkC_n^k。还剩下 m−2×km-2\times k 件手套是可选的，而这些手套可以从剩下的 n−kn-k 对手套中选择。左右手比较难办，我们暂时设剩下这些手套都只有左手，那么方案数就要再乘上 n−kn-k 件手套中选 m−2×km-2\times k 件手套的方案数，也就是 Cn−km−2×kC^{m-2\times k}_{n-k}。然后补上每一件手套都有左右手两种可能，就是再乘 2m−2×k2^{m-2\times k}。

最后放出结论，答案为：

{(Cnk×Cn−km−2×k×2m−2×k) mod (109+7), m−2×k≥0;0, otherwise.\begin{cases} \left(C^k_n\times C^{m-2\times k}_{n-k}\times 2^{m-2\times k}\right)\bmod (10^9+7)&\text{,}\ m-2\times k\geq 0\text{;} \\ 0\quad&\text{, otherwise.} \end{cases}

组合数和 22 的幂用递推公式预处理即可，数据范围再大组合数可以用模意义下的乘法逆元或者 Lucas 定理处理。时空复杂度 O(n2)O(n^2)。

T2

显然本题为树形 dp。按照树形 dp 的套路，我们令根为 11，ans(i)ans(i) 为以 xx 为根的子树中的最长美丽路径长度，dp(i)dp(i) 为以 xx 为根的子树且路径的一端为 xx 的最长美丽路径长度，则答案为 ans(1)ans(1)。容易得到转移方程：

dp(x)={1, sonx=∅;max⁡y∈sonxand⁡c(x)≠c(y){dp(y)+1}, otherwise.dp(x)=\begin{cases} 1 & \text{,}\ son_x=\varnothing\text{;} \\ \max\limits_{y\in son_x\operatorname{and}c(x)\neq c(y)}\{dp(y)+1\} \quad &\text{, otherwise.} \end{cases}

ans(x)={1, sonx=∅;max⁡{max⁡y∈sonx{ans(y)},maxlen+seclen+1}, otherwise.ans(x)=\begin{cases} 1 & \text{,}\ son_x=\varnothing\text{;} \\ \max\{\max\limits_{y\in son_x}\{ans(y)\},maxlen+seclen+1\} \quad &\text{, otherwise.} \end{cases}

其中 maxlen,seclenmaxlen,seclen 分别为异色儿子 yy 中 dp(y)dp(y) 的（非严格）最大、次大值。

翻译：若节点 xx 为叶子节点，则 dp(x)=ans(x)=1dp(x)=ans(x)=1；否则 dp(x)dp(x) 为其所有异色子节点 yy 中最大的 dp(y)+1dp(y)+1，ans(x)ans(x) 为其所有子节点 yy 中最大的 ans(y)ans(y)，再与其所有异色子节点 yy 中 dp(y)dp(y) 的（非严格）最大、次大值之和加一取最大值。

用 dfs 转移，时间复杂度 O(n)O(n)。

后记

估分 90pts90pts 以上嘿嘿。

看了官网答案，vocal，I AK GESP 8级！！！

userId_undefined
去预览
0/2000

全部评论 8

热门讨论