蓝桥杯搜索模拟暴力题:
题目:
手链样式
小明有 3 颗红珊瑚, 4 颗白珊瑚, 5 颗黄玛瑙.
他想用它们串成一圈作为手链, 送给女朋友.
现在小明想知道: 如果考虑手链可以随意转动或翻转, 一共可以有多少不同的组合样式呢?
思路:
这道题自己还没做出来, 其实自己分析到了转动翻转是怎么样的, 但是没有想到可以 + 本身就可以来控制转动和翻转, 然后在推是不是可以求出所有情况除以多少多少得出答案, 但是也没有推出来, 最后看了题解才知道的, 感觉自己还是很菜很菜的
全排列, 对每种情况转动, 翻转检测;
具体看代码:
- #include<iostream>
- #include<vector>
- #include<algorithm>
- using namespace std;
- #include <iostream>
- #include <string>
- #include <algorithm>
- using namespace std;
- vector<string> v;//vector 动态存储符合要求的串
- int main()
- {
- string s="aaabbbbccccc";//abc 分别代表三种颜色的珠子
- int ans=1,flag=0;
- v.push_back(s);// 最初一种情况肯定是符合条件的
- //cout<<*v.begin()<<endl;
- while(next_permutation(s.begin(),s.end()))// 全排列函数
- {
- flag=0;
- // 转动
- string s1=s+s;
- vector<string>::iterator it=v.begin();
- for(;it!=v.end();it++)
- {
- if(s1.find(*it)!=s1.npos)
- {
- flag=1;
- break;
- }
- }
- //
- if(!flag)
- {
- reverse(s1.begin(),s1.end());
- for(it=v.begin();it!=v.end();it++)
- {
- if(s1.find(*it)!=s1.npos)
- {
- flag=1;
- break;
- }
- }
- }
- if(!flag)
- {
- ans++;
- v.push_back(s);
- }
- }
- cout<<ans<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2865252.html