CF1097B Petr and a Combination Lock 题解

Content

有一个锁，它只有指针再次指到 \(0\) 刻度处才可以开锁（起始状态如图所示，一圈 \(360\) 度）。

以下给出 \(n\) 个操作及每次转动度数，如果可以通过逆时针或顺时针再次转到 \(0\) 度输出 YES，否则输出 NO。

数据范围：\(1\leqslant n\leqslant 15\)，\(1\leqslant a_i\leqslant 180\)。

Solution

不知道为什么 19 年 4 月就做了这题，现在看到这题想写篇题解，于是就有了这篇题解（

我们一看到数据范围 \(n\leqslant 15\)，因此可能的选择方向的方案数不会超过 \(2^{15}\)。这是一个非常小的数字，然后你就可以暴搜去一个一个枚举转向方案，看是否有合法的就行了。

Code

#include <cstdio>

#include <algorithm>

using namespace std;

int n, flag, a[20], used[20];

inline void check() {

	int sum = 0;

	for(int i = 1; i <= n; ++i)

		sum += a[i] * (used[i] ? -1 : 1);

	if(sum % 360 == 0)

		flag = 1;

}

inline void dfs(int x) {

	if(x == n + 1)

		return check();

	dfs(x + 1);

	used[x] = 1;

	dfs(x + 1);

	used[x] = 0;

}

int main() {

	scanf("%d", &n);

	for(int i = 1; i <= n; ++i)

		scanf("%d", &a[i]);

	dfs(1);

	printf(flag ? "YES" : "NO");

	return 0;

}

巴特西

CF1097B Petr and a Combination Lock 题解

Content

Solution

Code

最新文章

热门文章