首页 > 代码库 > NYOJ139---我排第几个

NYOJ139---我排第几个

我排第几个

时间限制:1000 ms  |  内存限制:65535 KB
难度:3
描述

现在有"abcdefghijkl”12个字符,将其所有的排列中按字典序排列,给出任意一种排列,说出这个排列在所有的排列中是第几小的?

输入
第一行有一个整数n(0<n<=10000);
随后有n行,每行是一个排列;
输出
输出一个整数m,占一行,m表示排列是第几位;
样例输入
3
abcdefghijkl
hgebkflacdji
gfkedhjblcia
样例输出
1
302715242
260726926
来源
[苗栋栋]原创
上传者

苗栋栋



康拓展开的应用


/*************************************************************************
    > File Name: nyoj139.cpp
    > Author: ALex
    > Mail: 405045132@qq.com 
    > Created Time: 2015年01月12日 星期一 21时22分04秒
 ************************************************************************/

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int fn[14];
char str[14];
bool vis[30];

int main()
{
	fn[0] = 1;
	for (int i = 1; i <= 12; ++i)
	{
		fn[i] = fn[i - 1] * i;
	}
	int t;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%s", str);
		long long ans = 0;
		memset (vis, 0, sizeof(vis));
		for (int i = 0; i < 12; ++i)
		{
			int cur = str[i] - 'a' + 1;
			int cnt = cur - 1;
			vis[str[i] - 'a' + 1] = 1;
			for (int j = 0; j < i; ++j)
			{
				if (str[j] < str[i] && vis[str[j] - 'a' + 1])
				{
					--cnt;
				}
			}
			ans += (long long)fn[12 - i - 1] * cnt;
		}
		printf("%lld\n", ans + 1);
	}
	return 0;
}



NYOJ139---我排第几个