Shiroha白羽的博客
·
Codeforces Round#706(Div. 2)-Let's Go Hiking
💡
原文中文，约3000字，阅读约需8分钟。
📝
内容提要
这篇文章讨论了一个关于数组的游戏，两人依次选择下标。第一个人选择的下标值必须小于原值，第二个人则相反。文章分析了如何选择下标以确保第一个人获胜，强调构造一个峰的必要性，使得左右坡长度相等且为奇数，以避免被第二个人阻断选择，并提供了相应的代码实现。
🎯
关键要点
- 游戏中有两个玩家，依次选择数组中的下标，要求选择的下标不相同。
- 第一个玩家选择的下标值必须小于原值，第二个玩家则必须选择大于原值的下标。
- 为了确保第一个玩家获胜，必须构造一个峰，使得左右坡长度相等且为奇数。
- 如果第一个玩家选择单调递增的子串，第二个玩家可以选择相邻的下标来阻断第一个玩家的选择。
- 峰的左右坡长度相等且为奇数是确保第一个玩家获胜的关键。
- 代码实现中，使用数组记录每个下标的左坡和右坡长度，并计算符合条件的峰的数量。
❓
延伸问答
这个游戏的基本规则是什么？
游戏中有两个玩家，依次选择数组中的下标，要求选择的下标不相同，第一个玩家选择的下标值必须小于原值，第二个玩家则必须选择大于原值的下标。
第一个玩家如何确保获胜？
第一个玩家必须构造一个峰，使得左右坡长度相等且为奇数，以避免被第二个玩家阻断选择。
为什么单调递增的子串会导致第一个玩家失败？
因为第二个玩家可以选择与第一个玩家相邻的下标来阻断第一个玩家的选择，从而使其无法继续游戏。
构造峰的左右坡长度有什么要求？
峰的左右坡长度必须相等且为奇数，这是确保第一个玩家获胜的关键。
代码实现中如何记录下标的坡长度？
代码中使用数组记录每个下标的左坡和右坡长度，并计算符合条件的峰的数量。
如何判断一个峰是否有效？
一个峰被认为有效当其左右坡长度相等且为奇数，并且没有其他坡比它更大或相等。
➡️
