Moe's CF Life

哈喽，主人！你好喵～是我，你最喜欢的小猫娘。今天又遇到了什么有趣的题目呀？嗯？一个关于组合锁的问题？听起来很有趣的样子！让本猫娘来看看怎么帮 Petr 解决这个小麻烦吧，喵呜～

题目大意

这道题是说呀，有一个刻度是 360 度的组合锁，指针一开始指着 0。我们需要精确地转动 n 次，每次转动的角度是 a_i。对于每一次转动，我们都可以选择顺时针或者逆时针。

我们的任务就是，判断一下是否存在一种转动方向的组合，使得在完成所有 n 次转动后，指针能正好回到 0 的位置。如果可以的话，就告诉 Petr "YES"，不然就告诉他 "NO"，让他去买新车好了，喵～

简单来说，就是给我们 n 个数字，每个数字前面可以放 + 号或者 - 号，问我们能不能找到一种组合，让这 n 个数字的代数和是 360 的倍数（包括 0）。

题解方法

主人请看，题目里说 n 的最大值只有 15 诶！这是一个非常非常重要的信息喵！n 这么小，意味着我们可以尝试所有可能的组合！

对于每一次转动，我们都有两种选择：顺时针（可以看作是加上这个角度）或者逆时针（减去这个角度）。那么对于 n 次转动，总共的可能性就有 $2 \times 2 \times \dots \times 2$ （n个2相乘），也就是 $2^n$ 种。

当 n=15 的时候，2¹⁵ = 32768，这个数字对于计算机来说简直是小菜一碟，一瞬间就能算完啦。

所以，我们的核心思路就是暴力枚举！把这 2ⁿ 种组合全都试一遍。只要其中有任何一种组合，能让最终的角度总和是 360 的倍数，那答案就是 "YES"。如果试完了所有组合都不行，那答案就是 "NO"。

那么，怎么优雅地枚举这 2ⁿ 种组合呢？这里就要用到一个超级好用的技巧啦，叫做位运算 (Bitmasking)！

我们可以用一个 n 位的二进制数来表示一种组合。比如，当 n=3 时，我们可以用 000 到 111 这 8 个二进制数来代表 8 种组合。我们可以约定，如果第 j 位是 1，就代表第 j 次转动是顺时针（+）；如果第 j 位是 0，就代表是逆时针（-）。

举个栗子，对于样例一：n=3, 角度分别是 10, 20, 30。

组合 110 (二进制) 对应的十进制是 6。它代表第 0 个角度（30）是 -，第 1 个角度（20）是 +，第 2 个角度（10）是 +。总和就是 -30 + 20 + 10 = 0。0 % 360 == 0，所以我们找到了一个可行的方案！

这样一来，我们只需要一个从 0 到 2ⁿ - 1 的循环，在循环里面根据当前循环变量 i 的二进制表示，来计算角度总和，然后判断一下就行啦，是不是很清晰明了呢，喵～

题解代码

这是 C++ 的实现代码，本猫娘给主人加上了详细的注释，方便理解哦～

cpp

#include <iostream>
#include <vector>

int main() {
    // 喵～ 加速一下输入输出，让程序跑得更快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n; // 读取转动的次数 n
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i]; // 读取每次转动的角度
    }

    bool possible = false; // 用一个 flag 来记录是否找到了可行的方案

    // 总共有 2^n 种组合。1 << n 就是 2 的 n 次方，喵～
    int num_combinations = 1 << n;

    // 我们用一个整数 i 从 0 遍历到 2^n - 1
    // 每一个 i 的二进制形式就代表了一种组合
    for (int i = 0; i < num_combinations; ++i) {
        int current_angle = 0; // 计算当前组合的总角度

        // 对于 n 次转动中的每一次 (j 从 0 到 n-1)
        for (int j = 0; j < n; ++j) {
            // 这里就是位运算的魔法啦！
            // (i >> j) & 1 用来检查 i 的二进制表示中，从右往数的第 j 位是不是 1
            if ((i >> j) & 1) {
                // 如果第 j 位是 1，我们就把它当做顺时针，加上角度
                current_angle += a[j];
            } else {
                // 如果第 j 位是 0，我们就把它当做逆时针，减去角度
                current_angle -= a[j];
            }
        }

        // 检查最终的总角度是不是 360 的倍数
        // C++ 的取模运算对负数也有效，所以不用担心 current_angle 是负数的情况
        if (current_angle % 360 == 0) {
            possible = true; // 找到啦！太棒了喵！
            break; // 既然已经找到了，就没必要再继续找了，直接跳出循环
        }
    }

    if (possible) {
        std::cout << "YES" << std::endl;
    } else {
        std::cout << "NO" << std::endl;
    }

    return 0;
}

知识点介绍：位运算 (Bitmasking)

位运算是直接对整数在内存中的二进制位进行操作，速度非常快，是算法竞赛中非常有用的一个工具，喵！

在这道题里，我们主要用了它来枚举子集/组合。

一个包含 n 个元素的集合，它的所有子集（包括空集和全集）一共有 2ⁿ 个。这和我们 n 次旋转，每次都有 + 或 - 两种选择的情况是一一对应的。

核心操作：

左移 <<
- 1 << n 的意思是将数字 1 的二进制表示向左移动 n 位，右边空出的位用 0 填充。
- 比如 1 << 3，1 的二进制是 ...0001，左移 3 位变成 ...1000，这个数就是十进制的 8。
- 所以 1 << n 是计算 $2^n$ 的一种快速方法。
右移 >>
- i >> j 的意思是将整数 i 的二进制表示向右移动 j 位，左边空出的位通常用 0 填充（对于无符号数）或者用符号位填充（对于有符号数，但在这里不影响）。
- 它的效果是把第 j 位（从右往左，从0开始数）移动到最右边（第0位）。
按位与 &
- a & b 会将 a 和 b 的二进制位对齐，然后对每一位进行与操作。只有当两个位都是 1 时，结果的对应位才是 1，否则是 0。
- ...1 & ...1 -> 1
- ...1 & ...0 -> 0
- ...0 & ...1 -> 0
- ...0 & ...0 -> 0
- x & 1 这个操作非常有用，它可以用来判断 x 的二进制表示的最低位（最右边一位）是 0 还是 1。因为 1 的二进制只有最低位是 1，其他都是 0。

组合起来：

if ((i >> j) & 1) 这句代码就是位运算的精髓所在了！

i >> j：把 i 的第 j 位移动到最右边。
& 1：然后判断这个被移到最右边的位是 1 还是 0。

通过这种方式，我们就可以在一个循环内，轻松地检查整数 i 所代表的二进制组合中，每一位的状态，从而决定是 + 还是 -。

希望本猫娘的解释能帮到主人哦！如果还有其他问题，随时都可以来找我玩，喵～ ❤️

题目大意 ​

题解方法 ​

题解代码 ​

知识点介绍：位运算 (Bitmasking) ​

核心操作： ​

组合起来： ​