《反转棋盘》解答.pdfVIP

栏目主持人 吴文虎 清华大学计算机系教授，博士生导师，国际信息学奥林匹克比赛原中国队总教练，… 七次带 队参赛，共赢得四十二块金牌，主要研究方向为语音识别及语言理解等。 区 《反转棋盘 解答 ■文／邬晓钧 我 那么对于所影响的行列中1的个数的奇偶性来说，与没有作的总数。另一方面，如果某一行或某一列反转了2次，反转是一样的。更进一步，如果某一行或某一列反转了偶 数次，则对于棋盘中1的个数的奇偶性的影响与没有反转 是～样的，如果某一行或某一列反转了奇数次，则对于棋 盘中1的个数的奇偶性的影响与反转一次是一样的。因此， 题目要求最少的反转次数，必然是某些行和列只反转一次， 而其它行和列不反转。 我们用Ro表示棋盘初始情况下1的个数为奇数的行 的集合，Re表示初始情况下1的个数为偶数的行的集合， Co表示初始情况下1的个数为奇数的列的集合，Ce表示 初始情况下1的个数为偶数的列的集合。我们定义当X表 示某一行或某一列时，O(x)表示该行或该列的反转次数， 当x表示一个集合时，o(x)表示集合中每一元素反转次数 的总和，则根据棋盘最终每行每列都恰好有偶数个1的要 求可知： O(Co UCe)+O(roj)+1为偶数，其中ro；∈Ro， O(Co U Ce)+O(rej)为偶数，其中re．∈Re， O(RoU Re)+o(cq)+1为偶数，其中COI∈Co， O(Ro U Re)+O(ce~)为偶数，其中rel∈Re， 且O(ro；)、O(re )、O(co,)~O(cej)的取值都为0或1。 [ E co[=) 熙 根据上面的式子可以知道，对于任意ro ∈Ro，O(ro；) 的值都相同，对于任意re ∈Re，O(re )的值都相同，且不 等于O(rei)；对于任意co ∈Co，O(coi)的值都相同，对于 任意re ∈Re，O(ce~)的值都相同，且不等于O(co．)。 由于o(x)的奇偶性除了与O(x)，X X有关外，还与 fXf(集合X的元素个数)有关，因此下面分两种情况讨论