2021年寒假每日一題，2017~2019年的省賽真題，
本文內容由倪文迪（華東理工大學計算機系軟體192班）和羅勇軍老師提供，
文章目錄
- 1、題目大意
- 2、我的嘗試
- 3、我的放棄
- 4、大神的手算
題目：魔方狀態 http://oj.ecustacm.cn/problem.php?id=1319
??2017年藍橋杯軟體類省賽C++語言大學A組第3題，一道填空題，
1、題目大意
??一個二階魔方，有6個面，但是只涂了3種顏色：
??（1）前面、下面：涂橙色
??（2）右面、左面：涂綠色
??（3）上面、后面：涂黃色
??然后隨便你打亂它，問一共有多少種不同狀態，
??如果兩個狀態經過魔方的整體旋轉后，各個面的顏色都一致，則認為是同一狀態，
2、我的嘗試
??既然是填空題，看有沒有投機取巧的辦法，
??正常的二階魔方，有6種顏色，每個角塊都不同，共8種角塊，以一個角塊不動作為參考角塊，其他7個角塊都能任意轉換方向，有
7
!
7!
7!種情況，
??7個角塊排列的時候，只有6格角塊可以自由選擇方向，第7個角塊的方向取決于前6個（玩過魔方都知道，其他7塊固定時，1個角塊不能在原地轉動），有
3
6
3^6
36種情況，
??所有情況一共有：
7
!
×
3
6
=
3
,
674
,
160
7!\times3^6 = 3,674,160
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
3\times3=9
3×3=9種情況，
??然后再放2個三色角塊312…
??…
??本教師已經暈了，做不下去了，
??偷看了答案，是229878，
229878
=
43
×
11
×
3
5
×
2
229878=43\times 11\times3^5\times2
229878=43×11×35×2，估計不是一個簡單的排列吧，
??據說能用Burnside引理做，哪位大神做了請告訴我，讓大家一起學學，
3、我的放棄
??既然用數學方法想不通，就只能用計算機暴力求解了，基本思路是：模擬魔方的旋轉，把每次新的旋轉結果看成一個狀態，然后用BFS搜索所有的狀態，看一共有多少種，當然，還要對狀態判重，
??不過，這是一個代碼很復雜（很惡心）的模擬題，比賽的時候做，簡直是浪費生命、浪費其他題得分的機會，對省賽這種得獎面大的比賽，還是放棄吧，
??最后是倪文迪說的話：“這道題目初看是排列組合，但由于其涂色的特殊性，不方便由組合數學解決，只能考慮終極搜索+模擬…對于這幾個塊形成的魔方，定義它為一種狀態，我們需要做的就是模擬魔方的旋轉，并判定當前狀態是否與之前出現過的狀態重復，然后我們建一維陣列，人為規定狀態表達，填入到陣列中，再判重，”
??參考一位大神寫的模擬，非常佩服（小聲說一句，運行時間很長很長，不要誤會死機了）：https://blog.csdn.net/qq_35222235/article/details/79725363
4、大神的手算
??本博客發布之后，本校大神杭業晟（獲得第十一屆藍橋杯全國總決賽A組一等獎）表示，他去學了一下Burnside引理，然后手算了這個題，
??先學這個：Burnside引理
??下面是杭業晟的手算：“我發現立方體有24個置換群…最后再除3是因為只有1/3是能夠轉的出來的”，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/245331.html
標籤：AI