2023 密码锁 · 方案一全域枚举

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

密码锁 5 个拨圈（0-9 循环）

2023
枚举

正文

// CSP-S 2023 复赛 T1 · 密码锁（方案一：全域枚举，最直白）
// 原题：https://oj.yecheng.tv/p/CSPS2023A
// 题意：密码锁 5 个拨圈（0-9 循环）。真实密码满足：n 个记录状态中，
//       每个状态要么与真实密码完全相同，要么恰好"一个拨圈转一格"
//       之差。问可能的真实密码个数。
// 思路（全域枚举）：
//   拨圈组合只有 10^5 种，逐个验证：对每个候选 T，统计它与每个
//   记录 S_i 的"差异位数 + 差异方向"，合法 ⟺ 每个记录与 T 的差异
//   是 0 位（相同）或恰 1 位且该位差 ±1（mod 10）。
//   复杂度 10^5 × 8 = 8e5，远小于限制。
// 复杂度：O(10^5 · n)。
// 易错点：
//   1. 拨圈是循环的：9 与 0 差一格（(a-b+10)%10 ∈ {1, 9}）；
//   2. 记录与密码相同也合法（差异 0 位）；
//   3. n 个记录必须全部满足，不是任意一个。
#include <cstdio>

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

// 候选 t 与记录 s 的差异是否合法
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;
        diff++;
        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 a = 0; a < 10; a++)
        for (int b = 0; b < 10; b++)
            for (int c = 0; c < 10; c++)
                for (int d = 0; d < 10; d++)
                    for (int e = 0; e < 10; e++) {
                        int t[6] = {0, a, b, c, d, e};
                        bool good = true;
                        for (int i = 1; i <= n && good; i++)
                            if (!ok(t, st[i])) good = false;
                        if (good) ans++;
                    }
    printf("%d\n", ans);
    return 0;
}

2023 密码锁 · 方案一 全域枚举

正文

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

2023 密码锁 · 方案一全域枚举