【手链样式】第六届蓝桥杯省赛【C++描述，全排列】

偏执的太偏执、 2023-03-04 06:51 9阅读 0赞

问题描述：  
  小明有3颗红珊瑚，4颗白珊瑚，5颗黄玛瑙。他想用它们串成一圈作为手链，送给女朋友。  
  现在小明想知道：如果考虑手链可以随意转动或翻转，一共可以有多少不同的组合样式呢？  
  请你提交该整数。不要填写任何多余的内容或说明性的文字。

思路分析：假设这串手链初始状态为"aaabbbbccccc"，**那么我们只需要对该字符串做全排列，只是每次需要判断是否重复即可。** 不懂全排列的可以参考：[解析C++全排列][C]  
  那么重点就是如何判断重复？题干说可以随意转动和翻转，翻转很好理解：“abcde"和"edcba"表示同一种状态。  
  这里转动其实不太好理解。假设字符串原先为"abc”，那么可以随意转动的意思是：“abc”、“bca”、"cab"表示一种状态。我们用字符串来表示一条手链，实际上我们就已经给了它一个方向与顺序，但如果可以随意转动，那么每一颗珊瑚都可以充当起始位置。**我们再观察上述三个字符串，它们无一例外都出现在"abcabc"中。**  
  因此思路就很清晰了：全排列每次产生一个字符串，我们首先遍历存储字符串的容器（本题采用vector），**因为考虑翻转，所以我们需要在容器每一个字符串里面查找是否出现了当前字符串**， 没出现则计数器cnt++，同时将当前字符串的翻转以及转动都存储进容器，因为三者本质上表示同一种状态。

完整代码：

#include<bits/stdc++.h>
    using namespace std;
    
    vector<string> strs;
    int cnt = 0;
    
    int solve() { 
    	string str = "aaabbbbccccc";
    	vector<string>::iterator it;
    	do { 
    		for(it = strs.begin();it!=strs.end();++it) { 
    			if((*it).find(str) != string::npos) { 
    				break;   //说明里面已经存在过了 
    			}
    		}
    		if(it == strs.end()) { 
    			//分别处理转动和翻动
    		    string str1 = str + str;
    		    strs.push_back(str1);
    		    reverse(str1.begin(),str1.end()); 
    		    strs.push_back(str1);
    		    cnt++;
    		}else { 
    			continue;
    		}
    	}while(next_permutation(str.begin(),str.end()));
    	cout<<cnt;
    } 
    
    int main() { 
    	solve();
    	return 0;
    }

答案：1170

[C]: https://blog.csdn.net/Cyril_KI/article/details/106051259