7 POJ 1256 Anagram
发布时间：2020-12-13 20:08:52 所属栏目：PHP教程 来源：网络整理
导读：给1个字符串包括大小写字符，规定'A''a''B''b'...'Z''z'，求该字符串的全排列。 用裸的dfsmap判重 写了1遍超时了，那种机灵的dfs方法没有怎样看懂。。 最开始用的setnext_permutation，太年轻，也超时了。。。 应用1个next_permutation()函数便可，algorithm
|
给1个字符串包括大小写字符，规定'A'<'a'<'B'<'b'<...<'Z'<'z'，求该字符串的全排列。 用裸的dfs+map判重 写了1遍超时了，那种机灵的dfs方法没有怎样看懂。。 最开始用的set+next_permutation，太年轻，也超时了。。。 应用1个next_permutation()函数便可，<algorithm>头文件 注意要先将字符串sort1遍，然后next_permutation()也要把比较函数cmp传进去，原来都不知道可以3个参数的。。
#include<cstdio>
#include<set>
#include<cstring>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
char s[20];
bool cmp(char a,char b)
{
if(a>='a'&&a<='z'&&b>='a'&&b<='z') return a<b;
if(a>='A'&&a<='Z'&&b>='A'&&b<='Z') return a<b;
if(abs(a-b)==32) return a<b;
if(a>='A'&&a<='Z') a+=32;
if(b>='A'&&b<='Z') b+=32;
return a<b;
}
int main()
{
int T,len;
scanf("%d",&T);
while(T--)
{
scanf("%s",s);
len=strlen(s);
sort(s,s+len,cmp);
do
{
puts(s);
}while(next_permutation(s,cmp));
}
return 0;
}
用裸的dfs+map判重 写了1遍超时了，那种机灵的dfs方法没有怎样看懂。。 最开始用的set+next_permutation，太年轻，也超时了。。。 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |