Shiroha白羽的博客
·
Codeforces Round 896 (Div. 2)
💡
原文中文，约8300字，阅读约需20分钟。
📝
内容提要
本文讨论了Codeforces第896轮比赛中的几道题目，包括数组异或操作、棋盘路径成本计算、矩阵MEX值求解和糖果分配问题。每道题目提供了具体的解法和代码实现。
🎯
关键要点
- A. Make It Zero: 通过异或操作将数组变为0，偶数长度数组需要2次操作，奇数长度数组需要4次操作。
- B. 2D Traveling: 在棋盘上从点a到点b的最小成本计算，利用特殊节点的0成本来优化路径。
- C. Fill in the Matrix: 构造一个n x m的矩阵，求每列的MEX值，最终结果最大为n+1或m，具体取决于n和m的关系。
- D1. Candy Party (Easy Version): 每个人必须给出2^x个糖果，计算糖果总数是否能均分，判断是否存在可能使每个人糖果数量相同的方案。
- D2. Candy Party (Hard Version): 允许每个人最多给出一个人糖果，分析差值是否符合2^x的形式，判断是否能实现糖果的均分。
❓
延伸问答
如何通过异或操作将数组变为0？
偶数长度数组需要2次操作，奇数长度数组需要4次操作。
在棋盘上计算最小成本的方法是什么？
找到距离起点最近的特殊节点和终点最近的特殊节点，计算成本并取较小值。
如何求解矩阵的MEX值？
构造一个n x m的矩阵，求每列的MEX值，最终结果最大为n+1或m，取决于n和m的关系。
糖果分配问题的简单版本有什么要求？
每个人必须给出2^x个糖果，计算糖果总数是否能均分。
糖果分配问题的难版与简单版有什么不同？
难版允许每个人最多给出一个人糖果，分析差值是否符合2^x的形式。
在Candy Party问题中，如何判断糖果是否能均分？
计算总糖果数量是否能被人数整除，并检查每个人的差值是否符合2^x的形式。
🏷️
标签
➡️
