【2023 CSP-S密码锁（洛谷P9752）】题解：动态规划与**交集的巧妙应用

ftggdnt

一、题目解读

2023年CSP-S的“密码锁”题目（洛谷P9752）要求破解一种环形密码锁机制。题目给定n组状态，每个状态由5个数字组成，通过“单拨圈”或“双相邻拨圈”操作可改变数字。正确密码需满足：通过操作能从初始状态转换到所有给定状态，且给定状态本身不能作为密码。题目核心在于寻找符合条件的正确密码候选集，并排除无效状态。

二、解题思路

1. 动态生成候选密码：

    设计generate_candidates函数，针对每个状态分别进行单拨圈（单个数字±[1,9]）和双相邻拨圈（相邻两数字同时±[1,9]）操作，生成所有可能的合法候选密码**。

    利用set容器自动去重，避免重复候选。

2. **交集筛选：

    初始化**个状态的候选集，依次与其他状态候选集进行交集运算（set_intersection）。

    若交集为空，说明无解；否则持续缩小共同候选集范围。

3. 排除观察状态：

    题目明确指出给定状态本身不是正确密码，因此需从最终候选集中移除所有原输入状态。

三、解题步骤

1. 输入处理：读取n组状态，存储为二维vector。

2. 生成初始候选：调用generate_candidates计算**个状态的候选集。

3. 逐步交集筛选：

    循环遍历其余n-1组状态，每组生成候选后与当前共同候选集求交集。

    若交集为空，退出循环（无解）。

4. 排除观察状态：遍历原输入状态，从共同候选集中删除。

5. 验证结果：若剩余候选集非空，输出任意一个元素；否则输出-1。

四、代码与注释

1. #include <iostream>  
   
2. #include <vector>  
   
3. #include <set>  
   
4. #include <algorithm>  
   
5. using namespace std;  
   
6. 
   
7. // 生成所有可能的正确密码候选  
   
8. set<vector<int>> generate_candidates(const vector<int>& state) {  
   
9.     set<vector<int>> candidates;  
   
10.     // 单拨圈操作  
    
11.     for (int i = 0; i < 5; ++i) {  
    
12.         for (int delta = -9; delta <= 9; ++delta) {  
    
13.             if (delta == 0) continue; // 跳过不变操作  
    
14.             vector<int> candidate = state; // **状态  
    
15.             candidate[i] = (candidate[i] - delta + 20) % 10; // 处理边界（负数转正）  
    
16.             candidates.insert(candidate);  
    
17.         }  
    
18.     }  
    
19.     // 双相邻拨圈操作  
    
20.     for (int i = 0; i < 4; ++i) {  
    
21.         for (int delta = -9; delta <= 9; ++delta) {  
    
22.             if (delta == 0) continue;  
    
23.             vector<int> candidate = state;  
    
24.             candidate[i] = (candidate[i] - delta + 20) % 10;  
    
25.             candidate[i+1] = (candidate[i+1] - delta + 20) % 10;  
    
26.             candidates.insert(candidate);  
    
27.         }  
    
28.     }  
    
29.     return candidates;  
    
30. }  
    
31. 
    
32. int main() {  
    
33.     ios::sync_with_stdio(false);  
    
34.     cin.tie(nullptr); // 加速IO  
    
35. 
    
36.     int n;  
    
37.     cin >> n;  
    
38.     vector<vector<int>> states(n, vector<int>(5)); // 存储n组状态  
    
39.     for (int i = 0; i < n; ++i) {  
    
40.         for (int j = 0; j < 5; ++j) {  
    
41.             cin >> states[i][j];  
    
42.         }  
    
43.     }  
    
44. 
    
45.     // **个状态的所有候选  
    
46.     set<vector<int>> common_candidates = generate_candidates(states[0]);  
    
47.     // 与其他状态的候选取交集  
    
48.     for (int i = 1; i < n; ++i) {  
    
49.         set<vector<int>> current_candidates = generate_candidates(states[i]);  
    
50.         set<vector<int>> temp;  
    
51.         set_intersection(  
    
52.             common_candidates.begin(), common_candidates.end(),  
    
53.             current_candidates.begin(), current_candidates.end(),  
    
54.             inserter(temp, temp.begin())  
    
55.         );  
    
56.         common_candidates = temp; // 更新交集结果  
    
57.         if (common_candidates.empty()) break; // 无解退出  
    
58.     }  
    
59. 
    
60.     // 排除观察到的状态本身（题目说明这些不是正确密码）  
    
61.     for (const auto& state : states) {  
    
62.         common_candidates.erase(state); // 从候选集中删除原状态  
    
63.     }  
    
64. 
    
65.     // 输出结果  
    
66.     if (common_candidates.empty()) {  
    
67.         cout << -1 << endl;  
    
68.     } else {  
    
69.         // 输出任意一个候选密码（由于**无序，可能输出不同结果）  
    
70.         for (const auto& candidate : common_candidates) {  
    
71.             for (int num : candidate) {  
    
72.                 cout << num << ';  
    
73.             }  
    
74.             cout << endl;  
    
75.             break; // 找到**个即退出  
    
76.         }  
    
77.     }  
    
78.     return 0;  
    
79. }

复制代码

五、总结

本解法巧妙结合动态生成候选与**交集运算，高效缩小正确密码范围。关键在于：

    1. 利用数学规律简化状态转换（单/双拨圈操作）；

    2. 通过交集逐步筛选，减少无效候选；

    3. 明确排除题目规定的无效状态。

该思路对处理多约束条件的状态搜索问题具有参考价值，代码中set容器与STL算法的结合提升了效率与可读性。

来源：【2023 CSP-S密码锁（洛谷P9752）】题解：动态规划与**交集的巧妙应用