题目请见：传送门
以下为题解，直接从洛谷上搬过来的，还专门改了markdown,(汗）
宽搜 with 一些技巧
- 由于查询量很大，所以要预先处理所有答案
- 预处理当然是用
BFS，并同时进行delete,swap,add操作。注意，不能在x为队首元素时才更新答案，这样会使效率大打折扣（不更新的话,dist[x]任为-1，相当于少了判重） - 对于以上三种操作也有要求，一下进行一些优化（炒鸡模拟应该也能过，因为
swap(),嗯嗯）: - 法一：见一楼的题解，不过有局限性
- 法二：针对
add(),和delete(),可以然枚举的状态有序化以达到优化效果，适用范围更广泛； - 以下为我的代码，其中结构体部分可以省去，
u.step可以直接用dist[x]代替。
#include<queue>#include<cstdio>#include<cstring>main() {}int dist[10000000];struct in{int x,s;}u;std::queue<in>que;void tie(int *a,int <h,int x) { lth=0;//解码 while(x) a[lth++]=x%10,x/=10;}int dis(int *a,int lth) { int x=0;//还原 while(lth) x*=10,x+=a[--lth]; return x;}void add(int *a,int lth,int step) { int tmp;//o(n)的add操作 a[lth]=a[lth-1]; for(int i=lth-1;i>=1;i--) { for(int j=a[i+1]+1;j<a[i-1];j++) { a[i]=j; tmp=dis(a,lth+1); if(dist[tmp]==-1) dist[tmp]=step,que.push((in){tmp,step}); } a[i]=a[i-1]; }}void del(int *a,int lth,int step) { int tmp,out=0;//o(n)的delete操作 for(int i=lth-1;i>=0;i--) { out^=a[i]^=out^=a[i]; tmp=dis(a,lth-1); if(dist[tmp]==-1) dist[tmp]=step,que.push((in){tmp,step}); }}void swa(int *a,int lth,int step) { int tmp;//o(n*(n-1)/2)的swap操作 for(int i=0;i<lth;i++) { for(int j=i+1;j<lth;j++) { if(a[i]==a[j]) continue; a[i]^=a[j]^=a[i]^=a[j]; tmp=dis(a,lth); if(dist[tmp]==-1) dist[tmp]=step,que.push((in){tmp,step}); a[i]^=a[j]^=a[i]^=a[j]; } }}int entry() { memset(dist,-1,sizeof dist); int a[10],lth,lmt,x; scanf("%d",&x); tie(a,lmt,x),dist[x]=0; que.push((in){x,0}); while(!que.empty()) { u=que.front(); que.pop(); memset(a,0,sizeof a); tie(a,lth,u.x); if(lth>1) del(a,lth,u.s+1),tie(a,lth,u.x); if(lth>1) swa(a,lth,u.s+1),tie(a,lth,u.x); if(lth<lmt) add(a,lth,u.s+1); } scanf("%d",&lmt); while(lmt--) { scanf("%d",&x); printf("%d\n",dist[x]); } return 0;}int aptal=entry();
