P9752 [CSP-S 2023] T1 密码锁:题解

题目。

F1：朴素算法

思路简析

观察数据范围：1 \leqslant n \leqslant 8。

可以暴力（这告诉我平时要多打语言月赛，我甚至都对数据点进行了分类讨论，但是我不记得使用暴力，最后我只得到了 70 pts）。

使用 5 个循环列举五个密码；

对其判断有几个不同：只能有一个或两个不同。

若有两个则判断是否挨着：必须挨着。

再进行对于两个现在的数字与枚举出来的密码的差值是否相同的判断，若是，则可以检查下一个给出的排列，否则直接退出。

代码实现

对于两个现在的数字与枚举出来的密码的差值需要进行计算，且不可以直接计算转动的次数，那样从 x 到 x+1 和从 x 到 x-1 就是一样的了。

可以将其看做从该数字变大为整数，变小为负数，因为从一个数字到另一个数字有两种方法，所以需要比较再选出小的（大的也可以）。

code：

#include <bits/stdc++.h>
namespace {
#define filein(x) freopen(x".in", "r", stdin)
#define fileout(x) freopen(x".out", "w", stdout)
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
using namespace std;
#define ll long long
#define db double
#define cT const T&
template <typename T>
T max (T& x, cT y) { return x>y? x : y;}
template <typename T>
T min (T& x, cT y) { return x<y? x : y;}
#undef cT
const int man = 10;
} ;
#define is(x, y) (bool(x==y && x&y))

int n, res;
int a[man][6];
int mds (int, int) ;
int main () {
    // file("test");
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) 
        for (int j = 1;j <= 5; ++ j) scanf("%d", a[i]+j);
    for (int i1 = 0; i1 <= 9; ++ i1) 
    for (int i2 = 0; i2 <= 9; ++ i2) 
    for (int i3 = 0; i3 <= 9; ++ i3) 
    for (int i4 = 0; i4 <= 9; ++ i4) 
    for (int i5 = 0; i5 <= 9; ++ i5) {
        int f = 1, b;
        for (int j = 1; j <= n; ++ j) {
            int a1, a2, a3, a4, a5;
            a1 = mds(i1, a[j][1]), 
            a2 = mds(i2, a[j][2]), 
            a3 = mds(i3, a[j][3]), 
            a4 = mds(i4, a[j][4]), 
            a5 = mds(i5, a[j][5]), 
            b = bool(a1) + bool(a2) + bool(a3) + bool(a4) + bool(a5);
            // if (b == 2) printf("%d %d %d %d %d\n", i1, i2, i3, i4, i5);//printf("KK%d %d %d %d %d %d\n", b, a1, a2, a3, a4, a5), 
            if (b == 1) continue;
            if (b == 2) if (is(a1, a2) || is(a2, a3) || is(a3, a4) || is(a4, a5)) continue;
            f = 0;
            break;
        } res += f;
        // if (f && b == 2) printf("%d\n", b);
        // if (f && b == 2) printf("%d %d %d %d %d\n", i1, i2, i3, i4, i5);
    }
    printf("%d\n", res);
    // for (int i1 = 0; i1 <= 9; ++ i1) 
    //     for (int i2 = 0; i2 <= 9; ++ i2) 
    //         printf("%d-%d=>%d\n", i1, i2, mds(i1, i2));

    return 0;
}

// ---

int mds (int x, int y) { 
    if (x == y) return 0;
    int r1 = x-y, r2 = y+10-x;
    if (x > y) return r1<r2? -1*r1: r2;
    else {
        r1 += 10, r2 -= 10;
        return r1<r2? -1*r1: r2;
    }
}

F2：哈希算法

思路简析

对于每个输入数列扩展所有可以更改的密码。很容易证明每个数列扩展的每个密码只会被统计一次，所以每个被统计 n 次的密码就是一种可能的情况。

代码实现

#include <bits/stdc++.h>
namespace {
#define filein(x) freopen(x".in", "r", stdin)
#define fileout(x) freopen(x".out", "w", stdout)
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
using namespace std;
#define ll long long
#define db double
#define cT const T&
template <typename T>
T max (T& x, cT y) { return x>y? x : y;}
template <typename T>
T min (T& x, cT y) { return x<y? x : y;}
#undef cT

const int man = 5e4+10, mam = 5e4+10, mmp = 1e9+1;
}

int n, res;
string s;
map<string, int> mp;
void add (char &) ;
int main () {
    file("test");
    scanf("%d\n", &n);
    for (int i = 1; i <= n; ++ i) {
        s = "$";
        for (int x, j = 1; j <= 5; ++ j) scanf("%d", &x), s += x+'0';
        for (int j = 1; j <= 5; ++ j) 
            for (int k = 0; k <= 9; ++ k) add(s[j]), ++ mp[s];
        for (int j = 1; j <= 4; ++ j)
            for (int k = 0; k <= 9; ++ k) add(s[j]), add(s[j+1]), ++ mp[s];
        } 
    for (auto p : mp) res += (p.second==n);
    printf("%d", res);
    return 0;
}

// ---

void add (char &c) { 
    c = c=='9'? '0': (c+1);
    return ;
}