ACM多校训练营题解：等比数列与树上DP

"ACM多校训练营题目解析" 在本次的ACM多校训练营第六场比赛中，我们涉及了几道不同类型的算法问题，包括博弈论、概率计算、动态规划和字符串处理。下面是这些题目的详细解析： A.SingingContest（歌唱比赛） 此题考察的是博弈论中的最佳策略。当选手面对对手时，他应选择权值大于对方最大值的最小值，以确保在可能的情况下赢得比赛。如果无法获胜，选手只能认输。因此，可以通过直接模拟比赛过程来解决问题。 B.EndlessPallet（无尽调色板） 这是一个概率问题，我们需要计算一棵树上的所有节点首次被染成黑色的期望时间。通过扩展公式，我们可以将问题转化为等比数列求和，其中每个项的公比是某个节点集合不被染色的概率。利用容斥原理，我们可以正向推导出每个节点集合的贡献。具体来说，对于每个子集S，其不被染色的概率是不经过集合内部节点的链数除以总链数，容斥因子是(-1)^|S|。这里可以使用动态规划来解决，设f[i][j][k][2]表示i子树中，与根相连且不在子集S内的节点构成的连通块大小为j，子树内已有k条不经过S内部节点的链，以及S大小的奇偶性。虽然看起来复杂度为O(n^7)，但实际上可以优化到O(n^5)。 C.GenerationI（一代） 这是一个组合计数问题，涉及到排列和隔板法。我们需要计算在n个位置放置k种颜色的球的所有方法，每个位置可以放置多个球。隔板法告诉我们，这样的方案数为C(n-1, k-1) * m! / (m-k)!，其中m是总的球种类数。然后，我们需要对所有可能的k进行求和。 D.Bulbasaur（宝可梦） 此题涉及到字符串处理和动态规划。我们首先注意到，单个字母在t秒后生成的字符串长度至少为2^t，因此在10秒后，单个字母生成的字符串长度将大于目标字符串T。我们可以先处理答案不超过10秒的情况，通过动态规划计算f[i][j][k]，表示经过j秒后，第i个字符演变出的字符串，进入T的KMP构造的DFA状态k后，会到达哪个状态。 以上是第六场比赛各个题目的详细解析，涵盖了博弈论、概率、动态规划和组合计数等多个核心算法知识点。理解和掌握这些问题的解决方案，对于提高编程竞赛水平和算法思维能力具有重要意义。