【HDU-1430】解题报告（数论，康拓展开逆展开，简单哈希，BFS）

原始题目

魔板

  • Time Limit: 10000/5000 MS (Java/Others)
  • Memory Limit: 65536/32768 K (Java/Others)
  • Total Submission(s): 4318
  • Accepted Submission(s): 1033

Problem Description

在魔方风靡全球之后不久，Rubik先生发明了它的简化版——魔板。魔板由8个同样大小的方块组成，每个方块颜色均不相同，可用数字1-8分别表示。任一时刻魔板的状态可用方块的颜色序列表示：从魔板的左上角开始，按顺时针方向依次写下各方块的颜色代号，所得到的数字序列即可表示此时魔板的状态。例如，序列(1,2,3,4,5,6,7,8)表示魔板状态为：

1 2 3 4
8 7 6 5

对于魔板，可施加三种不同的操作，具体操作方法如下：

  • A: 上下两行互换,如上图可变换为状态87654321
  • B: 每行同时循环右移一格,如上图可变换为41236785
  • C: 中间4个方块顺时针旋转一格,如上图可变换为17245368

给你魔板的初始状态与目标状态，请给出由初态到目态变换数最少的变换步骤，若有多种变换方案则取字典序最小的那种。

Input

每组测试数据包括两行，分别代表魔板的初态与目态。

Output

对每组测试数据输出满足题意的变换步骤。

Sample Input

12345678
17245368
12345678
82754631

Sample Output

C
AC

Author

LL

Source

ACM暑期集训队练习赛（三）

Recommend

linle

题目大意

如题

解题思路

  • 先考虑暴力，对于每个初态，按A，B，C的顺序BFS，到末态，输出。
  • 不过，似乎有些问题。
  • 问题1：如何表示状态？
  • 问题2：多组数据每次都BFS的话，会T，咋办？

对于问题1，我们不难发现，不同状态其实对应了1-8的一个排列，很明显根据常识我们知道排列是有顺序的（逆序数逐渐增大） 那么我们可否根据排列的数组得到他对应全排列里的序号？其实这和康托展开就搭上关系了。

  • 康拓展开：康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。

稍微详细点的介绍放在收获与反思里。

这样我们就解决了表示状态的问题。

那么对于问题2呢。我们会发现，魔板从初态到末态，重要的是每个板子相对位置的变化，而不是板子的数。换言之，我们可以做一个初态到'12345678'的映射，重新给板子标号， 再将末态各板子按映射关系对应新的标号，即末态按照映射对应一个新标号的末态。

初态        末态
75621483 -> 13846572
↓ 映射
12345678 -> 58763214

代码为

rep(i,0,len1){
    hhash[raw1[i]-'0']=i+1;
}
rep(i,0,len1){
    b[i]=hhash[raw2[i]-'0'];    
}

