Shiroha白羽的博客
·
Codeforces Round 921 (Div. 2)
原文中文，约2500字，阅读约需6分钟。
📝
内容提要
A. 我们应有尽有！是关于生成一个最多包含 k 个不同字母且长度为 n 的字符序列。解决方案是重复输出这 k 个字母 n 次。B. 一个平衡的问题集？是关于找到从将给定值 x 分成 n 部分所得的 n 个数的最大可能最大公约数 (gcd)。解决方案是找到一个可以分成 n 部分的 x 的因子。C. 我们真的应有尽有了吗？是问题 A 的反面。任务是找到一个不是给定字符串子序列的字符串。解决方案是从左到右选择每个字母的最后一次出现。D. 好旅程是关于在选择具有一定亲密度的朋友对后计算预期得分。解决方案涉及计算选择每对的概率以及每次选择后的得分增加。
🎯
关键要点
-
题目A：生成一个长度为n，最多包含k种不同字母的字符串序列，解决方案是重复输出这k个字母n次。
-
题目B：将一个数值x拆分成n份，求它们的最大公约数，解决方案是找到x的因子。
-
题目C：寻找一个不满足给定字符串子序列的字符串，解决方案是选择每个字母的最后一次出现。
-
题目D：计算在选择具有一定亲密度的朋友对后，期望得分，解决方案涉及计算选择每对的概率及得分增加。
❓
延伸问答
如何生成一个长度为n且最多包含k种不同字母的字符串序列？
可以通过重复输出这k个字母n次来生成所需的字符串序列。
如何计算将一个数值x拆分成n份的最大公约数？
最大公约数是x的因子，因此可以找到一个可以分成n份的x的因子。
如何找到一个不满足给定字符串子序列的字符串？
可以选择每个字母的最后一次出现，确保生成的字符串不是给定字符串的子序列。
在选择朋友对后如何计算期望得分？
期望得分通过计算每对朋友的亲密度和选择概率来得出。
题目A和题目C的主要区别是什么？
题目A要求生成一个包含k种字母的字符串，而题目C要求找到一个不包含给定字符串子序列的字符串。
如何处理选择朋友对后的亲密度增加？
每次选择后，选中的朋友的亲密度会增加1，这影响了后续的期望得分计算。
🏷️
