蓝桥杯2015年第六届真题-手链样式

题目

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

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

题解

考点：全排列函数，STL——string

对这12颗珠子进行全排，对于每一种排列方式如果已经出现过，则不统计，如果之前没出现过，则统计下来。最后输出统计的个数。

注意几点：

1. 见到环形，第一件事就是扩充为二倍表示；
2. “虑手链可以随意转动或翻转”，说明逆序匹配和错位匹配都是可以的。逆序匹配就是如果str逆序后仍包含substr，则也算是匹配；错位匹配就是一般的包含关系，如果str中包含substr则说明匹配；
3. str.find(substr) != string::npos的含义是判断str中是否存在substr，为真表示匹配成功，反之失败；（查找字符串a是否包含子串b，不是用strA.find(strB) > 0 而是 strA.find(strB) != string:npos）.

用STL的函数写起来确实会轻松不少，否则还需要自己手写很多循环用于判断字符串的包含关系。

虽然时间复杂度大约在 12! 左右，但是要敢写，毕竟是个填空。

代码

#include
using namespace std;

string str = "aaabbbbccccc";
vector v; // 如果枚举的某个手链不与v中的任何一个匹配，则将其变形后加入v 

int main()
{
	do {
		int i = 0;
		for (;i