蓝桥杯第六届省赛手链样式 STL

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

分析：这个题首先一定要理解题意，转动和翻转是个什么意思，转动就是我们所得到的的排列是个环，即起点不固定，具体点说即使1234和2341是一种方式（3421也一样）。翻转就是，这个排列是个立体的，可以上下左右翻转，具体点说即
1 1
2 3 和 3 2 是一样的（左右翻转），弄清了题意，就能事半功倍。
4 4

如果没有转动和翻转两个要求，就是直接全排列，有转动和翻转就得小心重复了

转动的话我们可以把str复制一份，比如abcd,我们变成abcdabcd，只要在这个序列里找到满足的情况就可以了

翻转的话可以用reverse()函数，用一个vector来储存满足的情况，用string情况下的next_permutation()函数进行全排列，如果vector中没有满足的，就将复制后的和翻转后的加进vector中

具体实现看代码

#include <bits/stdc++.h>
using namespace std;
const double pi=acos(-1);
const int mod=10007;
const int maxn=1e5+7;
typedef long long ll;
vector<string> v;//用来储存满足条件的情况 
vector<string>::iterator it;
int main(){
    string str="aaabbbbccccc";
    int cnt=0;
    do{
    for(it=v.begin();it!=v.end();it++){
        if((*it).find(str)!=string::npos)//如果这种情况已经存在了，就需要跳过 
        break;
    }
    if(it!=v.end())continue;//跳过
    //如果找到一种不存在的情况，就要把它转动和翻转的情况一起加进去，以免重复    
    string str2=str+str;//这个是转动
    v.push_back(str2);
    reverse(str2.begin(),str2.end()); 
    v.push_back(str2);
    cnt++;
    }while(next_permutation(str.begin(),str.end()));//用来求字符串的全排列
    cout<<cnt<<endl; 
    return 0;
}

答案：1170

蓝桥杯第六届省赛 手链样式 STL

相关推荐

蓝桥杯第六届省赛手链样式 STL