Codeforces Round 921 (Div. 2)
内容提要
A. 我们应有尽有！是关于生成一个最多包含 k 个不同字母且长度为 n 的字符序列。解决方案是重复输出这 k 个字母 n 次。B. 一个平衡的问题集？是关于找到从将给定值 x 分成 n 部分所得的 n 个数的最大可能最大公约数 (gcd)。解决方案是找到一个可以分成 n 部分的 x 的因子。C. 我们真的应有尽有了吗？是问题 A 的反面。任务是找到一个不是给定字符串子序列的字符串。解决方案是从左到右选择每个字母的最后一次出现。D. 好旅程是关于在选择具有一定亲密度的朋友对后计算预期得分。解决方案涉及计算选择每对的概率以及每次选择后的得分增加。
延伸解读
题目A与C的互补关系
A题要求构造一个序列，使得所有长度为n、最多k种字母的字符串都是它的子序列，解法是重复输出k个字母n次。C题则相反，给定一个字符串，要求找出一个不是其子序列的字符串，解法是从左到右取每个字母的最后一次出现。两题从正反两面考察了子序列的构造与判定，理解这种互补性有助于掌握子序列相关问题的常见思路。
B题中gcd与因子的转化
B题要求将x拆成n份，使它们的最大公约数最大。关键观察是：若所有部分都有因子d，则它们的和x也必有因子d，因此答案一定是x的因子。于是只需枚举x的因子，检查是否能分成至少n份（即x/d >= n），取最大的可行d。这一转化将复杂的拆分问题简化为因子枚举，是数论题中常见的技巧。
D题期望的线性累加
D题中，每次随机选两人，若为朋友则获得当前亲密度积分，并使该对亲密度+1。单次选中某对朋友的概率为2/(n*(n-1))，因此每次选择后，每对朋友的亲密度期望增加该概率值。利用期望的线性性质，可以将k次选择的总期望拆分为每对朋友独立贡献的累加，最终化简为关于初始亲密度和概率的表达式，再通过逆元计算。
Q&A
如何生成一个长度为n且最多包含k种不同字母的字符串序列？
可以通过重复输出这k个字母n次来生成所需的字符串序列。
如何计算将一个数值x拆分成n份的最大公约数？
最大公约数是x的因子，因此可以找到一个可以分成n份的x的因子。
如何找到一个不满足给定字符串子序列的字符串？
可以选择每个字母的最后一次出现，确保生成的字符串不是给定字符串的子序列。
在选择朋友对后如何计算期望得分？
期望得分通过计算每对朋友的亲密度和选择概率来得出。
题目A和题目C的主要区别是什么？
题目A要求生成一个包含k种字母的字符串，而题目C要求找到一个不包含给定字符串子序列的字符串。
如何处理选择朋友对后的亲密度增加？
每次选择后，选中的朋友的亲密度会增加1，这影响了后续的期望得分计算。
