UVa 10098: Generating Fast

本文主要是介绍UVa 10098: Generating Fast，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题要求按字典序生成字符串的全排列，不可重复（但字符可以重复，且区分大小写）。

基本思路是先对输入的字符串按字典序排序，然后从第一位开始递归，从所有输入的字符中选出一个填充，然后再选第二位......具体实现看代码。

要注意的是最后的输出方式，不小心的话会莫名其妙的WA，详情见代码。

我的解题代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <string>
#include <algorithm>
using namespace std;char s[15],ss[15];
int N;int cmp(const void *a, const void *b)
{return *(char *)a-*(char *)b;
}void print_permutation(int cur, int len)
{if(cur==len)	//满足此条件则ss已经填满，输出{for(int i=0; i<len; i++) cout << ss[i]; cout << endl;	//这里用cout << ss << endl; 提交就WA了，天知道怎么回事 = - =return ;}for(int i=0; i<len; i++) if(!i || s[i]!=s[i-1])	//判断是否与上一个待选字符是相同的，如果相同就跳过{int c1=0,c2=0;for(int j=0; j<len; j++) if(s[j]==s[i]) c1++;for(int j=0; j<cur; j++) if(ss[j]==s[i]) c2++;if(c2<c1)	//分别对s和ss中s[i]出现的次数计数，只要c2<c1，就还可以使用s[i]放入ss中{ss[cur]=s[i];print_permutation(cur+1,len);}}
}int main()
{cin >> N;while(N--){cin >> s;int len = strlen(s);qsort(s,len,sizeof(char),cmp);	//按字典序对s排序print_permutation(0,strlen(s));cout << endl;}return 0;
}

这篇关于UVa 10098: Generating Fast的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---