2021 ICPC 沈阳赛区J题 Luggage Lock

题意

有$T$组样例，其中每组样例为：
给定一个密码为$b_0{b}_1{b}_2{b}_3$的密码锁，已知当前密码锁的状态为$a_0{a}_1{a}_2{a}_3$，求解开密码的最小步数。
$b,a\in [0,9]$。

每一步可以操作任意一个连续的区间$[l,r]$，使得这个区间的数字都向上拨动一位或者向下拨动一位。
$${\forall }_{l\le i\le r}{a}_i=(a_i\pm 1)\mathrm{m}\mathrm{o}\mathrm{d}10$$

思路

首先考虑暴力的做法，从$a_0{a}_1{a}_2{a}_3$开始进行BFS，直到走到$b_0{b}_1{b}_2{b}_3$时跳出。
转移时采用记忆化，总共的状态数为$10^4$，即每次求出一组样例最坏的复杂度为$10^4$。
而$T\le 10^5$，所以复杂度为$10^9$，很明显没法通过。

再考虑预处理，预处理出每一种状态$a_0{a}_1{a}_2{a}_3$转移到其他所有状态的最小步数。
这个复杂度是$10^8$，常数小的或许可以通过这道题。（我没有尝试）

我可以先预处理出0000到其他所有状态的最小步数，对于每个样例$a_0{a}_1{a}_2{a}_3\Rightarrow b_0{b}_1{b}_2{b}_3$来说，我可以将$a_0{a}_1{a}_2{a}_3$当成$0000$并对$b_0{b}_1{b}_2{b}_3$做偏移处理，即可得到答案。
例如：$1234\Rightarrow 2344$相当于$0000\Rightarrow 1110$。

这个偏移的思想和一个前缀和的题很像，可以先把牛牛的猜球游戏补了。

AC的代码

