我排第几个
时间限制：1000 ms | 内存限制：65535 KB
难度：3
- 描述
-
现在有"abcdefghijkl”12个字符，将其所有的排列中按字典序排列，给出任意一种排列，说出这个排列在所有的排列中是第几小的？
- 输入
- 第一行有一个整数n（0<n<=10000）;
随后有n行，每行是一个排列； - 输出
- 输出一个整数m，占一行，m表示排列是第几位；
- 样例输入
-
3 abcdefghijkl hgebkflacdji gfkedhjblcia
- 样例输出
-
1 302715242 260726926
- 来源
- [苗栋栋]原创
- 上传者
- 苗栋栋
-
#include <cstdio> #include <cstring> int jc[13]={0, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600}; int main() { char normal[13]="abcdefghijkl"; int t; scanf("%d", &t); while(t--) { int v[13]; memset(v, 0, sizeof(v)); char str[13]; scanf("%s", str); int len=strlen(str); int sum=0; for(int i=0; i<len; i++) { v[str[i]-'a']=1; int d=0; int p=str[i]-'a'; for(int k=p-1; k>=0; k--) if(v[k]==0) d++; int j=i+1; int t=12-j; //printf("%d ", j+t); sum=sum+d*jc[t]; } printf("%d ", sum+1); } return 0; }
#include <cstdio> #include <cstring> char str[15]; typedef long long LL; LL jc[]={1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600}; int len= 12; LL kangtuo(char c[]) { LL sum =0, k; for(int i=0; i< len; i++) { k =0; for(int j=i+1; j< len; j++) if(c[j] <c[i]) k++; sum += k* jc[len-i-1]; } return sum; } int main() { int t; scanf("%d", &t); getchar(); while(t--) { gets(str); LL num= kangtuo(str); printf("%lld ", num+1); } }
第几是谁？
时间限制：3000 ms | 内存限制：65535 KB难度：3- 描述
- 现在有"abcdefghijkl”12个字符，将其按字典序排列，如果给出任意一种排列，我们能说出这个排列在所有的排列中是第几小的。但是现在我们给出它是第几小，需要你求出它所代表的序列.
- 输入
- 第一行有一个整数n（0<n<=10000）;
随后有n行，每行是一个整数m，它代表着序列的第几小； - 输出
- 输出一个序列，占一行，代表着第m小的序列。
- 样例输入
-
3 1 302715242 260726926
- 样例输出
-
abcdefghijkl hgebkflacdji gfkedhjblcia
#include <cstdio> #include <cstring> typedef long long LL; LL jc[]={1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600}; char c[15]= {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l'}; char s[15]; int main() { int t; scanf("%d", &t); while(t--) { memset(s, ' ', sizeof(s)); strcpy(s, c); LL m; scanf("%lld", &m); LL temp= m-1; for(int i=0; i <12; i++) { LL id= temp/jc[12-i-1]; printf("%c", s[id]); for(int j=id; j< 12- i; j++) s[j]=s[j+1]; temp -= id*jc[12-i-1]; } printf(" "); } return 0; }