Shiroha白羽的博客
·
Codeforces Round 941 (Div. 2)
原文中文，约3800字，阅读约需9分钟。
📝
内容提要
本文解答了四个问题：牌的交换、矩阵填充、石头堆游戏和构造数列。
🎯
关键要点
-
A. 牌的交换：有n张牌，允许选择k张相同的牌弃掉并摸进k-1张任意牌，求最少剩下多少张牌。
-
思路：通过暴力循环找可以进行操作的点数，判断是否可以操作。
-
B. 矩阵填充：给定一个矩阵，允许选择两个相同颜色的节点，将其组成的矩阵内的颜色变为相同，问是否能使整个矩阵颜色一致。
-
思路：若对角顶点颜色相同，则可以一次操作完成；若边的两端颜色相同且对边存在相同颜色的点，则可以通过两次操作完成。
-
C. 石头堆游戏：Alice和Bob轮流从n个石头堆中取石子，问最后谁赢。
-
思路：通过排序石头堆，分析谁能获得先手权，决定游戏的胜负。
-
D. 构造数列：需要构造一个数列，使得对于k无法找到子序列和为k，而对于其他i能找到。
-
思路：构造数列时，确保小于k的值之和不超过k，并加入k+1以避免组合出k。
❓
延伸问答
牌的交换问题的核心思路是什么？
通过暴力循环找可以进行操作的点数，判断是否可以操作，能操作就操作。
如何判断矩阵是否可以填充成同一颜色？
若对角顶点颜色相同，则可以一次操作完成；若边的两端颜色相同且对边存在相同颜色的点，则可以通过两次操作完成。
石头堆游戏中，谁能赢得游戏的关键是什么？
核心在于谁拿到了第一个先后手交换权，谁就能操纵整个游戏。
构造数列时，如何确保无法找到子序列和为k？
确保小于k的值之和不超过k，并加入k+1以避免组合出k。
在牌的交换问题中，如何计算剩余牌的数量？
每次操作可以整来k-1张任意牌，循环判断并操作，最后统计剩余牌的数量。
矩阵填充问题中，哪些情况无法完成填充？
如果对角顶点颜色不同，且边的两端颜色也不满足条件，则无法完成填充。
🏷️
