本文主要是介绍uva 11027 - Palindromic Permutation(数论)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
| Problem A | Palindromic Permutation |
| Time limit: 1 second | |
Given a string of characters, we can permute the individual characters to make new strings. We can then order these strings into alphabetical order.
For example the string ‘abba’ gives rise to the following 6 distinct permutations in alphabetical order.
aabb 1
abab 2
abba 3
baab 4
baba 5
bbaa 6
Of these 6 permutations, only 2 are palindromes (A string that reads the same when read backwards). These are ‘abba’ and ‘baab’.
Given a string, you have to find out the nth palindrome in the sorted list of all permutations. For the above case ‘abba’ is the 1st and ‘baab’ is the 2nd palindrome.
Input
The first line of input gives the number of test cases. Each case contains a string, consisting of lowercase letters only, followed by a space separated positive integer n (n < 2^31). The length of the string will be at most 30.
Output
For each case, output the case number followed by the nth palindrome, but if the total number of palindromes is less than n output ‘XXX’ without the quotes. Follow the sample for exact format.
| Sample Input | Output for Sample Input |
| 3 abba 1 abba 2 abba 3 | Case 1: abba Case 2: baab Case 3: XXX
|
题意：给定一个字符串，找出他可以重新排列出得字典序第n大的回文串，如果没有输出XXX。
思路：先判断能不能组成，如果能，取出回文串前半部分，然后一个个字母放过去，该字母能放的条件为，除去该字母，后面字母能组成的情况数小于n。如果不放，要放后面的字母，n就减去当前字母放头的情况数，放到末尾，最后输出字符串即可，注意过程中阶乘计算要用long long 因为最多要用到14！超过了范围
代码：
#include <stdio.h>
#include <string.h>int t, tt = 1, i, save[30], judge, len;
long long n, jc[35];
char str[35], ans[35], c;long long JC(long long n) {if (n == 0 || n == 1)return 1;elsereturn n * JC(n - 1);
}long long sum(long long num) {long long ans = jc[num];for (int i = 0; i < 26; i ++)ans /= jc[save[i]];return ans;
}void init() {c = '#';memset(save, 0, sizeof(save));judge = 0;scanf("%s%lld", str, &n); len =strlen(str);for (i = 0; i < len; i ++) {save[str[i] - 'a'] ++;if (save[str[i] - 'a'] % 2)judge ++;elsejudge --;}
}void solve() {for (int i = 0; i < 26; i ++) {if (save[i] % 2)c = i + 'a';save[i] /= 2;}len /= 2;if (n > sum(len)) {ans[0] = ans[1] = ans[2] = 'X';ans[3] = '\0';return;}int l = 0;while (l != len) {for (int i = 0; i < 26; i ++) {if (save[i] == 0) continue;save[i] --;long long t = sum(len - l - 1);if (n > t) {n -= t;save[i] ++;}else {ans[l ++] = i + 'a';break;}}}if (c != '#')ans[l ++] = c;for (int j = len - 1; j >= 0; j --)ans[l ++] = ans[j];ans[l] = '\0';
}
int main() {for (i = 0; i <= 30; i ++) {jc[i] = JC(i);}scanf("%d", &t);while (t --) {init();printf("Case %d: ", tt ++);if (judge > 1)printf("XXX\n");else {solve();printf("%s\n", ans);}}return 0;
}这篇关于uva 11027 - Palindromic Permutation(数论)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
