蓝桥杯 2015省赛 C/C++ A T7

知识点

有重复元素的圆排列与环排列的计数问题

全排列+特殊去重

题目

手链样式

小明有3颗红珊瑚，4颗白珊瑚，5颗黄玛瑙。
他想用它们串成一圈作为手链，送给女朋友。
现在小明想知道：如果考虑手链可以随意转动或翻转，一共可以有多少不同的组合样式呢？

请你提交该整数。不要填写任何多余的内容或说明性的文字。

思路

通过全排列生成所有可能的情况，在排除重复情况时，需要考虑到旋转和翻转，考虑字符串，s’是否为s的旋转等价于s’是否为(s+s)的子串，故通过find判断是否为已有序列的子串，若不是，则加入s+s和(s+s).reverse，每成功加入一次ans++。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

int ans = 0;

int main()
{
    string s = "aaabbbbccccc";
    vector<string> v1;
    do
    {
        // 排除重复，对于v1中每个元素进行检查，如果存在s的旋转或者翻转，则跳过
        int i = 0;
        for (; i < v1.size(); i++)
        {
            if (v1[i].find(s) != string::npos)
                break;
        }
        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;
}