数学 - 密码锁

2021-03-03 12:10:32

题目：ACwing 1351. 密码锁

题目来源：https://www.acwing.com/problem/content/1353/

描述：

农夫约翰的奶牛们总是偷偷的逃出他的农场，去外面为非作歹。

农夫约翰为了防止它们私自逃离农场，购买了一个密码锁，以此阻止奶牛们打开农场大门。

约翰知道他的奶牛们都非常聪明，因此他想要确保它们不能通过简单的尝试一些密码组合，就轻易的将锁打开。

锁具上有三个密码拨盘，每个拨盘上的数字为 1…N，其中 1 和 N 相邻（因为拨盘是圆形的）。

一共有两种可以打开密码锁的数字组合，一组是约翰设置的密码组合，一组是制造商设置的密码组合。

这种锁具有一定的容错性，只要三个表盘上的数字与任意一组正确密码组合的对应位置数字相距两个位置以内，锁均会打开。

例如，假设约翰设置的密码组合是 (1,2,3)，制造商设置的密码组合是 (4,5,6)。

此时我们输入组合 (1,3,5) 就可以将锁打开，因为这与约翰设置的密码接近，输入组合 (2,4,8) 也可以将锁打开，因为这与制造商设置的密码接近。

但是，如果我们输入组合 (1,5,6) 就不能将锁打开，因为它和两个密码都不接近。

现在给定你两个设置好的密码，请你判断一共有多少种密码组合可以将锁打开。

注意，密码组合是有序的，因此 (1,2,3) 和 (3,2,1) 是两种不同的组合。

输入格式
第一行包含整数 N。

第二行包含三个整数，表示约翰设置的密码组合。

第三行包含三个整数，表示制造商设置的密码组合。

输出格式
输出一个整数，表示可以打开锁的密码组合数量。

数据范围
$1≤N≤100$

输入样例：

1
2
3
50
1 2 3
5 6 7

输出样例：

1
249

算法1：$O(n^3)$

暴力枚举，如果匹配，答案 + 1。 n <= 100, 所以暴力枚举也就进行$10^6$次运算，小于$10^8$,是可以过的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 3;
int a[N], b[N];
int n;

bool check(int i, int j, int k)
{
    int res_a = 0, res_b = 0;
    int c[3] = {i, j, k};
    for(int i = 0; i < 3; i++)
    {
        if (abs(a[i] - c[i]) <= 2 || n - abs(a[i] - c[i]) <= 2) res_a ++;
        if (abs(b[i] - c[i]) <= 2 || n - abs(b[i] - c[i]) <= 2) res_b ++;
    }
    return res_a == 3 || res_b == 3;
}


int main()
{
    cin >> n;
    for(int i = 0; i < 3; i++) cin >> a[i];
    for(int i = 0; i < 3; i++) cin >> b[i];

    int res = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            for(int k = 1; k <= n; k++)
                if (check(i, j, k))
                    res ++;
    cout << res << endl;
    return 0;
}

算法2：$O(1)$

数学方法：
对于一个密码当n大于5时每个位置最多有5个数可以进行匹配，那么一共就是$5^3$。

所以一共最多就 $ 2 * 5^3 $
此时再去掉是a又是b的密码就行。

进行讨论：
当a, b 在同一位置上时。 需要减去 5
当a, b 相差 1 时。需要减去 4
当a, b 相差 2 时。需要减去 3
当a, b 相差 3 时。需要减去 2
当a, b 相差 4 时。需要减去 1
当a, b 相差 5 时。减去 0；

这里是a 与 b的差，不是间隔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <algorithm>

using namespace std;
const int N = 3;
int a[N], b[N];
int n;


int both()
{
    int res = 1;
    for(int i = 0; i < 3; i++)
    {
        int x = a[i], y = b[i];
        int d = min(abs(x - y), n - abs(x - y));

        res *= min(n, max(0, 5 - d));
    }
    return res;
}

int single()
{
    int res = 1;
    for(int i = 0; i < 3; i++) res *= min(n, 5);
    return res;
}

int main()
{
    cin >> n;
    for(int i = 0; i < 3; i++) cin >> a[i];
    for(int i = 0; i < 3; i++) cin >> b[i];

    cout << single() + single() - both() << endl;
    return 0;
}
  1. 1. 算法1：$O(n^3)$
  2. 2. 算法2：$O(1)$