文章：https://www.cnblogs.com/Mychael/p/8282895.html

康拓展開，知道數(shù)列求排名

//3 2 5 4 1 59 #include<bits/stdc++.h> using namespace std; int fac[20],sign[20],a[20],label[20],n; void init(){fac[0]=1;for(int i=1;i<=10;i++)fac[i]=fac[i-1]*i; } int kangtuo(int* a){for(int i=0;i<n;i++)sign[i]=1;int paiming=0;for(int i=0;i<n;i++){int cnt=0;for(int j=0;j<a[i];j++)if(sign[j])cnt++;sign[a[i]]=0;paiming+=cnt*fac[n-i-1];}return paiming; } int main(){init();cin>>n;for(int i=0;i<n;i++)cin>>a[i],a[i]--;///第一位的排名是0，所以要自減cout<<kangtuo(a)<<endl;return 0; }

康拓逆展開，知排名求數(shù)列

//10 5 1 3 4 5 2 #include<bits/stdc++.h> using namespace std; int ans[20],fac[20],sign[20],a[20],label[20],n; void init(){fac[0]=1;for(int i=1;i<=10;i++)fac[i]=fac[i-1]*i; } void nikangtuo(int paiming,int m){paiming--;int cnt;for(int i=0;i<m;i++)label[i]=1;for(int i=0;i<m;i++){cnt=paiming/fac[m-1-i];paiming=paiming%fac[m-1-i];for(int j=0;j<m;j++){if(!label[j])continue;if(!cnt){label[j]=0;ans[i]=j;break;}cnt--;}}for(int i=0;i<m;i++)cout<<ans[i]+1<<" "; } int main() {init();int paiming,m;cin>>paiming>>m;nikangtuo(paiming,m); }

　　

http://poj.org/problem?id=1077

#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; const int M=4e5+5; struct node{int a[9]; }que[M],endd; int factorial[9],start[9]; char str[2],dir[]="lrdu",op[M]; int net[M],vis[M]; int nextx[4]={0,0,-1,1}; int nexty[4]={1,-1,0,0}; void init(){factorial[0]=1;for(int i=1;i<9;i++)factorial[i]=factorial[i-1]*i; } int kang(int *a){int v=0;for(int i=0;i<9;i++){int countt=0;for(int j=i+1;j<9;j++)if(a[i]>a[j])countt++;v+=countt*factorial[8-i];}return v; } void bfs(int sign){int head=0,tail=0;que[tail++]=endd;vis[sign]=1;while(head<tail){node P=que[head++];int now_sign=kang(P.a);int x,y,z;for(int i=0;i<9;i++){if(P.a[i]==0){x=i/3,y=i%3,z=i;break;}}node Q=P;for(int i=0;i<4;i++){int tx=x+nextx[i];int ty=y+nexty[i];if(tx<0||ty<0||tx>=3||ty>=3)continue;int tz=tx*3+ty;Q.a[z]=P.a[tz];Q.a[tz]=0;int Q_sign=kang(Q.a);if(!vis[Q_sign]){vis[Q_sign]=1;op[Q_sign]=dir[i];net[Q_sign]=now_sign;que[tail++]=Q;}Q=P;}} } int main(){init();for(int i=0;i<9;i++)if(i==8)endd.a[i]=0;elseendd.a[i]=i+1;int sign=kang(endd.a);bfs(sign);while(~scanf("%s",str)){if(str[0]=='x')start[0]=0;elsestart[0]=str[0]^48;for(int i=1;i<9;i++){scanf("%s",str);if(str[0]=='x')start[i]=0;elsestart[i]=str[0]^48;}int start_sign=kang(start);if(vis[start_sign]){while(sign!=start_sign){putchar(op[start_sign]);start_sign=net[start_sign]; }putchar('\n');}elseputs("unsolvable");}return 0; } View Code

?

https://www.luogu.org/problemnew/show/P2730

#include<cstdio> #include<cstring> #include<queue> #include<algorithm> #include<iostream> using namespace std; int mi(int x,int y){return x<y?x:y; } inline int read(){int sum=0,x=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')x=0;ch=getchar();}while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar();}return x?sum:-sum; } inline void write(int x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0'); } const int M=4e5+5; struct node{int a[8]; }que[M],endd; int fac[8],start[8]; char dir[]="ABC",op[M],anss[M]; int nextt[M],vis[M]; void init(){fac[0]=1;for(int i=1;i<8;i++)fac[i]=fac[i-1]*i; } int kang(int *a){int ans=0;for(int i=0;i<8;i++){int countt=0;for(int j=i+1;j<8;j++)if(a[i]>a[j])countt++;ans+=countt*fac[7-i];}return ans; } void bfs(int sign){int head=0,tail=0;que[tail++]=endd;vis[sign]=1;while(head<tail){node P=que[head++];int now_sign=kang(P.a);node Q=P;for(int i=0;i<3;i++){//Aif(i==0){for(int j=0;j<=3;j++){int t=Q.a[j];Q.a[j]=Q.a[7-j];Q.a[7-j]=t;}}//Belse if(i==1){Q.a[0]=P.a[3];Q.a[1]=P.a[0];Q.a[2]=P.a[1];Q.a[3]=P.a[2];Q.a[4]=P.a[5];Q.a[5]=P.a[6];Q.a[6]=P.a[7];Q.a[7]=P.a[4];}//Celse{Q.a[0]=P.a[0];Q.a[1]=P.a[6];Q.a[2]=P.a[1];Q.a[3]=P.a[3];Q.a[4]=P.a[4];Q.a[5]=P.a[2];Q.a[6]=P.a[5];Q.a[7]=P.a[7];}int Q_sign=kang(Q.a);if(!vis[Q_sign]){vis[Q_sign]=1;op[Q_sign]=dir[i];nextt[Q_sign]=now_sign;que[tail++]=Q;}Q=P;}} } int main(){init();for(int i=0;i<8;i++)endd.a[i]=i+1;int sign=kang(endd.a);bfs(sign);while(~scanf("%d",&start[0])){for(int i=1;i<8;i++)start[i]=read();int start_sign=kang(start);// string ss;int i=0;while(sign!=start_sign){//putchar(op[start_sign]);//ss+=op[start_sign];anss[i++]=op[start_sign];start_sign=nextt[start_sign];}write(i);putchar('\n');i--;for(;i>=0;i--)putchar(anss[i]);putchar('\n');}return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/starve/p/10970413.html

總結(jié)

以上是生活随笔為你收集整理的八数码（康拓展开标记）及类似题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。