Skip to content
本博客自 2023 年 4 月 4 日起转为归档状态，可能不再发表新的博文。点此了解博主的竞赛生涯。
This blog has been archived by the owner since April 4, 2023. It may no longer have new updates.

「CSP-S 2023」密码锁

题解966 字
# 洛谷 # CSP-S # 2023 # set
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

小 Y 有一把五个拨圈的密码锁。如图所示，每个拨圈上是从 00 到 99 的数字。每个拨圈都是从 00 到 99 的循环，即 99 拨动一个位置后可以变成 00 或 88，

因为校园里比较安全，小 Y 采用的锁车方式是：从正确密码开始，随机转动密码锁仅一次；每次都是以某个幅度仅转动一个拨圈或者同时转动两个相邻的拨圈。

当小 Y 选择同时转动两个相邻拨圈时，两个拨圈转动的幅度相同，即小 Y 可以将密码锁从 0 0 1 1 5\tt{0\;0\;1\;1\;5} 转成 1 1 1 1 5\tt{1\;1\;1\;1\;5}，但不会转成 1 2 1 1 5\tt{1\;2\;1\;1\;5}。

时间久了，小 Y 也担心这么锁车的安全性，所以小 Y 记下了自己锁车后密码锁的 nn 个状态，注意这 nn 个状态都不是正确密码。

为了检验这么锁车的安全性，小 Y 有多少种可能的正确密码，使得每个正确密码都能够按照他所采用的锁车方式产生锁车后密码锁的全部 nn 个状态。

#输入格式

输入的第一行包含一个正整数 nn，表示锁车后密码锁的状态数。

接下来 nn 行每行包含五个整数，表示一个密码锁的状态。

#输出格式

输出一行包含一个整数，表示密码锁的这 nn 个状态按照给定的锁车方式能对应多少种正确密码。

#输入输出样例

样例输入 #1

1
0 0 1 1 5

样例输出 #1

81

样例解释 #1

一共有 8181 种可能的方案。

其中转动一个拨圈的方案有 4545 种，转动两个拨圈的方案有 3636 种。

样例输入 #2

见选手目录下的 lock/lock2.in 与 lock/lock2.ans。

#数据范围与约定

对于所有测试数据有：1≤n≤81 \leq n \leq 8。

测试点 n≤n\leq 特殊性质
1∼31\sim 3 11 无
4∼54\sim 5 22
6∼86\sim 8 88 A
9∼109\sim 10 无

特殊性质 A：保证所有正确密码都可以通过仅转动一个拨圈得到测试数据给出的 nn 个状态。

#思路

对于每个给定的密码锁的状态，枚举其所对应的每个起始状态，然后在每种上锁状态对应的起始状态的集合之间取交集即可。

取交集的操作可以使用 std::set_intersection 函数来减少代码量。

#代码

C++
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
#include <iostream>
#include <algorithm>
#include <array>
#include <set>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 10,
          M = 5;

int n, ans;
std::array<int, M> a[N];
std::set<std::array<int, M>> set;

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

    cin >> n;

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

    for (int i = 1; i <= n; i++) {
        std::set<std::array<int, M>> set_now;

        // Type 1: Only one element is different.
        for (int j = 0; j < M; j++) {
            std::array<int, M> t = a[i];

            for (int k = 0; k < 10; k++) {
                t[j] = (a[i][j] + k) % 10;

                if (t[j] != a[i][j]) {
                    set_now.emplace(t);
                }
            }
        }

        // Type 2: Two adjacent elements are different.
        for (int j = 0; j + 1 < M; j++) {
            std::array<int, M> t = a[i];

            for (int k = 0; k < 10; k++) {
                t[j] = (a[i][j] + k) % 10;
                t[j + 1] = (a[i][j + 1] + k) % 10;

                if (t[j] != a[i][j]) {
                    set_now.emplace(t);
                }
            }
        }

        if (i == 1) {
            set = set_now;
        } else {
            std::set<std::array<int, M>> set_tmp;

            std::set_intersection(set.begin(), set.end(), set_now.begin(), set_now.end(), std::inserter(set_tmp, set_tmp.begin()));

            set = set_tmp;
        }

        ans = set.size();
    }

    cout << ans << endl;

    return 0;
}