NYOJ139---我排第几个 - c++编程基础

我排第几个

时间限制：1000 ms | 内存限制：65535 KB 难度：3

描述

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

输入第一行有一个整数n（0 随后有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 
#include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 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; }