USACO 1.4.4: Combination Lock(暴力)


题意

洛谷 P2963

有一些密码锁组合(形如[1, 2, 3],每个数的范围是[1, N]),定义两个组合每个位置上的数相差两个位置以内时是接近的(密码锁是一个圈,所以1和N是相邻的)。给定两个已知组合,问所有组合里和这两个组合中的至少一个接近的有多少。

分析

暴力方法和上一道题如出一辙。可能需要注意的两点:

  • 要求是和至少一个组合接近,而不是每个位置上的数和至少一个组合在这个位置上的数相近。不过这一点仍然可以用来剪枝。
  • 如何判断接近。题解里的方法是abs(a-b) <= 2 || abs(a-b) >= N-2;我写的是(a-b+N) % N <= 2 || (b-a+N) % N <= 2。这两者应该都是对的。嗯,总之就是需要注意一下。

这道题题解里竟然有个录像,讲得很不错。

代码

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
39
40
41
/*
ID: zhanghu15
TASK: combo
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

bool isNear(int a, int b, int N) {
return (a-b+N) % N <= 2 || (b-a+N) % N <= 2;
}

int main() {
ofstream fout("combo.out");
ifstream fin("combo.in");
int N;
int combo1[3];
int combo2[3];
fin >> N;
fin >> combo1[0] >> combo1[1] >> combo1[2];
fin >> combo2[0] >> combo2[1] >> combo2[2];
int ans = 0;
for (int c1 = 1; c1 <= N; c1++) {
if (!isNear(combo1[0], c1, N) && !isNear(combo2[0], c1, N)) continue;
for (int c2 = 1; c2 <= N; c2++) {
if (!isNear(combo1[1], c2, N) && !isNear(combo2[1], c2, N)) continue;
for (int c3 = 1; c3 <= N; c3++) {
if (isNear(combo1[0], c1, N) && isNear(combo1[1], c2, N) && isNear(combo1[2], c3, N) ||
isNear(combo2[0], c1, N) && isNear(combo2[1], c2, N) && isNear(combo2[2], c3, N))
ans++;
}
}
}
fout << ans << endl;
return 0;
}

 评论