poj 1256 Anagram—next_permutation的神奇应用

题意：给你一条字符串，让你输出字符串中字符的全排列，输出的顺序要按它给的奇葩的字典序。

题解：要输出全排列，暴力dfs可以过，但要注意题目的字典序以及相同字符的情况。如果用next_permutation()处理可以简单很多；我是先将字典序"A a B b...Z z"的每个字母赋予一个值，即从1 2 3...52。然后将给的字符串全部转换成对应的数值后，用next_permutation()进行全排列(当然题目给的字典序有一定规律，所以也可以直接给next_permutation()写个cmp函数直接处理字符串)。

 /**

 * @author Wixson

 */

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <queue>

 #include <stack>

 #include <vector>

 #include <utility>

 #include <map>

 #include <set>

 const int inf=0x3f3f3f3f;

 const double PI=acos(-1.0);

 const double EPS=1e-;

 using namespace std;

 typedef long long ll;

 typedef pair<int,int> P;

 char str[];

 char book[];

 int a[];

 void init()

 {

     for(int i=;i<;i++)

     {

         if(i%) book[i]='a'+i/;

         else book[i]='A'+i/;

     }

 }

 int main()

 {

     //freopen("input.txt","r",stdin);

     init();

     int t,n;

     scanf("%d",&t);

     while(t--)

     {

         scanf("%s",str);

         n=strlen(str);

         for(int i=;i<n;i++)

         {

             if(str[i]>='A'&&str[i]<='Z') a[i]=(str[i]-'A')*;

             else a[i]=(str[i]-'a')*+;

         }

         //

         sort(a,a+n);

         do

         {

             for(int i=;i<n;i++) putchar(book[a[i]]);

             putchar('\n');

         }while(next_permutation(a,a+n));

     }

     return ;

 }

巴特西

poj 1256 Anagram—next_permutation的神奇应用

最新文章

热门文章