#include <bits/stdc++.h>
using namespace std;
#define si pair<string, int>
#define fi first
#define se second
int vis[10][10][10][10];
int val[10][10][10][10];
void init() {
queue<si> q;
q.push({"0000", 0});
vis[0][0][0][0] = 1;
val[0][0][0][0] = 0;
int res = 0;
while (!q.empty()) {
si cur = q.front();
q.pop();
val[cur.fi[0] - '0'][cur.fi[1] - '0'][cur.fi[2] - '0']
[cur.fi[3] - '0'] = cur.se;
// 一个位置+1
for (int i = 0; i < 4; i++) {
string tmp = cur.fi;
if (tmp[i] == '9')
tmp[i] = '0';
else
tmp[i]++;
if (vis[tmp[0] - '0'][tmp[1] - '0'][tmp[2] - '0'][tmp[3] - '0'])
continue;
vis[tmp[0] - '0'][tmp[1] - '0'][tmp[2] - '0'][tmp[3] - '0'] = 1;
q.push({tmp, cur.se + 1});
}
// 一个位置-1
for (int i = 0; i < 4; i++) {
string tmp = cur.fi;
if (tmp[i] == '0')
tmp[i] = '9';
else
tmp[i]--;
if (vis[tmp[0] - '0'][tmp[1] - '0'][tmp[2] - '0'][tmp[3] - '0'])
continue;
vis[tmp[0] - '0'][tmp[1] - '0'][tmp[2] - '0'][tmp[3] - '0'] = 1;
q.push({tmp, cur.se + 1});
}
// 两个位置+1
for (int i = 0; i < 3; i++) {
string tmp = cur.fi;
if (tmp[i] == '9')
tmp[i] = '0';
else
tmp[i]++;
if (tmp[i + 1] == '9')
tmp[i + 1] = '0';
else
tmp[i + 1]++;
if (vis[tmp[0] - '0'][tmp[1] - '0'][tmp[2] - '0'][tmp[3] - '0'])
continue;
vis[tmp[0] - '0'][tmp[1] - '0'][tmp[2] - '0'][tmp[3] - '0'] = 1;
q.push({tmp, cur.se + 1});
}
// 两个位置-1
for (int i = 0; i < 3; i++) {
string tmp = cur.fi;
if (tmp[i] == '0')
tmp[i] = '9';
else
tmp[i]--;
if (tmp[i + 1] == '0')
tmp[i + 1] = '9';
else
tmp[i + 1]--;
if (vis[tmp[0] - '0'][tmp[1] - '0'][tmp[2] - '0'][tmp[3] - '0'])
continue;
vis[tmp[0] - '0'][tmp[1] - '0'][tmp[2] - '0'][tmp[3] - '0'] = 1;
q.push({tmp, cur.se + 1});
}
// 三个位置+1
for (int i = 0; i < 2; i++) {
string tmp = cur.fi;
if (tmp[i] == '9')
tmp[i] = '0';
else
tmp[i]++;
if (tmp[i + 1] == '9')
tmp[i + 1] = '0';
else
tmp[i + 1]++;
if (tmp[i + 2] == '9')
tmp[i + 2] = '0';
else
tmp[i + 2]++;
if (vis[tmp[0] - '0'][tmp[1] - '0'][tmp[2] - '0'][tmp[3] - '0'])
continue;
vis[tmp[0] - '0'][tmp[1] - '0'][tmp[2] - '0'][tmp[3] - '0'] = 1;
q.push({tmp, cur.se + 1});
}
// 三个位置-1
for (int i = 0; i < 2; i++) {
string tmp = cur.fi;
if (tmp[i] == '0')
tmp[i] = '9';
else
tmp[i]--;
if (tmp[i + 1] == '0')
tmp[i + 1] = '9';
else
tmp[i + 1]--;
if (tmp[i + 2] == '0')
tmp[i + 2] = '9';
else
tmp[i + 2]--;
if (vis[tmp[0] - '0'][tmp[1] - '0'][tmp[2] - '0'][tmp[3] - '0'])
continue;
vis[tmp[0] - '0'][tmp[1] - '0'][tmp[2] - '0'][tmp[3] - '0'] = 1;
q.push({tmp, cur.se + 1});
}
// 四个位置+1
for (int i = 0; i < 1; i++) {
string tmp = cur.fi;
if (tmp[i] == '9')
tmp[i] = '0';
else
tmp[i]++;
if (tmp[i + 1] == '9')
tmp[i + 1] = '0';
else
tmp[i + 1]++;
if (tmp[i + 2] == '9')
tmp[i + 2] = '0';
else
tmp[i + 2]++;
if (tmp[i + 3] == '9')
tmp[i + 3] = '0';
else
tmp[i + 3]++;
if (vis[tmp[0] - '0'][tmp[1] - '0'][tmp[2] - '0'][tmp[3] - '0'])
continue;
vis[tmp[0] - '0'][tmp[1] - '0'][tmp[2] - '0'][tmp[3] - '0'] = 1;
q.push({tmp, cur.se + 1});
}
// 四个位置-1
for (int i = 0; i < 1; i++) {
string tmp = cur.fi;
if (tmp[i] == '0')
tmp[i] = '9';
else
tmp[i]--;
if (tmp[i + 1] == '0')
tmp[i + 1] = '9';
else
tmp[i + 1]--;
if (tmp[i + 2] == '0')
tmp[i + 2] = '9';
else
tmp[i + 2]--;
if (tmp[i + 3] == '0')
tmp[i + 3] = '9';
else
tmp[i + 3]--;
if (vis[tmp[0] - '0'][tmp[1] - '0'][tmp[2] - '0'][tmp[3] - '0'])
continue;
vis[tmp[0] - '0'][tmp[1] - '0'][tmp[2] - '0'][tmp[3] - '0'] = 1;
q.push({tmp, cur.se + 1});
}
}
}
int main() {
init();
int T;
cin >> T;
while (T--) {
string s, t;
cin >> s >> t;
t[0] -= s[0] - '0' - 10;
t[1] -= s[1] - '0' - 10;
t[2] -= s[2] - '0' - 10;
t[3] -= s[3] - '0' - 10;
if (t[0] > '9') t[0] -= 10;
if (t[1] > '9') t[1] -= 10;
if (t[2] > '9') t[2] -= 10;
if (t[3] > '9') t[3] -= 10;
int res = val[t[0] - '0'][t[1] - '0'][t[2] - '0'][t[3] - '0'];
cout << res << "n";
}
return 0;
}

最后

以上就是苗条战斗机为你收集整理的2021 ICPC 沈阳赛区J题 Luggage Lock2021 ICPC 沈阳赛区J题 Luggage Lock的全部内容，希望文章能够帮你解决2021 ICPC 沈阳赛区J题 Luggage Lock2021 ICPC 沈阳赛区J题 Luggage Lock所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。