题解

141 条题解

  • 1
    @ 2017-01-19 21:40:51

    这道题目的基础算法就是**康托展开**
    康托展开有着这样的定义——
    把一个整数X展开成如下形式:
    X = a[n]×(n-1)! + a[n-1]×(n-2)! + ... + a×(i-1)! + ... + a[2]×1! + a[1]×0!
    其中,a为整数,并且0<=a<i(1<=i<=n)
    可以通过这样的方式求得它的全排列组合,是一种快速便捷、简单便捷的方法。
    至于具体的一些细节,你们可以自行搜索一下。
    这里,我给出C++的程序(如果使用C的朋友,只要将头文件改成stdio.h即可),希望对大家有所帮助。
    **特别注意**:
    ***我的程序中有输入优化,标准的写法应该差不多是这样的**
    ```
    int s()
    {
    char ch=getchar();
    int x=ch-'0';
    for(;(ch=getchar())>='0'&&ch<='9';)
    x=x*10+ch-'0';
    return x;
    }

    **我的程序中有输出优化,标准的写法应该差不多是这样的**

    bool w(int r)
    {
    if(r>9)
    w(r/10);
    putchar(r%10+'0');
    return 1;
    }
    ```
    我的输入输出优化根据题目需要稍作了修改.
    这里,我申明几点。
    在一些void的函数内可以尝试改成bool甚至int的返回值,并不影响操作,还更贴近scanf/printf的方式。
    输入输出优化是帮助程序在一定程度上节省时间和空间,特别是空间,效果更明显(对,是空间)。

    评测结果

    编译成功
    foo.cpp: In function 'bool permutation(int)':
    foo.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
    }
    ^
    foo.cpp: In function 'int main()':
    foo.cpp:42:13: warning: iteration 24 invokes undefined behavior [-Waggressive-loop-optimizations]
    k[i]=i;
    ~~~~^~
    foo.cpp:41:20: note: within this loop
    for(R int i=1;i<=25;i++)
    ~^~~~
    测试数据 #0: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 536 KiB, score = 10
    测试数据 #5: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    测试数据 #6: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    测试数据 #7: Accepted, time = 0 ms, mem = 540 KiB, score = 10
    Accepted, time = 0 ms, mem = 540 KiB, score = 80

    代码

    #include<cstdio>
    #define R register
    #define ll long long
    ll n,m,a[25],k[25];
    ll s()
    {
    R char ch=getchar();
    R ll x=ch-'0';
    for(;(ch=getchar())>='0'&&ch<='9';)
    x=x*10+ch-'0';
    return x;
    }
    bool w(R ll r)
    {
    if(r>9)
    w(r/10);
    putchar(r%10+'0');
    return 1;
    }
    bool print()
    {
    for(int i=n;i;i--)
    w(a[i]),putchar(' ');
    return 1;
    }
    bool permutation(int w)
    {
    if(w==0)
    return print();
    R long long tmp,cnt=1;
    for(R int i=2;i<w;i++) cnt*=i;
    for(a[w]++;m>cnt;m-=cnt,a[w]++);
    tmp=a[w];
    a[w]=k[a[w]];
    for(R int i=tmp;i<n;i++)
    k[i]=k[i+1];
    permutation(w-1);
    }
    int main()
    {
    for(R int i=1;i<=25;i++)
    k[i]=i;
    n=s();m=s();
    permutation(n);
    return 0;
    }

    希望对大家有所帮助,RP++!

  • 0
    @ 2018-10-27 12:12:08
    #include <iostream>
    #include <cstdlib>
    #include <cstdio>
    #include <map>
    #include <vector>
    #include <cstring>
    #include <string>
    #include <algorithm>
    #include <cmath>
    #include <iomanip>
    #include <set>
    #include <cstring>
    
    using namespace std;
    
    vector<int> e;
    vector<int> res;
    int n;
    long long m;
    long long fac[21];
    
    int c_div(long long a, long long b){
        int res = 0;
        for(; b * res < a; res++);
        return res;
    }
    
    int main(){
        cin >> n >> m; fac[0] = 1;
        for(int i = 1; i <= n; i++) e.push_back(i);
        for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * (long long)i;
        long long r = m;
        for(int i = 1; i <= n; i++){
            int p = c_div(r, fac[n - i]);
            res.push_back(e[p - 1]);
            e.erase(e.begin() + p - 1);
            r -= (long long)(p - 1) * fac[n - i];
        }
        for(int i = 0; i < n; i++) cout << res[i] << " ";
        cout << endl;
        return 0;
    }
    
  • 0
    @ 2014-08-15 11:29:23

    #include<cstring>
    #include<iostream>
    using namespace std;
    bool b[101];
    int i,n,a;
    unsigned long long f,m,j,s,k;
    unsigned long long aa(int x)
    {
    int c;
    unsigned long long ss=1;
    for(c=1;c<=x;c++)
    ss*=c;
    return ss;
    }
    main()
    {
    cin>>n>>m;
    memset(b,1,sizeof(b));
    for(i=n;i>=1;i--)
    {
    f=aa(i-1);
    j=m/f;
    s=0;
    if(m!=j*f)
    k=j+1;
    else
    k=j;
    if(k==0)
    k=i;
    for(a=1;a<=n;a++)
    if(b[a])
    {
    s++;
    if(s==k)
    {
    cout<<a;
    if(i!=1)
    cout<<" ";
    b[a]=0;
    break;
    }
    }
    m-=j*f;
    }
    }

  • 0
    @ 2014-03-16 19:58:36

    模拟 水过

    var b:array[0..100]of boolean;n,i,a:longint;f,m,j,s,k:qword;
    function js(x:longint):qword;
    var c:longint;ss:qword;
    begin
    ss:=1;
    for c:=1 to x do
    ss:=ss*c;
    exit(ss);
    end;
    begin
    readln(n,m);fillchar(b,sizeof(b),true);
    for i:=n downto 1 do
    begin
    f:=js(i-1);
    j:=m div f;
    s:=0;
    if m<>j*f then k:=j+1 else k:=j;
    if k=0 then k:=i;
    for a:=1 to n do
    if b[a] then
    begin
    inc(s);
    if s=k then
    begin
    write(a);
    if i<>1 then write(' ');
    b[a]:=false;
    break;
    end;
    end;
    m:=m-j*f;
    end;
    writeln;
    end.

  • 0
    @ 2013-10-26 18:09:39

    {康托展开逆运算}
    var
    jie : array[1..19] of int64;
    m : int64;
    n,i,j : longint;
    have : array[1..20] of longint;
    begin
    read(n,m);
    jie[1] := 1;
    for i := 2 to n-1 do jie[i] := jie[i-1] * int64(i);
    for i := 1 to n do have[i] := i;
    m := m-1;
    for j := 1 to n-1 do
    begin
    write(have[m div jie[n-j] + 1],' ');
    for i := m div jie[n-j] + 1 to n-j do have[i] := have[i+1];
    m := m mod jie[n-j];
    end;
    writeln(have[1]);
    end.

  • 0
    @ 2012-07-21 10:08:04

    要用点排列组合的知识,

    如果这个数为 3xxx...x (共n位) ,那这就在 2*(n-1)! ~ 3*(n-1)! 这范围之间

    以此类推出第k位来,

    仔细调试便能写出正确的程序

  • 0
    @ 2010-04-09 18:55:16

    #include

    using namespace std;

    int number[20]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

    int paixu(int a)

    {

    int b=1;

    for(int i=1;i

  • 0
    @ 2010-04-06 20:27:17

    var

    a:array[0..20] of int64=(1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000,20922789888000,355687428096000,6402373705728000,121645100408832000,2432902008176640000);

    c,b:array[1..20] of longint;

    n,k,i,i1,i2,s,y,j:longint;

    begin

    readln(n,k);

    s:=0;

    fillchar(c,sizeof(c),0);

    k:=k-1;

    j:=n-1;

    for i:=1 to n do begin

    y:=k div a[j];

    for i1:=1 to n do

    if c[i1]=0 then begin

    s:=0;

    for i2:=1 to n do

    if c[i2]=0 then

    if i1>i2 then s:=s+1;

    if s=y then begin

    write(i1);

    if in then write(' ');

    c[i1]:=1;

    break;

    end;

    end;

    k:=k mod a[j];

    dec(j);

    end;

    end.

    康托展开的逆运算

    这个内容我没有在网上找到,不过实现起来并不麻烦,主要还是自己的话应该有很多不严谨之处敬请谅解

    这个方法还是用例子来说比较好

    例1 {1,2,3,4,5}的全排列,并且已经从小到大排序完毕

    (1)找出第96个数

    首先用96-1得到95

    用95去除4! 得到3余23

    用23去除3! 得到3余5

    用5去除2!得到2余1

    用1去除1!得到1余0

    有3个数比它小的数是4

    所以第一位是4

    有3个数比它小的数是4但4已经在之前出现过了所以是5(因为4在之前出现过了所以实际比5小的数是3个)

    有2个数比它小的数是3

    有1个数比它小的数是2

    最后一个数只能是1

    所以这个数是45321

    (2)找出第16个数

    首先用16-1得到15

    用15去除4!得到0余15

    用15去除3!得到2余3

    用3去除2!得到1余1

    用1去除1!得到1余0

    有0个数比它小的数是1

    有2个数比它小的数是3 但由于1已经在之前出现过了所以是4(因为1在之前出现过了所以实际比4小的数是2)

    有1个数比它小的数是2 但由于1已经在之前出现过了所以是3(因为1在之前出现过了所以实际比3小的数是1)

    有1个数比它小得数是2 但由于1,3,4已经在之前出现过了所以是5(因为1,3,4在之前出现过了所以实际比5小的数是1)

    最后一个数只能是2

    所以这个数是14352

    • @ 2013-11-03 09:38:11

      k可以用longint读?

    • @ 2016-11-08 19:39:57

      感谢

  • 0
    @ 2010-03-13 01:36:43

    #include

    #include

    using namespace std;

    /*

    厦门一中信息学小组leap.ahead

    VIJOS P1092,题解

    */

    long long int jc(long long int a)

    {

    long long int b = a;

    a--;

    while(a>0)

    {

    b*=a;

    a--;

    }

    return b;

    }

    int main()

    {

    int n;

    int t = 1;

    int k = 1;

    int p = 0;

    long long int m;

    cin >> n >> m;

    int flaga[n+1];

    m--; //step 1

    while((n-t)>=1)

    {

    //cout

  • 0
    @ 2009-11-10 16:36:14

    康托展开的逆运算

    核心代码

    m:=m-1;//第k小排列的序号为k-1

    for i:= 1 to n do

    begin

    x = m div (n-i)!//表示数列中有x个数比ans[i]大

    m:= m mod (n-i)!//把第i位开始的方案删除

    ans[i]:=find(x);//从未用过的数中计算ans[i];

    flag[ans[i]]:=true//把得到的ans[i]标记为已经使用

    end;

  • 0
    @ 2009-11-08 12:45:10

    水题

  • 0
    @ 2009-11-09 18:05:52
  • 0
    @ 2009-11-01 12:07:45

    靠,完全没注意n=20,然后通过率就又下了一点......

    不是全排列...

  • 0
    @ 2009-10-29 00:10:50

    AC 70 庆祝一下

  • 0
    @ 2009-10-26 22:29:26

    刚开始用全排列写的,一个一个找下去,会超时。

    于是,我来到了题解,看了整页还是不明白,百度百科上面的也看不懂,这个叫康托展开..

    刚开始把m:=m-1;

    每次按顺序做这么几件事:1. k:=(m div a[n-i])+1; 2.从前往后找

    第k个未使用过的数并标记为已使用,输出 3. m:=m mod a[n-i];

    4. 从前往后将未使用过的输出

    Program P1092;

    Const maxn=21;

    Var n,m,i,j,k:longint;

    a:array[0..maxn] of int64;

    f:array[0..maxn] of boolean;

    begin

    readln(n,m);

    a[1]:=1;

    for i:=2 to n do a[i]:=a*i;

    fillchar(f,sizeof(f),true);

    i:=1;

    m:=m-1;

    while (m0) and (i0 do

    begin

    inc(j);

    if f[j] then dec(k);

    end;

    f[j]:=false;

    write(j,' ');

    m:=m mod a[n-i];

    inc(i);

    end;

    for j:=1 to n do if f[j] then write(j,' ');

    readln;

    end.

  • 0
    @ 2009-10-18 11:57:59

    program p1092;

    VAR

    i,j,n,m,k,s,p:longint;

    c:array[0..100]of 0..1;

    f:array[1..100]of int64;

    begin

    readln(n,m);fillchar(c,sizeof(c),1);

    f[1]:=1; c[0]:=0;

    for i:=2 to n do f[i]:=f*i;

    p:=n;

    repeat

    dec(p);

    k:=m div f[p];

    m:=m mod f[p];

    i:=0;s:=0;

    while s0 then inc(i);

    while c[i]=0 do inc(i);

    c[i]:=0;

    write(i,' ');

    until m=0;

    for i:=n downto 1 do

    if c[i]=1 then write(i,' ');

    writeln;

    end.

  • 0
    @ 2009-10-17 09:58:44

    能不能把康拓排序倒过来写!?

  • 0
    @ 2009-10-11 16:21:16

    额 还以为是全排列呢.....

信息

ID
1092
难度
5
分类
组合数学 点击显示
标签
(无)
递交数
4374
已通过
1361
通过率
31%
上传者