(六省)蓝桥真题 手链样式

news/2024/11/2 17:30:09/

手链样式

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

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

圆(环)排列:围成一个圆,圆旋转一下就是同一个排列。因此从n个中取r个的圆排列数为

项链排列:项链是立体的,存在翻转的情况,项链排列数为

但是翻转对于左右对称的情况是没有影响的,不需要除以2。

所以项链排列的公式为:

(引用自:https://www.cnblogs.com/lemonbiscuit/p/7776008.html)

方法二:全排列,去掉相同的

在v中存翻转前后的两种结果,对任意新的一种组合方式,在v中进行匹配查找。

do...while结构

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */vector<string> v;//存储已出现的情况 int main(int argc, char** argv) 
{string str = "aaabbbbccccc";int count = 0;v.clear();do{vector<string>::iterator it;for(it = v.begin(); it != v.end(); it++){//从*it的0位置开始找,返回第一次成功匹配str的首字符在*it中的位置if((*it).find(str,0) != string::npos)  break;//如果在已有的里面能找到,即是重复的,判断下一个 }if(it != v.end()) continue;string str2 = str+str;//可以任意转动 v.push_back(str2); reverse(str2.begin(), str2.end());     //需要algorithm头文件 可以翻转 v.push_back(str2);  count++;}while(next_permutation(str.begin(),str.end())) ;cout<<count<<endl;return 0;
}
//  1170 

while...结构

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */vector<string> v;//存储已出现的情况 int main(int argc, char** argv) 
{string str = "aaabbbbccccc";int count = 1;v.clear();string str2 = str+str;v.push_back(str2);reverse(str2.begin(),str2.end());v.push_back(str2); while(next_permutation(str.begin(),str.end())) {vector<string>::iterator it;for(it = v.begin(); it != v.end(); it++){//从*it的0位置开始找,返回第一次成功匹配str的首字符在*it中的位置if((*it).find(str,0) != string::npos)  break;//如果在已有的里面能找到,即是重复的,判断下一个 }if(it != v.end()) continue;string str2 = str+str;//可以任意转动 v.push_back(str2); reverse(str2.begin(), str2.end());     //需要algorithm头文件 可以翻转 v.push_back(str2);  count++;};cout<<count<<endl;return 0;
}
//  1170 

方法三:

在v外的字符串str2中存储旋转和翻转的结果,在str2中匹配查找v中组合

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */vector<string> v;//存储已出现的情况 int main(int argc, char** argv) 
{string str = "aaabbbbccccc";int count = 1;int flag = 0;v.push_back(str);while(next_permutation(str.begin(),str.end())){flag = 0;//转动string str2 = str + str;vector<string>::iterator it;for(it = v.begin(); it != v.end(); it++){if(str2.find(*it) != string::npos){flag = 1;//找到了该种组合方式,不再查找 break;}}//翻转if(flag == 0){//转动后,在v中仍没有找到相同组合 reverse(str2.begin(),str2.end());for(it = v.begin(); it != v.end(); it++){if(str2.find(*it) != string::npos){flag = 1;break;}}}//继转动后,翻转后,在v中仍没有找到相同组合,确定为一种新组合,添加进v if(flag == 0){v.push_back(str);count++;} }cout<<count<<endl;return 0;
}
//  1170 

方法四、map<string,bool> mp 代替 vector 和 flag

#include <iostream>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */map<string,bool> mp;//存储已出现的情况 
int colorNum[3] = {2,4,5};//假定从红色开始放置,所以红色已经少了一个 
char color[4] = "rwy";//红色,白色,黄色bool pd(string str)
{int len = str.size();str += str;//旋转 for(int i = 0; i < len; i++){//取str中的第i个(包括第i个)开始的len个字符 string temp = str.substr(i,len);if(mp[temp] == 1)return 0;//如果在mp中存在,则不增加计数,返回0 }return 1;
}int dfs(string str)
{if(!colorNum[0] && !colorNum[1] && !colorNum[2]){//所有颜色的数量都为0了,得出了一个新的排列 if(pd(str) == 0) return 0;//该排列所属组合已经计数了,返回0,跳出本层dfs reverse(str.begin(),str.end());//翻转 if(pd(str) == 0)return 0;//该排列的翻转排列所属组合已经计数了,返回0,跳出本层dfs //该排列的旋转和翻转所属组合均未计数,添加进mp,计数加一,返回1 ,跳出本层dfsmp[str] = true; return 1;}int count = 0;for(int i = 0; i < 3; i++){if(!colorNum[i]) continue;//该颜色数量为0,结束本层循环,直接进行i+1层循环 string temp = str;colorNum[i]--; temp += color[i];count += dfs(temp);colorNum[i]++;}return count;
} 
int main(int argc, char** argv) 
{mp.clear();cout<<dfs("r")<<endl;return 0;
}
//  1170 

 


http://www.ppmy.cn/news/670811.html

相关文章

蓝桥 手链样式

小明有3颗红珊瑚&#xff0c;4颗白珊瑚&#xff0c;5颗黄玛瑙。 他想用它们串成一圈作为手链&#xff0c;送给女朋友。 现在小明想知道&#xff1a;如果考虑手链可以随意转动或翻转&#xff0c;一共可以有多少不同的组合样式呢&#xff1f; 请你提交该整数。不要填写任何多余的…

English trip EM3 LP 4B Home Design Relationship Teacher:Ryan

课上内容&#xff08;Lesson&#xff09; "green home" 1. saves energy 2. is good for the environment(plants, land, water) If you want your house to be more "green". How can you do it? 1. Unplug your TV, PC, and microwave 2. Use CFL lig…

Django Vue corsheaders跨域问题

跨域问题 记录一下在我自己的django-vue项目里面出现的跨域问题 我的项目之前一直是在本地跑的&#xff0c;因为需要上线测试&#xff0c;所以我就运行在同一个vlan里面 ip段&#xff1a;192.168.1.0/24 突然发现存在跨域问题&#xff0c;我django的接口访问被拦截了。 检查…

【性能测试】轻商城-项目实战2

目录 昨日回顾 今日目标 1、性能测试脚本编写 2、 性能测试环境准备 &#xff08;1&#xff09;特点 &#xff08;2&#xff09;如何达成性能测试环境与生产环境一致 &#xff08;3&#xff09;测试数据的准备(插入10万条数据) 3、执行测试脚本 &#xff08;1&#xf…

[蓝桥杯2015初赛]手链样式-思维+next_permutation枚举(好题)

题目描述 小明有3颗红珊瑚&#xff0c;4颗白珊瑚&#xff0c;5颗黄玛瑙。 他想用它们串成一圈作为手链&#xff0c;送给女朋友。 现在小明想知道&#xff1a;如果考虑手链可以随意转动或翻转&#xff0c;一共有多少不同的组合样式&#xff1f; 输出 请你输出该整数。不要输出任…

科技产品也要讲时尚 P9红蓝新色彰显独特风格

一直以来&#xff0c;科技给人的感觉都是冰冷、深奥的&#xff0c;无论是离我们生活很远的太空航天还是就在我们生活之中的智能手机。一直追求极致体验的华为&#xff0c;正在一定程度上改变人们对科技的一贯严肃的看法。在保持极致科技、极致品质的同时&#xff0c;华为的一系…

故宫珍宝馆完成二期改陈 珍贵红珊瑚盆景揭开面纱

中新网客户端北京1月28日电(记者 上官云 应妮)28日&#xff0c;记者从故宫博物院获悉&#xff0c;故宫博物院珍宝馆二期改陈项目完成&#xff0c;计划于春节前正式对公众开放。一批珍贵文物即将亮相&#xff0c;其中包括铜镀金嵌珐琅海棠式盆红珊瑚盆景等。 中新社记者 杜洋 摄…

【ASP.NET Core】EF Core - “导航属性”

“导航属性”是实体框架用得算是比较频繁的概念。 首先&#xff0c;它是类型成员&#xff0c;其次&#xff0c;他是属性&#xff0c;这不是 F 话&#xff0c;而是明确它的本质。那么&#xff0c;什么场景下会用到导航属性呢&#xff1f;重点就落在“导航”一词上了&#xff0c;…