先声明，是康托，不是康娜，hhh

 

在我们做题中，搜索也好，动态规划也好，我们往往有时候需要用一个数字表示一种状态

 

比如有8个灯泡排成一排，如果你用0和1表示灯泡的发光情况

那么一排灯泡就可以转换为一个二进制数字了

 

比如

01100110 = 102

11110000 = 240

10101010 = 170

 

通过这些十进制数，只要把他们展开，我们就知道灯泡的状态了

 

步入正题：

康托展开就是用一个数代表一串数，把这个数展开为这串数

而康托逆展开就是把一串数转换为它对应的一个数

比如：

123  ->  0

132  ->  1

213  ->  2

231  ->  3

312  ->  4

321  ->  5

从左到右就是康托逆展开，从右到左就是康托展开

那么，应该如何做到呢？？

例如序列：1，2，3，4。改变次序后为3,4,2,1（也可以是其他的序列），康托展开告诉我们每种序列都对应着独一无二的一个数字。

引入一个数组，a[m]: 其中m代表着该序列的第m位（也就是序列下标啦），a[m]则代表从第m位到最后一位，第m位上的数是排第几小的（从1开始，1排第0...）

比如3,4,2,1: a[0]=2(a[o]代表3在3,4,2,1中排第几小），a[1]=2(a[1]代表4在4,2,1中排第几小），a[2]=1(a[1]代表2在2,1中排第几小），a[3]=1(a[1]代表1在1中排第几小）

此时X（3,4,2,1）=a[0]*(4-1)!+a[1]*(4-2)!+a[2]*(4-3)!+a3*(4-4)!=17      （这一步能理解吗？全排列问题）

显然X（1,2,3,4）=0

 

那么反向思考一下：如果已知序列号，如何求出对应的序列？

a[0]=17/3！=2......5

a[1]=5/2!=2......1

a[2]=1/1!=1......0

a[3]=0/0!=0

1,2,3,4中排第2的是3

1,2,4中排第2的是4

1,2中排第1的是2

1中排第0的是1

所以序列号17对应的序列就是3,4,2,1.

贴上代码：

1 #include
     
       2 #include
      
         3 typedef long long LL; 4  5 LL fac[1010]; 6  7  8 void cantor(int s[], LL num, int k){
   //康托展开，把一个数字num展开成一个数组s，k是数组长度 9     int t;10     bool h[k];//0到k-1，表示是否出现过 11     memset(h, 0, sizeof(h)); 12     for(int i = 0; i < k; i ++){13         t = num / fac[k-i-1];14         num = num % fac[k-i-1];15         for(int j = 0, pos = 0; ; j ++, pos ++){16             if(h[pos]) j --;17             if(j == t){18                 h[pos] = true;19                 s[i] = pos + 1;20                 break;21             }22         }23     }24 }25 void inv_cantor(int s[], LL &num, int k){
   //康托逆展开，把一个数组s换算成一个数字num 26     int cnt;27     num = 0;28     for(int i = 0; i < k; i ++){29         cnt = 0;30         for(int j = i + 1; j < k; j ++){31             if(s[i] > s[j]) cnt ++;//判断几个数小于它32         }33         num += fac[k-i-1] * cnt;34     }35 }36 37 int main()38 {39     fac[0] = 1;40     for(int i = 1; i <20 ; i ++) 41         fac[i] = fac[i-1] * i;42     int a[20];43     a[0]=3;//数组从0开始，元素值从1开始 44     a[1]=4;45     a[2]=2;46     a[3]=1;47     LL ans;48     inv_cantor(a,ans,4);49     printf("%lld\n",ans);50     int b[20];51     cantor(b,4,17);52     for(int i=0;i<4;i++)53     printf("%d ",b[i]); 54 }
      
     

 

康托展开经典题：hdu 1430

http://acm.hdu.edu.cn/showproblem.php?pid=1430

 直接上代码，解释在注释中：

1 #include
     
        2 #include
      
          3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 using namespace std; 8 9 typedef long long LL; 10 11 LL fac[1010]; 12 int vis[50000]; 13 string ans[50000];//记录下到下标最近的走法 14 15 struct node 16 { 17 string ans; 18 int s[10]; 19 LL status; 20 }; 21 22 void cantor(int s[], LL num, int k){ //康托展开，把一个数字num展开成一个数组s，k是数组长度 23 int t; 24 bool h[k];//0到k-1，表示是否出现过 25 memset(h, 0, sizeof(h)); 26 for(int i = 0; i < k; i ++){ 27 t = num / fac[k-i-1]; 28 num = num % fac[k-i-1]; 29 for(int j = 0, pos = 0; ; j ++, pos ++){ 30 if(h[pos]) j --; 31 if(j == t){ 32 h[pos] = true; 33 s[i] = pos + 1; 34 break; 35 } 36 } 37 } 38 } 39 void inv_cantor(int s[], LL &num, int k){ //康托逆展开，把一个数组s换算成一个数字num 40 int cnt; 41 num = 0; 42 for(int i = 0; i < k; i ++){ 43 cnt = 0; 44 for(int j = i + 1; j < k; j ++){ 45 if(s[i] > s[j]) cnt ++;//判断几个数小于它 46 } 47 num += fac[k-i-1] * cnt; 48 } 49 } 50 51 void bfs() 52 { 53 memset(vis,0,sizeof(vis)); 54 queue
           
            q; 55 node f,next; 56 for(int i=0;i<8;i++) 57 f.s[i]=i+1;//最初状态 58 f.ans=""; 59 inv_cantor(f.s,f.status,8); 60 vis[f.status]=1; 61 q.push(f); 62 while(!q.empty()) 63 { 64 f=q.front(); 65 q.pop(); 66 next=f;//第一种变换 67 swap(next.s[0],next.s[7]); 68 swap(next.s[1],next.s[6]); 69 swap(next.s[2],next.s[5]); 70 swap(next.s[3],next.s[4]); 71 inv_cantor(next.s,next.status,8);// 康托逆展开，将next.s序列对应的序列号存在status里面 72 if(vis[next.status]==0)//若未访问 73 { 74 next.ans+='A';//进行了一次A变换 75 vis[next.status]=1; //标记为访问 76 q.push(next); 77 ans[next.status]=next.ans;//序列号为next.status对应的答案 78 } 79 80 next=f;//第二种变换 81 swap(next.s[3],next.s[2]); 82 swap(next.s[2],next.s[1]); 83 swap(next.s[1],next.s[0]); 84 swap(next.s[4],next.s[5]); 85 swap(next.s[5],next.s[6]); 86 swap(next.s[6],next.s[7]); 87 inv_cantor(next.s,next.status,8); 88 if (vis[next.status]==0) 89 { 90 next.ans+='B'; 91 vis[next.status]=1; 92 q.push(next); 93 ans[next.status]=next.ans; 94 } 95 96 next=f; //第三种变换 97 swap(next.s[1],next.s[6]); 98 swap(next.s[6],next.s[5]); 99 swap(next.s[5],next.s[2]); 100 inv_cantor(next.s,next.status,8); 101 if (vis[next.status]==0) 102 { 103 next.ans+='C'; 104 vis[next.status]=1; 105 q.push(next); 106 ans[next.status]=next.ans; 107 108 } 109 }110 }111 112 int main()113 {114 fac[0] = 1;115 for(int i = 1; i <20 ; i ++) 116 fac[i] = fac[i-1] * i;117 bfs();118 119 string as,bs;120 while(cin>>as>>bs)121 {122 int a[10];123 for(int i=0;i<8;i++)124 a[i]=as[i]-'0';125 int b[10];126 for(int i=0;i<8;i++)127 b[i]=bs[i]-'0';128 for(int i=0;i<8;i++)//把a数组看为{1,2,3,4,5,6,7,8}b数组跟着变化 129 {130 for(int j=0;j<8;j++)131 {132 if(b[i]==a[j])133 {134 b[i]=j+1;135 break;136 }137 }138 }139 LL res;140 inv_cantor(b,res,8);//b数组的序列号为res 141 cout<
            
             <
            
           
          
         
        
       
      
     

注意，用c++提交错误的话请换g++提交