首页 > 代码库 > lightoj 1060 - nth Permutation(组合数+贪心)
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(组合数+贪心)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。