手鏈樣式

小明有3顆紅珊瑚，4顆白珊瑚，5顆黃瑪瑙。

他想用它們串成一圈作為手鏈，送給女朋友。

現在小明想知道：如果考慮手鏈可以隨意轉動或翻轉，一共可以有多少不同的組合樣式呢？

請你提交該整數。

不要填寫任何多余的內容或說明性的文字。

Ideas

這是一個排列組合問題，一共有 12 個位置，可以先從中選出 3 個，放紅珊瑚，然后從剩下的 9 個中選出 4 個放白珊瑚，剩余的 5 個位置放黃瑪瑙。

這道題只是一道填空題，所以可以用一些語言自帶的全排列函數，但是需要做一些去重的操作。

手鏈可以隨意轉動，相當于將排列進行右移操作，所以將上面的結果除以 12。

手鏈還能夠翻轉，也就是說必須保證對稱軸兩邊的石頭不同類型數量相等，所以必須由紅珊瑚和黃瑪瑙作為對稱軸。

對稱軸兩邊分別放 5 個石頭，從 5 個位置里面選 2 個放白珊瑚，然后從剩下的 3 個位置中選 2 個放黃瑪瑙。

考慮到翻轉的情況，將上面的結果除以 2，然后再加上一個對稱的操作。所以這道題其實是可以通過純數學計算的方式得出結果的。

不過作為一名勤勤懇懇的碼農，不寫點代碼總覺得難受，所以下面的代碼是通過全排列+去重的方式實現的。

Code

C++

#include <iostream> #include <string> #include <algorithm> #include <vector>using namespace std;int main(int argc, const char *argv[]) {string s = "aaabbbbccccc";vector<string> v1;int ans = 0;do {//排出重復，對于v1中的每個元素進行檢查，如果存在s的旋轉或者翻轉，則跳過int i = 0;for (; i < v1.size(); ++i) {if (v1[i].find(s) != string::npos)break;}//s不可用的情況if (i != v1.size())continue;string s2 = s + s;v1.push_back(s2);//用于判斷旋轉的情況reverse(s2.begin(), s2.end());v1.push_back(s2);//將s的翻轉放入vector中ans++;} while (next_permutation(s.begin(), s.end()));cout << ans << endl;return 0; }

Python

from itertools import permutationsif __name__ == '__main__':ans, cnt = set(), 0nums = ['1', '1', '1', '2', '2', '2', '2', '3', '3', '3', '3', '3']for item in permutations(nums):string = ''.join(item)if string not in ans: # 如果這種樣式之前已經遇到過print(string)string2 = string + stringfor i in range(len(nums)):ans.add(string2[i:i + 12])string2 = string2[::-1] # 考慮翻轉的情況for i in range(len(nums)):ans.add(string2[i:i + 12])cnt += 1print(cnt)

Answer: 1170

總結

以上是生活随笔為你收集整理的2015年第六届蓝桥杯 - 省赛 - C/C++大学A组 - G. 手链样式的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。