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

题目

题解

对于语文不好的我理解“转动”和“翻转”理解了很久（狼狈.jpg）
转动：得到的排列的起点不是固定的，比如：1234和2341（或3412）是一样的。
翻转：一个圈圈，它可以上下左右翻转，比如：
 1      1
2  3  和  3   2 是一样的（左右翻转）
 4      4
步骤：先进行全排列，然后去重（转动和翻转）
转动：把string复制，如把abcd变成abcdabcd，在这个序列里找到满足的情况即可
翻转：用reverse()函数
用vector来存储满足的情况，用string情况下的next_permutation()函数进行全排列，如果vector中没有满足情况，就将复制后的和翻转后的加进vector中

代码1

#include <iostream>
#include<bits/stdc++.h>

using namespace std;

vector<string> link;

int main()
{
    string s="aaabbbbccccc";
    link.push_back(s);
    int sum=1;

    while(next_permutation(s.begin(),s.end())){
        string s2=s+s;
        //转动
        int flag=0;
        vector<string>::iterator it=link.begin();
        for(;it!=link.end();it++){
            if(s2.find(*it)!=string::npos){
                flag=1;
                break;
            }
        }
        if(!flag){
            reverse(s2.begin(),s2.end());
            for(it=link.begin();it!=link.end();it++){
                if(s2.find(*it)!=string::npos){
                    flag=1;
                    break;
                }
            }
        }
        if(!flag){
            sum++;
            link.push_back(s);
        }
    }
    cout<<sum;
    return 0;
}

代码2

#include <iostream>
#include<bits/stdc++.h>

using namespace std;

vector<string> link;

int main()
{
    string s="aaabbbbccccc";
    link.push_back(s);
    int sum=0;
    do{
        int i=0;
        for(;i<link.size();i++){
            if(link[i].find(s)!=string::npos)
                break;
        }
//排出重复，对于v1中的每个元素进行检查，如果存在s的旋转或者翻转，则跳过
        if(i!=link.size())
            continue;
        string s2=s+s;
        link.push_back(s2);
        reverse(s2.begin(),s2.end());
        link.push_back(s2);
        sum++;
    }while(next_permutation(s.begin(),s.end()));
    cout<<sum;
    return 0;
}

拓展——next_permutation(a,a+n)

在解决该问题之前先拓展一个新学的函数。
全排列函数：next_permutation(a,a+n)
next_permutation(start,end)和prev_permutation(start,end)，这两个函数的作用是一样的，区别在于前者求的是当前排列的下一个排列，后一个求的是当前排列的上一个排列，这里的前后可以理解为字典序的前后。
next_permutation函数的原型为：

bool next_permutation(iterator start, iterator end)

当当前序列不存在下一个排列时，函数返回false，否则返回true
一般是以do while(next_permutation(s.begin(),s.end()));的形式存在

char类型的next_permutation 👇

【POJ 1256】Anagram

#include <iostream>
//#include<bits/stdc++.h>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<cstdio>

using namespace std;

//字典序
int cmp(char a,char b){
    if(tolower(a)!=tolower(b))
        return tolower(a)<tolower(b);
    else
        return a<b;
}

int main()
{
    char ch[20];
    int n;
    cin>>n;
    while(n--){
        scanf("%s",ch);
        sort(ch,ch+strlen(ch),cmp);
        do{
            printf("%s\n",ch);
        }while(next_permutation(ch,ch+strlen(ch),cmp));
    }
    return 0;
}