当前位置：首页 > 提高组 > 【2023 CSP-S密码锁（洛谷P9752）】题解：动态规划与集合交集的巧妙应用

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

2天前

一、题目解读

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。

四、代码与注释

#include <iostream>  
#include <vector>  
#include <set>  
#include <algorithm>  
using namespace std;  

// 生成所有可能的正确密码候选  
set<vector<int>> generate_candidates(const vector<int>& state) {  
    set<vector<int>> candidates;  
    // 单拨圈操作  
    for (int i = 0; i < 5; ++i) {  
        for (int delta = -9; delta <= 9; ++delta) {  
            if (delta == 0) continue; // 跳过不变操作  
            vector<int> candidate = state; // 复制状态  
            candidate[i] = (candidate[i] - delta + 20) % 10; // 处理边界（负数转正）  
            candidates.insert(candidate);  
        }  
    }  
    // 双相邻拨圈操作  
    for (int i = 0; i < 4; ++i) {  
        for (int delta = -9; delta <= 9; ++delta) {  
            if (delta == 0) continue;  
            vector<int> candidate = state;  
            candidate[i] = (candidate[i] - delta + 20) % 10;  
            candidate[i+1] = (candidate[i+1] - delta + 20) % 10;  
            candidates.insert(candidate);  
        }  
    }  
    return candidates;  
}  

int main() {  
    ios::sync_with_stdio(false);  
    cin.tie(nullptr); // 加速IO  

    int n;  
    cin >> n;  
    vector<vector<int>> states(n, vector<int>(5)); // 存储n组状态  
    for (int i = 0; i < n; ++i) {  
        for (int j = 0; j < 5; ++j) {  
            cin >> states[i][j];  
        }  
    }  

    // 第一个状态的所有候选  
    set<vector<int>> common_candidates = generate_candidates(states[0]);  
    // 与其他状态的候选取交集  
    for (int i = 1; i < n; ++i) {  
        set<vector<int>> current_candidates = generate_candidates(states[i]);  
        set<vector<int>> temp;  
        set_intersection(  
            common_candidates.begin(), common_candidates.end(),  
            current_candidates.begin(), current_candidates.end(),  
            inserter(temp, temp.begin())  
        );  
        common_candidates = temp; // 更新交集结果  
        if (common_candidates.empty()) break; // 无解退出  
    }  

    // 排除观察到的状态本身（题目说明这些不是正确密码）  
    for (const auto& state : states) {  
        common_candidates.erase(state); // 从候选集中删除原状态  
    }  

    // 输出结果  
    if (common_candidates.empty()) {  
        cout << -1 << endl;  
    } else {  
        // 输出任意一个候选密码（由于集合无序，可能输出不同结果）  
        for (const auto& candidate : common_candidates) {  
            for (int num : candidate) {  
                cout << num << ';  
            }  
            cout << endl;  
            break; // 找到第一个即退出  
        }  
    }  
    return 0;  
}