2023年CSP-S密码锁（洛谷P9752）：集合运算与候选筛选策略

一、问题背景

2023年CSP-S竞赛的密码锁问题要求通过观察多个异常状态，推断出原始正确密码的可能组合。密码锁由5个拨圈组成，每次操作可以是单拨圈转动或相邻双拨圈同步转动。

二、核心算法解析

1. 候选密码生成

set<vector<int>> generate_candidates(const vector<int>& state) {
    set<vector<int>> candidates;
    // 单拨圈操作：每个拨圈独立转动-9到9格（除0）
    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; // +20处理负数取模
            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;
}

2. 集合交集处理

// 取所有观察状态的候选密码交集
set_intersection(
    common_candidates.begin(), common_candidates.end(),
    current_candidates.begin(), current_candidates.end(),
    inserter(temp, temp.begin())
);

三、完整代码实现

#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);
    
    int n;
    cin >> n;
    vector<vector<int>> states(n, vector<int>(5));
    
    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);
    }
    
    cout << common_candidates.size() << endl;
    return 0;
}