[CSP-S 2023] 密码锁
2huk
·
·
题解
[CSP-S 2023] 密码锁
Description
小 Y 有一把 5 个拨圈的密码锁，每个拨圈都是 0 \sim 9 的循环。
每次小 Y 从正确密码开始，通过以下两种方法之一随机转动密码锁一次：
- 以某个幅度仅转动一个拨圈；
- 以某个幅度同时转动两个相邻的拨圈。
小 Y 记下了自己转动后密码锁的 n 个状态，注意这 n 个状态都不是正确密码。
求有多少种可能的正确密码，使得每个正确密码都能够按照他所采用的锁车方式产生锁车后密码锁的全部 n 个状态。
## Solution
可以注意到，每位可以填 $0 \sim 9$ 中的共 $10$ 位数字，因此 $5$ 位总共有 $5^{10} \approx 10^7$ 个不同的密码锁状态。
考虑 dfs 暴力枚举每一位，然后检验是否可以从这个状态变到所有给定的 $n$ 个状态即可。若是，则答案加一。
根据上述想法可以写出如下代码：
```cpp
bool chk()
{
for (int i = 1; i <= n; ++ i )
if (!calc(i)) // calc(i) 表示能否将当前状态枚举的 p 转化成给定的第 i 个状态
return false;
return true;
}
void dfs(int u)
{
if (u > 5)
{
res += chk();
return;
}
for (int i = 0; i < 10; ++ i )
{
p[u] = i; // 枚举状态 p
dfs(u + 1);
}
return;
}
```
其中第 4 行的 `calc(i)` 表示能否将当前状态枚举的 $p$ 转化成给定的第 $i$ 个状态（以下将第 $i$ 个状态称为 $a_i$）。考虑实现这个问题。
- 若 $p = a_i$，那么这个状态是不可行的。 因为题目中提到所有的状态都不是不是正确密码；
- 若 $p$ 与 $a_i$ 只有一位不同，那么这个状态是可行的。可以由题目中的操作 1 转化成 $a_i$；
- 若 $p$ 与 $a_i$ 不同的位数多于 $2$ 位，那么这个状态是不可行的；
- 若 $p$ 与 $a_i$ 不同的位数为 $2$ 位，但是这不同的两位不相邻，那么这个状态是不可行的；
- 若 $p$ 与 $a_i$ 不同的位数为 $2$ 位，且这两位相邻，则需要分类讨论：
- 若可以从 $p$ 以相同的幅度将两位转到 $a_i$，那么这个状态是可行的；
- 若不可以从 $p$ 以相同的幅度将两位转到 $a_i$，那么这个状态是不可行的。
```cpp
bool calc(int x) // 能否将 p 转化成 a[x]？
{
int cnt = 0; // 找到 p 与 a[x] 不同的所有位
for (int i = 1; i <= 5; ++ i )
if (p[i] != a[x][i])
di[ ++ cnt] = i;
if (!cnt) return false; // 完全相同，不可行
if (cnt == 1) return true; // 只有一位不同，可行
if (cnt > 2) return false; // 多余两位不同，不可行
if (abs(di[1] - di[2]) != 1) return false; // 不同的两位不相邻，不可行
return (f(p[di[1]], a[x][di[1]]) == f(p[di[2]], a[x][di[2]])); // 判断两位的转动幅度是否相同
}
```
接下来考虑计算如何在拨圈上将 $x$ 转为 $y$，即代码中的 `f(x, y)` 函数：
- 若 $x \le y$，那么直接转即可，幅度为 $y - x$；
- 若 $x > y$，那么首先需要将 $x$ 转到 $0$，再从 $0$ 转到 $y$，总幅度为 $10 - x + y$。
```cpp
int f(int x, int y) // 从 a 转到 b 的次数
{
return (x <= y) ? (y - x) : (10 - x + y);
}
```
那么问题就解决了。
## Code
```cpp
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 10;
int n, a[N][6], res;
int p[6];
int di[N];
int f(int x, int y) // 从 a 转到 b 的次数
{
return (x <= y) ? (y - x) : (10 - x + y);
}
bool calc(int x) // 能否将 p 转化成 a[x]？
{
int cnt = 0; // 找到 p 与 a[x] 不同的所有位
for (int i = 1; i <= 5; ++ i )
if (p[i] != a[x][i])
di[ ++ cnt] = i;
if (!cnt) return false; // 完全相同，不可行
if (cnt == 1) return true; // 只有一位不同，可行
if (cnt > 2) return false; // 多余两位不同，不可行
if (abs(di[1] - di[2]) != 1) return false; // 不同的两位不相邻，不可行
return (f(p[di[1]], a[x][di[1]]) == f(p[di[2]], a[x][di[2]])); // 判断两位的转动幅度是否相同
}
bool chk()
{
for (int i = 1; i <= n; ++ i )
if (!calc(i)) // calc(i) 表示能否将当前状态枚举的 p 转化成给定的第 i 个状态
return false;
return true;
}
void dfs(int u)
{
if (u > 5)
{
res += chk();
return;
}
for (int i = 0; i < 10; ++ i )
{
p[u] = i; // 枚举状态 p
dfs(u + 1);
}
return;
}
int main()
{
freopen("lock.in", "r", stdin);
freopen("lock.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; ++ i )
for (int j = 1; j <= 5; ++ j )
cin >> a[i][j];
dfs(1);
cout << res;
return 0;
}
```