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

贾蔷
• 阅读 13

【2023 CSP-S密码锁(洛谷P9752)】题解:动态规划与集合交集的巧妙应用 一、题目解读 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算法的结合提升了效率与可读性。

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

点赞
收藏
评论区
推荐文章
贾蔷 贾蔷
3星期前
2013 蓝桥杯 省赛B组 翻硬币(洛谷P8597题) 从暴力BFS到贪心算法的优化之路
一、问题背景与理解洛谷P8597是一道经典的翻硬币问题,题目描述如下:给定两个由''和'o'组成的字符串s1和s2,分别表示初始状态和目标状态。每次操作可以选择任意位置开始翻转连续的k个硬币(''变'o','o'变'')。要求计算出从初始状态变为目标状态所
贾蔷 贾蔷
3星期前
2025年GESP七级等价消除(洛谷P11965)代码解析与优化策略
一、题目解读2025年GESP七级考试中的“等价消除(洛谷P11965)”问题要求统计给定字符串中满足等价条件的子串数量。所谓“等价子串”,是指子串中所有字符出现的次数均相同。题目需要高效算法解决,考验对字符串处理和状态压缩的掌握。二、解题思路采用位运算
贾蔷 贾蔷
5天前
2023年GESP六级小杨握手问题(洛谷B3874):Fenwick树求解逆序对的代码解析
一、题目解读“小杨的握手问题”源自2023年GESP六级考试(对应洛谷题目B3874)。题目描述为:给定一个长度为N的排列,每次将当前数与之前未访问过的数握手,求总共握手次数。本质上是求排列中逆序对的个数,即统计每个数右侧比它小的元素数量。需设计高效算法在
深度学习 深度学习
5天前
【CSP-S 2019】括号树(洛谷P5658):栈+DFS
一、题目解读括号树问题(洛谷P5658)要求处理一个由括号序列转化的树结构:每个节点表示一个括号,'('为子节点,')'为父节点。题目给定一棵n个节点的树,需计算每个节点的深度(括号层数),并输出所有节点深度与节点编号乘积的异或和。核心在于将括号序列转化为
深度学习 深度学习
5天前
洛谷1111题解:基于Kruskal算法与并查集的最小生成树实现
一、题目解读洛谷1111题是一道经典的图论问题,要求构建一个无向图的最小生成树,并输出其最大边权值。题目核心在于通过给定的边集合,找到连接所有节点的最小权值子集,同时保证无环。这通常涉及最小生成树算法(如Kruskal)的应用,需要高效处理边权重与节点连通
深度学习 深度学习
5天前
2024蓝桥杯省赛B组前缀总分(洛谷P12124)解题思路与代码详解
一、题目解读2024年蓝桥杯省B组题目“前缀总分”(对应洛谷P12124)要求计算给定字符串集合中,所有前缀的最长公共前缀(LCP)的总分,并找出通过移动字符位置后可能获得的最大总分。题目考察字符串处理与动态规划能力,需高效计算LCP并优化得分策略。二、解
贾蔷 贾蔷
5天前
2023年GESP六级题解:洛谷P10108闯关游戏动态规划解法详解
一、题目解读本文针对2023年GESP六级题目“闯关游戏”(洛谷P10108)进行详细解析。题目要求玩家通过不同关卡路径选择,计算从起点到终点的最大得分。关卡间存在跳跃规则,需结合动态规划思想设计高效算法,最终输出最优得分。二、解题思路采用动态规划(Dyn
深度学习 深度学习
5天前
洛谷P2034题解:动态规划+单调队列优化求解最大K段子段和问题
一、题目解读洛谷P2034题目要求给定一个长度为n的整数数组,将其分成不超过k段,求各段和的最大值。该问题属于经典动态规划问题的扩展,需结合优化技巧高效求解。二、解题思路采用动态规划单调队列优化的策略。核心思想是定义状态dp
深度学习 深度学习
3天前
2024年蓝桥杯国赛A组题 九宫格全解析:基于BFS算法的代码实现与优化
2024年蓝桥杯国赛A组题九宫格全解析:基于BFS算法的代码实现与优化蓝桥杯国赛九宫格问题BFS算法代码解析解题步骤第1张一、题目解读2024年蓝桥杯国A的九宫格题目(对应洛谷P10578)要求通过旋转九宫格中的2x2区域,实现从初始状态到目标状态的转换,
深度学习 深度学习
20小时前
2012年NOIP提高组「借教室」(洛谷P1083)解题思路与二分查找优化代码解析
一、题目解读本题为2012年NOIP提高组中的「借教室」问题(洛谷P1083),要求处理教室借用订单的分配问题。给定n天每天可用教室数量r和m个订单(订单包含需求教室数d、开始日期s、结束日期t),判断能否通过删除部分订单使所有订单满足教室容量限制。若能,