[蓝桥杯2015初赛]手链样式

2020/01/29 20:56
阅读数 140

题目链接:http://oj.ecustacm.cn/problem.php?id=1254

 

题目描述

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

输出

请你输出该整数。不要输出任何多余的内容或说明性的文字。

 

思想:

暴力枚举,我们直接把每一次得到的串先复制拼接一下(模拟旋转)成环,再翻转一下,如果两次得到的串在已得的串里面没有就加入

 

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <math.h>
#include <cstdio>
#include <iomanip>
#include <time.h>

#define LL long long
#define INF 0x3f3f3f3f
#define ls nod<<1
#define rs (nod<<1)+1

const int maxn = 1e5 + 10 ;
const LL mod = 20010905;

std::vector<std::string> v;

int main() {
    std::string str = "aaabbbbccccc";
    int sum = 0;
    do {
        std::vector<std::string>::iterator it;
        for (it = v.begin();it != v.end();it++) {
            if((*it).find(str, 0) != std::string::npos)
            {
                break;
            }
        }
        if (it != v.end())
            continue;
        std::string str2 = str + str;  //可以任意转动的缘故
        v.push_back(str2);
        reverse(str2.begin(), str2.end());  //可以任意翻转的缘故
        v.push_back(str2);
        sum++;
    }while(next_permutation(str.begin(), str.end()));
    printf("%d\n",sum);
}

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部