CF1097B 题解

· · 题解

开锁问题 题解

题目大意

有一个锁，初始指针指向 0 刻度，可进行 n(1 \le n \le 15) 次逆时针或顺时针转动，第 i 次转动 a_i(1 \le n \le 15) 度，如果可以再次转到 0 刻度，输出 YES，否则输出 NO。

题目解析

大部分题解都使用的是 DFS 二决策枚举，还有使用 位运算 + 递推 的，本文就不再赘述。本文介绍一种二进制枚举的方法。

我们每次转动都有 2 种选择选择：顺时针转动或逆时针转动。总共有 n 次转动，因为 n 很小，所以我们可以使用一个 0 到 2 ^ n - 1 之间的二进制数字来表示转动的方案。（2 ^ {15} \approx 3 \times 10 ^ 4）

例如 (1100)_2 代表的就是先顺时针转动 2 次，再逆时针转动 2 次。

位运算简单学习（已学过可跳过）

位运算是一种二进制专用的运算，没有进位和借位，每一位之间相互独立。

按位与 &：对两个数字每一位计算，两位都为 1，答案为 1，至少一位为 0，答案为 0。

按位或 |：对两个数字每一位计算，两位都为 0，答案为 0，至少一位为 1，答案为 1。

按位异或 |：对两个数字每一位计算，两位不同，答案为 1，两位相同，答案为 0。

按位非 ~：对一个数字每一位计算，这一位为 0，答案为 1，这一位为 1，答案为 0。

左移 <<：对一个数字每一位计算，最左边舍弃，最右边补 0。

右移 >>：对一个数字每一位计算，最右边舍弃，最左边补 0。

注：位运算的运算优先级很低，当你不知道它的运算优先级时，你可以多加一些括号来增高运算优先级。

代码

#include <iostream> 
using namespace std;

int main()
{
    int n; // 输入 
    cin >> n;
    int a[16];
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
    for (int i = 0; i < (1 << n); ++i) 
    // 枚举，i 的二进制表示转动方案（从 1 到 2 的 n 次方），j 表示转动到了第几位 
    {
        int sum = 0;
        for (int j = 0; j < n; ++j)
        {
            if ((i >> j & 1) == 1) // i 的二进制的从右往左数第 j 位为 1 
            {
                sum += a[j];
            }
            else
            {
                sum -= a[j];
            }
        }
        if (sum % 360 == 0) // 输出答案 
        {
            cout << "YES";
            return 0;
        }
    }
    cout << "NO";

    return 0;
}