真题解析│蓝桥杯省赛真题之魔方状态
-
-
梁老师
北京小升初老师～
0 人点赞了该文章 · 81 浏览
2017年蓝桥杯软件类省赛C++语言大学A组第3题“魔方状态”，一道填空题。
* 本文内容由倪文迪（华东理工大学计算机系软件192班）和罗勇军老师提供。题目链接：魔方状态
http://oj.ecustacm.cn/problem.php?id=1319
一个二阶魔方，有6个面，但是只涂了3种颜色：
（1）前面、下面：涂橙色
（2）右面、左面：涂绿色
（3）上面、后面：涂黄色
然后随便你打乱它，问一共有多少种不同状态。如果两个状态经过魔方的整体旋转后，各个面的颜色都一致，则认为是同一状态。
既然是填空题，看有没有投机取巧的办法。正常的二阶魔方，有6种颜色，每个角块都不同，共8种角块。以一个角块不动作为参考角块，其他7个角块都能任意转换方向。有7!种情况。
7个角块排列的时候，只有6格角块可以自由选择方向，第7个角块的方向取决于前6个（玩过魔方都知道，其他7块固定时，1个角块不能在原地转动），有36种情况。所有情况一共有：7! × 36 = 3 , 674 , 160。本题只有三种颜色，却复杂得多。倪文迪说用排列组合很难做，本教师不相信。结果浪费半天时间之后，被迫同意他的说法。为了找出到底有几种不同的角块，本教师用白纸做了一个破六面体，观察好久，终于发现：本题的二阶魔方，涂3种颜色，只有4种不同的角块，每种2个。设三种颜色是1、2、3，这4种角块是：132、312、113、322。这4种角块，有三种颜色的角块132、312，和两种颜色的角块113、322。先看2个三色角块132，可以并排放、对角放、反对角放（互相看不见），共3种，每种有3个旋转，共3 × 3 = 9 种情况。偷看了答案，是229878，229878 = 43 × 11 × 35 × 2，估计不是一个简单的排列吧。据说能用Burnside引理做，哪位大神做了请告诉我，让大家一起学学。既然用数学方法想不通，就只能用计算机暴力求解了，基本思路是：模拟魔方的旋转，把每次新的旋转结果看成一个状态，然后用BFS搜索所有的状态，看一共有多少种。当然，还要对状态判重。不过，这是一个代码很复杂（很恶心）的模拟题，比赛的时候做，简直是浪费生命、浪费其他题得分的机会。对省赛这种得奖面大的比赛，还是放弃吧。最后是倪文迪说的话：“这道题目初看是排列组合，但由于其涂色的特殊性，不方便由组合数学解决。只能考虑终极搜索+模拟…对于这几个块形成的魔方，定义它为一种状态，我们需要做的就是模拟魔方的旋转，并判定当前状态是否与之前出现过的状态重复。然后我们建一维数组，人为规定状态表达，填入到数组中，再判重。”参考一位大神写的模拟，非常佩服（小声说一句，运行时间很长很长，不要误会死机了）：https://blog.csdn.net/qq_35222235/article/details/79725363华东理工大学大神杭业晟（获得第十一届蓝桥杯全国总决赛A组一等奖）表示在学习了一下Burnside引理后手算了这个题。下面是杭业晟的手算：“我发现立方体有24个置换群…最后再除3是因为只有1/3是能够转的出来的”。
免责声明:
本文由 梁老师
原创发布于 家长帮 ，著作权归作者所有。
全部 0条评论