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

时间:2024-12-04 15:06:14

小明有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(-);
const int mod=;
const int maxn=1e5+;
typedef long long ll;
vector<string> v;//用来储存满足条件的情况
vector<string>::iterator it;
int main(){
string str="aaabbbbccccc";
int cnt=;
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 ;
}

答案:1170