时间戳

首页 > 技术文章 > [蓝桥杯2015初赛]手链样式

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

-Ackerman 2020-01-29 20:56 原文

题目链接：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);
}

 

推荐阅读