lightoj 1060 - nth Permutation（组合数+贪心）

题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1060

题解：如果是不重复数的这些操作可以用康托展开的逆来求，如果是有重复数字出现康托展开的逆就要稍微变一下。要除去自身个数的组合数具体看一代码，暴力就行

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

typedef long long ll;

ll f[30];

char s[30];

int num[30];

void init() {

    f[1] = f[0] = 1;

    for(int i = 2 ; i <= 20 ; i++) f[i] = f[i - 1] * i;

}

int main() {

    int t , Case = 0;

    scanf("%d" , &t);

    init();

    while(t--) {

        int n;

        scanf("%s %d" , s , &n);

        memset(num , 0 , sizeof(num));

        int len = strlen(s);

        for(int i = 0 ; i < len ; i++) {

            num[s[i] - 'a']++;

        }

        ll Max = f[len];

        for(int i = 0 ; i < 26 ; i++) if(num[i]) Max /= f[num[i]];//最多的组合种类

        printf("Case %d: " , ++Case);

        if(Max < n) { printf("Impossible\n"); continue; }

        for(int i = 0 ; i < len ; i++) {

            for(int j = 0 ; j < 26 ; j++) {

                if(!num[j]) continue;

                ll gg = f[len - i - 1];

                num[j]--;

                for(int l = 0 ; l < 26 ; l++) if(num[l]) gg /= f[num[l]];

                if(gg >= n) {

                    putchar(j + 'a');

                    break;

                }//如果取当第j个字母为当前位的组合数大于n那么肯定符合。有种贪心的思想。

                n -= gg;//否则就是下一个字母这里之所以要减去是因为要求递增下去前面的组合都不行到下一组合肯定要减去上一个组合数。

                num[j]++;

            }

            if(i == len - 1) printf("\n");

        }

    }

    return 0;

}

巴特西

lightoj 1060 - nth Permutation（组合数+贪心）

最新文章

热门文章