自我想法
说实话,在Y老师用unordered_map时我是真的不明白,也许是我太弱了。于是我想有没有可以直接用map的方法
题目描述
这是一张有 8 个大小相同的格子的魔板:
1 2 3 4
8 7 6 5
我们知道魔板的每一个方格都有一种颜色。
这 8 种颜色用前 8 个正整数来表示。
可以用颜色的序列来表示一种魔板状态,规定从魔板的左上角开始,沿顺时针方向依次取出整数,构成一个颜色序列。
对于上图的魔板状态,我们用序列 (1,2,3,4,5,6,7,8) 来表示,这是基本状态。
这里提供三种基本操作,分别用大写字母 A,B,C 来表示(可以通过这些操作改变魔板的状态):
A:交换上下两行;
B:将最右边的一列插入到最左边;
C:魔板中央对的4个数作顺时针旋转。
你要编程计算用最少的基本操作完成基本状态到特殊状态的转换,输出基本操作序列。
输入样例
2 6 8 4 5 7 3 1
输入样例
7
BCABCCB
分析
对于这道题,我们可以开两个map数组,一个记录状态,另一个记录前驱,而对应的每个操作,我们其实不用像
Y老师那样专业,数组模拟也能做到,最后得到答案后,在一个一个往回跳,判断每次对应的操作就行了,最后统一输出
代码
//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops")
//#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt")
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>
#define RG register
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int N=9;
int tot;
char a[N*N];
map<string,string>pre;
map<string,int>dist;
queue<string>q;
inline string Get_1(string k)
{
string res="";
for (int i=7;i>=4;i--) res+=k[i];
for (int i=3;i>=0;i--) res+=k[i];
return res;
}//对行列变换
inline string Get_3(string k)
{
string res="";
res+=k[0];
res+=k[6];
res+=k[1];
res+=k[3];
res+=k[4];
res+=k[2];
res+=k[5];
res+=k[7];
return res;
}//一个一个加
inline string Get_2(string k)
{
string res="";
res+=k[3];
for (int i=0;i<3;i++) res+=k[i];
for (int i=5;i<8;i++) res+=k[i];
res+=k[4];
return res;
}
inline void BFS(string end)
{
string v0="12345678";
if(end==v0) return ;
dist[v0]=0;
q.push(v0);
while(!q.empty())
{
string k=q.front();q.pop();
string x[4];
x[0]=Get_1(k);
x[1]=Get_2(k);
x[2]=Get_3(k);
for (int i=0;i<3;i++)
{
string str=x[i];
if(dist[str]==0)
{
dist[str]=dist[k]+1;
pre[str]=k;
if(str==end) break;
q.push(str);
}
}
}
}
inline void check(string end)
{
string op=pre[end];
if(op[0]==end[7]&&op[1]==end[6]&&op[2]==end[5]&&op[3]==end[4])
{
a[++tot]='A';
return ;
}
else if(op[1]==end[2]&&op[2]==end[5]&&op[6]==end[1]&&op[5]==end[6])
{
a[++tot]='C';
return ;
}
else a[++tot]='B';
}
int main()
{
string end="";
int x;
for (int i=0;i<8;i++)
{
cin>>x;
end+=char(x+'0');
}
BFS(end);
cout<<dist[end]<<"\n";
string vo="12345678";
while(end!=vo)
{
check(end);
end=pre[end];
}
if(dist[end])
for (int i=tot;i>=1;i--) cout<<a[i];
return 0;
}
Y总说过,unordered_map比map更快点,两者都可以用
不,
unordered_map
最坏复杂度为 $O(n)$,map
最坏复杂度 $O(\log n)$随机数据下,
unordered_map
比map
优秀,但是出题人故意卡你就完蛋了是的,acwing有一场周赛卡unordered_map了。但是大多数情况两者都可以用,并且unordered_map快一点。
map底层原理是pair+红黑树,时间复杂度是自带$log$的
然而unordered_map底层原理是哈希表(用一个数去表示一些数据,如果不同的数据对应了同样的数,就在对应的地方加一个位置去区别这两个数据),时间复杂度是一个常数极小的$n$(几乎就是O(1)因为这个数据范围碰撞概率不大),所以说这个如果数据范围大一点容易被卡掉的
思路明白了就行,毕竟我这个代码有点繁琐
大佬照着您的思路,我敲了一下,过了样例,但是wa,您能帮我看看么
我看看
思路明白了就行,毕竟我这个代码有点繁琐
好的~
感谢您的讲解☺
map
如果只用来哈希就相当于unordered_map
,但unordered_map
复杂度都是常数的,会比map
快不少。而map
则更多用于维护key
的顺序。