保留板子相对移动的位置不变化即可，这样我们只要预处理一下'12345678'到各个排列的末态，然后对每组输入，做映射到'12345678'，输出新末态的结果即可。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define eps 1e-8
#define mp make_pair
#define np next_permutation
#define pb push_back
#define all(x) x.begin(),x.end()
#define rep(i,a,n) for(int i=a;i<n;++i)
#define per(i,a,n) for(int i=n-1;i>=a;--i)
#define ms(x,a) memset((x),a,sizeof((x))) 
#define mod 998244353 
#define gapline  cout<<"##---------------##"<<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int maxl=8;
const int maxn=1e5+5;
int A[maxl];//阶乘； 
int ans_cantor[maxl];//康托展开数组 
int next_cantor[maxl];
bool vis_cantor[maxl];//康托标记数组 
bool vis[maxn];
int hhash[20],b[20];
string ans[maxn];
string raw1,raw2;
queue <ll> q;
void prechange(){
	int len1=raw1.length();
	rep(i,0,len1){
		hhash[raw1[i]-'0']=i+1;
	}
	rep(i,0,len1){
		b[i]=hhash[raw2[i]-'0'];	
	}
}
//contar展开，逆展开，数组标号都是从0开始 
void cantor(int contar_s[], ll num, int contar_k){//康托展开，把一个数字num展开成一个数组contar_s，contar_k是数组长度
    int t;
    memset(vis_cantor, 0, sizeof(vis_cantor)); 
    for(int i = 0; i < contar_k; i ++){
        t = num / A[contar_k-i-1];
        num%=A[contar_k-i-1];
		int cnt_cantor=0;
		rep(j,0,contar_k){	//计算每位的逆序数 
			if(vis_cantor[j]) continue;
			if(cnt_cantor==t){
				contar_s[i]=j+1,vis_cantor[j]=1;break;	
			} 
			++cnt_cantor;
			
		}
    }
//    rep(i,0,contar_k) cout<<contar_s[i]<<' '; //输出康拖展开的结果 
//    cout<<endl;
//    gapline;
}
ll inv_cantor(int contar_s[], int contar_k){//康托逆展开，把一个数组contar_s换算成一个数字num 
    int cnt;ll num=0;
    num = 0;
    for(int i = 0; i < contar_k; i ++){
        cnt = 0;
        for(int j = i + 1; j < contar_k; j ++){
            if(contar_s[i] > contar_s[j]) cnt ++;//判断几个数小于它,即求逆序数。 
        }
        num += A[contar_k-i-1] * cnt;
    }
    return num;
}
void change(int i){
	switch(i){
		case 0: //操作A 
			rep(j,0,4) swap(next_cantor[j],next_cantor[maxl-1-j]);
			break;
		case 1: //操作B
			per(j,1,4) swap(next_cantor[(j+1)%4],next_cantor[j]);
			swap(next_cantor[4],next_cantor[7]);
			swap(next_cantor[5],next_cantor[4]);
			swap(next_cantor[6],next_cantor[5]); 
			break;
		case 2: //操作C
			swap(next_cantor[1],next_cantor[2]);
			swap(next_cantor[1],next_cantor[6]);
			swap(next_cantor[6],next_cantor[5]);
			break; 
	}
}
void bfs(){
	A[0]=A[1]=1;
	A[2]=2;
	rep(i,3,maxl+1) A[i]=A[i-1]*i;
	while(!q.empty()) q.pop();
	q.push(0);
	vis[0]=1;
	while(!q.empty()){
		ll temp1=q.front();q.pop();
		cantor(ans_cantor,temp1,maxl);
		rep(i,0,3){
			rep(j,0,maxl) next_cantor[j]=ans_cantor[j];
			change(i);
			ll temp2=inv_cantor(next_cantor,maxl);
			if(!vis[temp2]){
				q.push(temp2);
				vis[temp2]=1;
				ans[temp2]=ans[temp1]+(char)('A'+i);
			}
		}
	}
}

 


int main(){
	ios::sync_with_stdio(false);
	bfs();
	while(cin>>raw1>>raw2){
		prechange();
		//b[]为最终目标态 
		ll cnt=inv_cantor(b,maxl);
		cout<<ans[cnt]<<endl;
	} 
}

收获与反思

  • 本题综合应用了数论里的康托展开（用于找到状态数和排列之间的联系），hash到相同情况讨论，以及BFS，值得深入考虑

  • 关于康托展开 https://www.cnblogs.com/linyujun/p/5205760.html 大部分是通过这篇博客以及其他资料学习的，感谢原作者！

    公式为 \[ X = a_n \times (n-1)! + a_{n-1} \times (n-2)! + \cdots + a_2 \times 1! + a_1 \times 0! \]

    其中\(a_n\)表示第i个元素在未出现的元素中排列第几（从0开始） ，也可以理解成\(a_n\)表示该位的逆序数。

    康托展开得到的X，就是该排列在全排列中的顺序（从0开始）。

    逆展开就是循环除以(n-1)!，商为第n位在未出现元素排列第几（从0开始）。模为下一位的被除数。

    在详细的等开个数论专题（挖坑）。