（2015）第六届蓝桥杯省赛（软件类） C/C++ 大学A组 题解（第七题）

第七题

题目

手链样式

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

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

思路分析

     这是数论中的等价类计数问题，本题中的珊瑚相当于“项链”，只可旋转，不可翻转。

而本题中的黄玛瑙相当于“手镯”，既可以旋转，又可以翻转。

    举个例子，假设序列S中只有四个元素“abcd”,旋转后的结果为"bcda","cdba","dbac";

而翻转后的结果为“dcba”。

关键问题1：如何判断一个序列是否是旋转得来的呢？将两个序列S拼接在一起，SS的结果为“abcdabcd”,
判断旋转得到的某种排列，例如"bcda"，是否是拼接序列的一个子序列就可以。

关键问题2：如何判断一个序列是否是翻转得来的呢？将两个序列S拼接在一起(“abcdabcd”)再reverse，SS的结果为"dcbadcba"

判断翻转得到的某种排列，例如“dcba”,是否是该拼接序列逆转后的一个子序列就可以。

  

运行结果

1170

代码

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

int main(int argc, char** argv) {
	vector<string>vc;
	int sum=0;//记录不同的组合数
	string str="aaabbbbccccc";
	do{
		vector<string>::iterator it;
		for(it=vc.begin();it!=vc.end();it++){
			if((*it).find(str,0)!=string::npos){//如果找到str子串，且不到尽头· 
				break;
			}	
		}
		if(it!=vc.end()) continue;
		//可任意旋转
		string s1=str+str;
		vc.push_back(s1);//记录拼接后的组合序列，以匹配旋转序列 
		//可任意翻转 
		reverse(s1.begin(),s1.end());//记录拼接后逆转的组合序列，以匹配翻转序列
		vc.push_back(s1);
		sum++; 
	}while(next_permutation(str.begin(),str.end()));
	
	cout<<sum<<endl;
	return 0;
}

参考链接： 点击打开链接