2023 密码锁 · 方案二基准候选收敛

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 2/5 · 共 1526 字

拿第一条记录当模板生成候选，逐条记录收敛

2023
枚举

正文

// CSP-S 2023 复赛 T1 · 密码锁（方案二：以首个记录生成候选，O(18n)）
// 原题：https://oj.yecheng.tv/p/CSPS2023A
// 题意：同方案一。
// 思路（候选收敛）：
//   真实密码 T 与每个记录的差异 ≤ 一位 ±1。取第一个记录 S_1 为基准：
//   T 只有 19 种可能：S_1 本身、或某一位 +1 / −1（5×2 = 10 种）。
//   ——等等，T 与 S_1 的差异最多一位 ±1，所以候选 = S_1 ∪
//   {S_1 第 i 位 ±1}，共 1 + 10 = 11 种。逐个用 n 个记录验证即可。
//   比全域枚举快 4 个数量级（本题数据小体现不出，但思路可迁移：
//   "用第一个约束把候选空间压到常数"）。
// 复杂度：O(11 · n)。
// 易错点：
//   1. +1 / −1 都要试（循环拨圈 0−1 = 9）；
//   2. 候选 S_1 本身也要验证其余 n−1 条记录；
//   3. 验证函数与方案一相同（差异 0 位或 1 位 ±1）。
#include <cstdio>

int n;
int st[10][6];

bool ok(int* t, int* s) {
    int diff = 0;
    for (int i = 1; i <= 5; i++) {
        int d = (t[i] - s[i] + 10) % 10;
        if (d == 0) continue;
        if (d != 1 && d != 9) return false;
        if (++diff > 1) return false;
    }
    return true;
}

int main() {
    freopen("lock.in", "r", stdin);
    freopen("lock.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= 5; j++) scanf("%d", &st[i][j]);
    int ans = 0;
    for (int pos = 0; pos <= 5; pos++) {
        for (int dir = 0; dir < 2; dir++) {
            if (pos == 0 && dir == 1) continue;    // S_1 本身只算一次
            int t[6];
            for (int j = 1; j <= 5; j++) t[j] = st[1][j];
            if (pos > 0) t[pos] = (t[pos] + (dir == 0 ? 1 : 9)) % 10;
            bool good = true;
            for (int i = 2; i <= n && good; i++)
                if (!ok(t, st[i])) good = false;
            if (good) ans++;
        }
    }
    printf("%d\n", ans);
    return 0;
}

2023 密码锁 · 方案二 基准候选收敛

正文

CSP-S 标程 · 复赛真题的其它内容

2023 密码锁 · 方案二基准候选收敛