[CSP-S 2023]密码锁 - 题解
题目大意
题目描述了一个密码锁的情景，密码锁由五个拨圈组成，每个拨圈上有从0到9的数字。小Y在设置密码时只会拨动一次，且只会拨动一个拨圈或使用相同的力度拨动相邻的两个拨圈。小Y担心密码锁的安全性，因此他尝试了一些不同的操作来解锁密码锁，将这些操作记录下来。现在要求你找出所有可能的正确密码，这些正确密码可以通过小Y所采用的锁车方式生成小Y记录的所有n个状态。
题目分析
这道题的关键是要找出所有可能的正确密码，使得每个正确密码都能通过给定的锁车方式生成n个状态。在题目描述中，给出了两种操作方式，一种是转动一个拨圈，一种是同时转动两个相邻拨圈。所以我们需要遍历所有可能的5个拨圈的组合，找出满足条件的正确密码。
部分分解法（骗分解法）
以下是原题的测试点范围：
| 测试点 | n\leq | 特殊性质 |
|---|---|---|
| 1\sim 3 | 1 | 无 |
| 4\sim 5 | 2 | 无 |
| 6\sim 8 | 8 | A |
| 9\sim 10 | 8 | 无 |
特殊性质 A：保证所有正确密码都可以通过仅转动一个拨圈得到测试数据给出的 n个状态。
30pts解法
测试数据第一组：n=1，固定有81种正确密码，分别是转动1次是5\times9=45 种，转动2次4\times9=36 种，所以总共是81种，输入完成后直接输出 81即可。
#include<bits/stdc++.h>
#define N 11
using namespace std;
int n;
int main(){
scanf("%d",&n);
printf("81");
return 0;
}
60pts解法
在30pts的基础上，可以根据骗分的方法，有这样一种思路：特殊性质A中描述只会存在拨动一次的情况，所以 n\le8 的所有状态肯定同时只存在一位数字不同。所以正确密码的数量应该为 10-n 。
所以我们可以分情况讨论，代码如下：
#include<bits/stdc++.h>
#define N 11
using namespace std;
int n;
int main(){
scanf("%d",&n);
if(n==1){
printf("81");
}
else{
printf("%d",10-n);
}
return 0;
}
短短几行拿下60分，是不是非常的轻松呢~
正解思路
- 遍历所有可能的5个拨圈的数字组合，这里我们可以使用5个嵌套的循循环，每个循环从0到9，代表每个拨圈的数字。
- 对于每种组合，遍历n个状态，检查是否满足通过给定的锁车方式生成这n个状态。这里我们定义一个函数
check来判断是否满足条件。 - 在
check函数中，我们首先统计每个拨圈需要改变的数字的个数，如果个数为1，说明只需要转动一个拨圈；如果个数为2，说明需要同时转动两个相邻的拨圈。我们可以通过计算每个拨圈对应数字的差值来判断是否可以通过同时转动两个相邻拨圈来达到目标状态。 - 如果
check函数返回true，说明这种组合是一个可能的正确密码，增加答案的计数。 - 最后输出答案即可。
AC代码
#include<bits/stdc++.h>
#define N 11
using namespace std;
int n, a[N][N], b[N], ans;
// 检查是否通过锁车方式生成给定状态
bool check(int i) {
int cnt = 0;
for (int j = 1; j <= 5; j++) {
cnt += (a[i][j] != b[j]);
}
// 如果只有一个数字不同，可以通过转动一个拨圈达到目标状态
if (cnt == 1) return true;
// 如果数字不同的个数不是1也不是2，不满足条件
else if (cnt != 2) return false;
// 如果有两个数字不同，检查是否可以通过同时转动两个相邻拨圈达到目标状态
for (int j = 1; j < 5; j++) {
// 分别判断拨动前当前状态和正确密码是否相同并且拨动后两密码是否可以相同
if (a[i][j] != b[j] && a[i][j + 1] != b[j + 1] && (b[j] - a[i][j] + 10) % 10 == (b[j + 1] - a[i][j + 1] + 10) % 10) {
return true;
}
}
return false;
}
// 检查是否所有n个状态都满足条件
bool checkmain() {
for (int i = 1; i <= n; i++) {
if (!check(i)) return false;
}
return true;
}
int main(){
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 5; j++) {
cin >> a[i][j];
}
}
// 暴力枚举5个数字
for (int i = 0; i <= 9; i++) {
for (int j = 0; j <= 9; j++) {
for (int k = 0; k <= 9; k++) {
for (int l = 0; l <= 9; l++) {
for (int o = 0; o <= 9; o++) {
int num = 0; // 使用数组存储当前枚举的5位数
b[++num] = i;
b[++num] = j;
b[++num] = k;
b[++num] = l;
b[++num] = o;
// 如果满足条件，增加正确密码的个数
if (checkmain()) {
ans++;
}
}
}
}
}
}
cout << ans;
return 0;
}
时间复杂度分析
在主循环中，我们有5个嵌套循环，每个循环的范围是0到9，所以共循环10^5次。每一个密码的状态数一共81种，所以时间复杂度应为O(8.1\times 10^6)，因此不会超时。
空间复杂度分析
- 除了输入数据和输出数据外，主要使用了两个数组
a和b，以及一个整数ans。这三个的空间复杂度是O(n) + O(5) + O(1) = O(n)。 - 递归调用时会有一定的栈空间占用，但在这里递归的深度不会太大，因此不会显著影响总体空间复杂度。
- 综合考虑，总体空间复杂度为O(n)。
