1023 - Discovering Permutations PDF (English) Statistics ForumTime Limit: 0.5 second(s) Memory Limit: 32 MBIn this problem you have to find the permutations using the first N English capital letters. Since there can be many permutations, you have to print the first K permutations.
InputInput starts with an integer T (≤ 100), denoting the number of test cases.
Each case contains two integers N, K (1 ≤ N ≤ 26, 1 ≤ K ≤ 30).
OutputFor each case, print the case number in a line. Then print the first K permutations that contain the first N English capital letters in alphabetical order. If there are less than K permutations then print all of them.
Sample InputOutput for Sample Input23 810 10Case 1:ABCACBBACBCACABCBACase 2:ABCDEFGHIJABCDEFGHJIABCDEFGIHJABCDEFGIJHABCDEFGJHIABCDEFGJIHABCDEFHGIJABCDEFHGJIABCDEFHIGJABCDEFHIJG
解题思路: 全排列模板改进一下，直接过。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<string> using namespace std; char a[26]={'A','B','C','D','E','F','G', 'H','I','J','K','L','M','N', 'O','P','Q','R','S','T','U', 'V','W','X','Y','Z'}; int T,n,k,cnt; string str[130]; bool permutation(int num){ if(num>=n){ int i;int sum; sum = 0; str[cnt] = a; str[cnt][n] = '\0'; // cout<<str[cnt]<<endl; cnt++; if(cnt>=120) return false; return true; } for(int i=num;i<n;i++){ swap(a[num],a[i]); if(!permutation(num+1)) return false; //这里直接返回后没执行下面的swap, 所以下一个case的时候要先把a[]重新排好序。 swap(a[num],a[i]); } return true; } int main(){ scanf("%d",&T); for(int t=1;t<=T;t++){ cnt = 0; scanf("%d%d",&n,&k); printf("Case %d:\n",t); sort(a,a+26); permutation(0); sort(str,str+cnt); for(int i=0;i<min(cnt,k);i++) { for(int j=0;j<n;j++) cout<<str[i][j]; cout<<endl; } // 用全排列的STL的写法。 // do{ // for(int i=0;i<n;i++) printf("%c",a[i]); // printf("\n"); // cnt++; // }while(next_permutation(a,a+n)&&(k>cnt)); } return 0; } View Code
转载于:https://www.cnblogs.com/yuanshixingdan/p/5551450.html
