Shiroha白羽的博客
·
Codeforces Round 1079 (Div. 2)
💡
原文中文，约3100字，阅读约需8分钟。
📝
内容提要
本文讨论了友好数、数组与排列、博弈问题和美丽对的数量等编程题，提供了解题思路和代码实现，强调通过枚举和条件判断解决问题的方法。
🎯
关键要点
- 友好数问题：给定等式 y - d(y) = x，求可能的 y 的数量。
- 通过枚举 d(y) 的值，计算 y = x + d(y)，并验证合法性。
- 数组与排列问题：检查是否可以通过相邻值的拷贝将排列 p 变为数组 a。
- 核心思路是确保 p 中的值在 a 中出现时，左边的值不再出现。
- 博弈问题：Alice 和 Bob 通过选择数字 p 和 q 进行博弈，判断胜负。
- Bob 胜出的条件是 p 和 q 满足特定公式，Alice 可以避免失败。
- 美丽对问题：寻找满足 a_i * a_j = j - i 的下标对数量。
- 使用暴力法遍历每个位置，寻找可能的配对，优化内循环次数。
❓
延伸问答
友好数问题的主要思路是什么？
通过枚举 d(y) 的值，计算 y = x + d(y)，并验证 y 的合法性。
如何判断数组 p 是否可以变为数组 a？
需要确保 p 中的值在 a 中出现时，左边的值不再出现，以避免覆盖。
Alice 和 Bob 的博弈中，Bob 胜出的条件是什么？
Bob 胜出的条件是 p 和 q 满足特定公式，Alice 可以避免失败。
美丽对问题的解法是什么？
使用暴力法遍历每个位置，寻找满足 a_i * a_j = j - i 的下标对。
在友好数问题中，d(y) 的最大值是多少？
d(y) 的最大值为 90，因为 y 的十进制位数有限。
如何优化美丽对问题的内循环次数？
通过调整外层和内层循环的顺序，减少内循环的遍历次数。
➡️
