[CSP-S 2023] 密码锁

GitHub跳转原题关系图返回列表

枚举所有五位密码，用差分模式判断它能否一次操作变成每个记录状态。

OJ: luogu

题目 ID: P9752

难度:普及-

标签:枚举模拟

日期: 2026-07-06 08:46

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

密码锁有 5 个拨圈，每个拨圈是 0..9 的循环数字。正确密码经过一次操作后，会变成一个锁车后的状态。

一次操作只有两种：

  • 只转动一个拨圈，幅度可以是 1..9；
  • 同时转动两个相邻拨圈，两个拨圈的转动幅度必须相同，也是 1..9。

现在给出 n 个锁车后的状态，问有多少个可能的正确密码，使得它分别经过一次合法操作，可以得到这 n 个状态中的每一个。

思路

密码只有 5 位，每位 10 种，总共只有 10^5 个候选。直接枚举每一个候选密码，再检查它和每个记录状态之间的差异是否合法即可。

先看递归枚举每一位的暴力写法：

cpp
// brute.cpp：小数据暴力解，把 5 个密码位看成选择序列，递归枚举每一位填 0..9。
#include <bits/stdc++.h>
using namespace std;

int n;
int record_state[10][5];
int pwd[5];
int answer;

bool can_change_to_record(int row) {
    int diff[5];
    int non_zero = 0;
    for (int i = 0; i < 5; i++) {
        diff[i] = (record_state[row][i] - pwd[i] + 10) % 10;
        if (diff[i] != 0) {
            non_zero++;
        }
    }

    if (non_zero == 1) {
        return true;
    }
    if (non_zero != 2) {
        return false;
    }

    for (int i = 0; i + 1 < 5; i++) {
        if (diff[i] != 0 && diff[i] == diff[i + 1]) {
            bool ok = true;
            for (int j = 0; j < 5; j++) {
                if (j != i && j != i + 1 && diff[j] != 0) {
                    ok = false;
                }
            }
            if (ok) {
                return true;
            }
        }
    }
    return false;
}

bool check_password() {
    for (int i = 1; i <= n; i++) {
        if (!can_change_to_record(i)) {
            return false;
        }
    }
    return true;
}

void dfs_build(int pos) {
    if (pos == 5) {
        if (check_password()) {
            answer++;
        }
        return;
    }

    // 这一层选择第 pos 位密码填哪个数字。
    for (int d = 0; d <= 9; d++) {
        pwd[pos] = d;
        dfs_build(pos + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 5; j++) {
            cin >> record_state[i][j];
        }
    }

    dfs_build(0);
    cout << answer << '\n';
    return 0;
}

这个暴力把 5 位密码看成一个选择序列：第 pos 层递归决定第 pos 位填 0..9 中的哪个数字。递归先生成完整的 pwd[]，叶子节点再统一检查它能否一次操作变成所有记录状态。因为状态总数只有 100000，这种枚举本身已经足够作为正解。

判断一个候选密码 pwd 能不能一次操作变成某个记录状态 s，可以看差分：

text
diff[i] = (s[i] - pwd[i] + 10) % 10

如果 diff[i] = 0，说明这一位没有被转动；否则说明这一位被转了 diff[i] 格。

合法情况只有两类：

  • 恰好一个位置非零：对应只转动一个拨圈；
  • 恰好两个位置非零，且它们相邻、差分值相等：对应同时转动两个相邻拨圈。

对每个候选密码，只要它对所有记录状态都满足上述条件，就把答案加一。

代码

cpp
// main.cpp：枚举所有 5 位密码，检查它能否一次操作变成每个记录状态。
#include <bits/stdc++.h>
using namespace std;

int n;
int record_state[10][5];
int pwd[5];

bool can_change_to_record(int row) {
    int diff[5];
    int non_zero = 0;
    for (int i = 0; i < 5; i++) {
        diff[i] = (record_state[row][i] - pwd[i] + 10) % 10;
        if (diff[i] != 0) {
            non_zero++;
        }
    }

    // 情况 1：只转动一个拨圈。
    if (non_zero == 1) {
        return true;
    }

    // 情况 2：同时转动两个相邻拨圈，且幅度相同。
    if (non_zero == 2) {
        for (int i = 0; i + 1 < 5; i++) {
            if (diff[i] != 0 && diff[i] == diff[i + 1]) {
                bool ok = true;
                for (int j = 0; j < 5; j++) {
                    if (j != i && j != i + 1 && diff[j] != 0) {
                        ok = false;
                    }
                }
                if (ok) {
                    return true;
                }
            }
        }
    }

    return false;
}

bool check_password() {
    for (int i = 1; i <= n; i++) {
        if (!can_change_to_record(i)) {
            return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 5; j++) {
            cin >> record_state[i][j];
        }
    }

    int answer = 0;
    for (int x = 0; x < 100000; x++) {
        int t = x;
        for (int i = 4; i >= 0; i--) {
            pwd[i] = t % 10;
            t /= 10;
        }
        if (check_password()) {
            answer++;
        }
    }

    cout << answer << '\n';
    return 0;
}

复杂度

候选密码有 10^5 个，每个候选需要检查 n <= 8 个状态，每个状态只看 5 位。

时间复杂度为 O(105∗n∗5)O(10^5 * n * 5)，空间复杂度为 O(n∗5)O(n * 5)。

总结

本题的关键不是设计复杂算法，而是把“一次操作”翻译成清楚的差分模式。只要差分判断不漏掉“相邻两个拨圈同幅度转动”，直接枚举所有密码就可以稳定通过。