密码锁

题目描述

小 Y 有一把五个拨圈的密码锁，每个拨圈是 $0 \sim 9$ 的循环数字（ $9$ 再拨一格变 $0$ ）。锁车方式为：从正确密码出发，恰好转动一次，且必须是以下两种之一：转动一个拨圈，幅度为任意非零值（模 10）；或同时转动一对相邻拨圈，两圈幅度相同且非零（模 10），例如可把 $\tt{0\;0\;1\;1\;5}$ 转成 $\tt{1\;1\;1\;1\;5}$ ，但不会转成 $\tt{1\;2\;1\;1\;5}$ 。给定 $n$ 个锁车后的状态（每个都是五个 $0 \sim 9$ 的数字，且都不是正确密码），求有多少个可能的正确密码，使得每个给定状态都能由它经过一次上述转动产生。数据范围： $1 \leqslant n \leqslant 8$ 。

输入格式：第一行一个正整数 $n$ ；接下来 $n$ 行每行五个整数，表示一个状态。输出格式：一行一个整数，表示可能的正确密码数。样例输入 1 与 0 0 1 1 5 对应样例输出 81。

思路

不从密码正向枚举，而是从每个锁车后的状态反推：一次合法转动只有 5×9=45 种单拨圈和 4×9=36 种相邻双拨圈模板，倒放即得该状态的 81 个一步可达前驱（正确密码）。「正确密码能一步转到所有 n 个状态」等价于它属于全部前驱集合的交集，从第一个状态的 81 个前驱出发依次与其余状态的 81 个前驱求交，交集大小就是答案。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 15:04
# update_at: 2026-10-02 15:04

import sys

DIALS = 5  # 拨圈数


def predecessors(state: tuple[int, ...]) -> set[tuple[int, ...]]:
    """一次合法转动恰好到达 state 的全部密码：5×9 个单拨圈 + 4×9 个相邻双拨圈。"""
    # 单拨圈反推：任一拨圈换成另外 9 个数字之一（幅度非零）
    single = {
        state[:i] + (v,) + state[i + 1:]
        for i in range(DIALS)
        for v in range(10)
        if v != state[i]
    }
    # 相邻双拨圈反推：两位同时减同一个非零幅度 d（模 10 循环）
    pair = {
        state[:i] + ((state[i] - d) % 10, (state[i + 1] - d) % 10) + state[i + 2:]
        for i in range(DIALS - 1)
        for d in range(1, 10)
    }
    return single | pair


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    states = [tuple(next(data) for _ in range(DIALS)) for _ in range(n)]

    # 正确密码必须同时是每个状态的前驱，取交集即得答案
    cand = predecessors(states[0])
    for state in states[1:]:
        cand &= predecessors(state)

    print(len(cand))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101#include <bits/stdc++.h>
using namespace std;

/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 16:30
 * update_at: 2026-10-06 16:30
 */

typedef long long ll;

// 每个状态反推出的前驱集合最多 81 个，交集只收缩，用数组存即可
const int MAXN = 10;   // n <= 8
const int MAXP = 100;  // 单个状态的前驱最多 5*9 + 4*9 = 81 个

ll n;                                   // 锁车后状态数
ll st[MAXN][5];                         // st[i][j] = 第 i 个状态的第 j 个拨圈数字
ll cand[MAXP][5];                       // 当前候选密码集合（前驱集合的交集）
ll cnt;                                 // 当前候选个数

// 判断数组 p 的五个数字是否已在候选集合 cand 中（去重用）
bool in_cand(ll p[5]) {
    for (ll i = 0; i < cnt; i++) {
        bool same = true;
        for (ll j = 0; j < 5; j++)
            if (cand[i][j] != p[j]) same = false;
        if (same) return true;
    }
    return false;
}

// 把状态 s 的全部前驱与候选集合求交：先枚举 81 个前驱，属于旧候选才保留
void intersect(ll s[5]) {
    ll nxt[MAXP][5]; // 新交集，最多仍 81 个
    ll ncnt = 0;
    ll p[5];

    // 单拨圈反推：第 i 位换成其余 9 个数字（幅度非零），恰一位不同
    for (ll i = 0; i < 5; i++) {
        for (ll v = 0; v < 10; v++) {
            if (v == s[i]) continue;
            for (ll j = 0; j < 5; j++) p[j] = s[j];
            p[i] = v;
            if (in_cand(p)) { // 新交集只需检查旧候选
                for (ll j = 0; j < 5; j++) nxt[ncnt][j] = p[j];
                ncnt++;
            }
        }
    }

    // 相邻双拨圈反推：相邻两位同减非零幅度 d（模 10），恰两位不同
    for (ll i = 0; i + 1 < 5; i++) {
        for (ll d = 1; d <= 9; d++) {
            for (ll j = 0; j < 5; j++) p[j] = s[j];
            p[i] = (s[i] - d + 10) % 10;
            p[i + 1] = (s[i + 1] - d + 10) % 10;
            if (in_cand(p)) {
                for (ll j = 0; j < 5; j++) nxt[ncnt][j] = p[j];
                ncnt++;
            }
        }
    }

    // 用新交集覆盖旧候选
    for (ll i = 0; i < ncnt; i++)
        for (ll j = 0; j < 5; j++) cand[i][j] = nxt[i][j];
    cnt = ncnt;
}

int main() {
    scanf("%lld", &n);
    for (ll i = 0; i < n; i++)
        for (ll j = 0; j < 5; j++) scanf("%lld", &st[i][j]);

    // 第一个状态的全部前驱作为初始候选：单拨圈 + 相邻双拨圈，共 81 个
    cnt = 0;
    ll p[5];
    for (ll i = 0; i < 5; i++)
        for (ll v = 0; v < 10; v++) {
            if (v == st[0][i]) continue;
            for (ll j = 0; j < 5; j++) p[j] = st[0][j];
            p[i] = v;
            for (ll j = 0; j < 5; j++) cand[cnt][j] = p[j];
            cnt++;
        }
    for (ll i = 0; i + 1 < 5; i++)
        for (ll d = 1; d <= 9; d++) {
            for (ll j = 0; j < 5; j++) p[j] = st[0][j];
            p[i] = (st[0][i] - d + 10) % 10;
            p[i + 1] = (st[0][i + 1] - d + 10) % 10;
            for (ll j = 0; j < 5; j++) cand[cnt][j] = p[j];
            cnt++;
        }

    // 依次与其余状态的前驱集合求交，交集大小即答案
    for (ll i = 1; i < n; i++) intersect(st[i]);
    printf("%lld\n", cnt);
    return 0;
}

测试点	$n\leq$	特殊性质
$1\sim 3$	$1$	无
$4\sim 5$	$2$	无
$6\sim 8$	$8$	A
$9\sim 10$	$8$	无

目录

题目描述

思路

参考代码