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

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

3周前 (06-28)

【2023 CSP-S密码锁(洛谷P9752)】题解:动态规划与集合交集的巧妙应用  动态规划 状态转换 第1张

一、题目解读

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;  
}

五、总结

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

    1. 利用数学规律简化状态转换(单/双拨圈操作);

    2. 通过交集逐步筛选,减少无效候选;

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

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


原创内容 转载请注明出处

分享给朋友:

相关文章

力扣70题:告别暴力递归!从零实现记忆化搜索解法

力扣70题:告别暴力递归!从零实现记忆化搜索解法

题意解析:想象你站在楼梯底部,面前有n级台阶。每次你可以选择跨1级或2级台阶,最终到达顶端的路径有多少种不同的走法?这个问题本质上是在探索分叉决策的叠加效果——当我们把每个台阶处的选择看作二叉树的分支...

CSP-J 2019纪念品题解(洛谷P5662):动态规划+完全背包问题的实战应用

CSP-J 2019纪念品题解(洛谷P5662):动态规划+完全背包问题的实战应用

一、题目解读2019年CSP-J的“纪念品”问题(对应洛谷P5662)要求玩家在T天内通过买卖纪念品最大化金币收益。每天可交易N种商品,需计算最优策略下的最终金币数。题目强调动态规划思维与资源分配优化...

CSP-J方格取数题解|动态规划解法|洛谷P7074代码解析

CSP-J方格取数题解|动态规划解法|洛谷P7074代码解析

一、题目解读题目要求在一个n×m的网格中,从左上角到右下角选择一条路径,路径上的数字可重复取用,求取数之和的最大值。路径限制为仅能向右或向下移动。需注意路径的灵活性与重复取数的可能性,传统单向动态规划...

牛客12576题解题全解析:动态规划+质因数分解实现跳跃问题最优解

牛客12576题解题全解析:动态规划+质因数分解实现跳跃问题最优解

一、题目解读牛客12576题是一道经典的算法题,要求给定起点N和终点M,求解从N到M的最少跳跃次数。题目考察的核心在于路径优化与动态规划思想,需结合数论中的质因数分解技巧,通过合理设计算法降低时间复杂...

NOIP 2008火柴棒等式题解(C++代码实现)  动态规划与枚举算法详解

NOIP 2008火柴棒等式题解(C++代码实现) 动态规划与枚举算法详解

一、题目解读火柴棒等式问题(NOIP 2008,洛谷P1149)要求使用给定数量的火柴棒,构造形如 A + B = C 的等式,其中A、B、C均为整数,且火柴棒总数恰好等于输入值。需统计符合条件的等式...

洛谷P4551题解题报告:图论与Trie树优化异或路径问题的实战解析

洛谷P4551题解题报告:图论与Trie树优化异或路径问题的实战解析

一、题目解读洛谷P4551题要求在一个无向图中,寻找任意两点路径权值异或后的最大值。题目输入为图的边信息(点数n和n-1条边),每条边包含起点、终点及权值。需输出所有路径中权值异或的最大值。问题核心在...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。