倪文迪带你学蓝桥杯2021寒假每日一题:1.5日第3题

2021年寒假每日一题,2017~2019年的省赛真题。
本文内容由倪文迪(华东理工大学计算机系软件192班)和罗勇军老师提供。

@

题目:魔方状态 http://oj.ecustacm.cn/problem.php?id=1319
  2017年蓝桥杯软件类省赛C++语言大学A组第3题,一道填空题。

1、题目大意

  一个二阶魔方,有6个面,但是只涂了3种颜色:
  (1)前面、下面:涂橙色
  (2)右面、左面:涂绿色
  (3)上面、后面:涂黄色
  然后随便你打乱它,问一共有多少种不同状态。
  如果两个状态经过魔方的整体旋转后,各个面的颜色都一致,则认为是同一状态。

2、我的尝试

  既然是填空题,看有没有投机取巧的办法。
  正常的二阶魔方,有6种颜色,每个角块都不同,共8种角块。以一个角块不动作为参考角块,其他7个角块都能任意转换方向。有(7!)种情况。
  7个角块排列的时候,只有6格角块可以自由选择方向,第7个角块的方向取决于前6个(玩过魔方都知道,其他7块固定时,1个角块不能在原地转动),有(3^6)种情况。
  所有情况一共有:(7! imes3^6 = 3,674,160)
  正常魔方是很简单的。
  本题只有三种颜色,却复杂得多。倪文迪说用排列组合很难做,本教师不相信。结果浪费半天时间之后,被迫同意他的说法。
  为了找出到底有几种不同的角块,本教师用白纸做了一个破六面体,观察好久,终于发现:
  本题的二阶魔方,涂3种颜色,只有4种不同的角块,每种2个。设三种颜色是1、2、3,这4种角块是:132、312、113、322。
  这4种角块,有三种颜色的角块132、312,和两种颜色的角块113、322。
  问有几种排列?下面尝试排列一下。
  先看2个三色角块132,可以并排放、对角放、反对角放(互相看不见),共3种,每种有3个旋转,共(3 imes3=9)种情况。
  然后再放2个三色角块312......
  ......
  本教师已经晕了,做不下去了。
  偷看了答案,是229878,(229878=43 imes 11 imes3^5 imes2),估计不是一个简单的排列吧。
  据说能用Burnside引理做,哪位大神做了请告诉我,让大家一起学学。

3、我的放弃

  既然用数学方法想不通,就只能用计算机暴力求解了,基本思路是:模拟魔方的旋转,把每次新的旋转结果看成一个状态,然后用BFS搜索所有的状态,看一共有多少种。当然,还要对状态判重。
  不过,这是一个代码很复杂(很恶心)的模拟题,比赛的时候做,简直是浪费生命、浪费其他题得分的机会。对省赛这种得奖面大的比赛,还是放弃吧。
  最后是倪文迪说的话:“这道题目初看是排列组合,但由于其涂色的特殊性,不方便由组合数学解决。只能考虑终极搜索+模拟......对于这几个块形成的魔方,定义它为一种状态,我们需要做的就是模拟魔方的旋转,并判定当前状态是否与之前出现过的状态重复。然后我们建一维数组,人为规定状态表达,填入到数组中,再判重。”
  参考一位大神写的模拟,非常佩服(小声说一句,运行时间很长很长,不要误会死机了):https://blog.csdn.net/qq_35222235/article/details/79725363

4、大神的手算

  本博客发布之后,本校大神杭业晟(获得第十一届蓝桥杯全国总决赛A组一等奖)表示,他去学了一下Burnside引理,然后手算了这个题。
  先学这个:Burnside引理
  下面是杭业晟的手算:“我发现立方体有24个置换群...最后再除3是因为只有1/3是能够转的出来的”。

原文地址:https://www.cnblogs.com/luoyj/p/14241709.html