不知道哪的算法笔记 -> Enumerate

Enumerate

OI wiki

概念

枚举（英语：Enumerate）是基于已有知识来猜测答案的一种问题求解策略。
枚举的思想是不断地猜测，从可能的集合中一一尝试，然后再判断题目的条件是否成立。

TL;DR

一个一个试出来喵！

例题

一个数组中的数互不相同，求其中和为0的数对的个数。

可行的办法是遍历每一个元素，给它们相加看是否和为0

for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
        if (a[i] + a[j] == 0) ++ans;

然而第一个数和第二个数，正反着来都一样，所以只需要让第二个数下标的范围（也就是尝试第二个数的次数）小于第一个数的下标，就不会让数反过来再来一次，最后给总数乘以2就好了

for (int i = 0; i < n; ++i)
    for (int j = 0; j < i; ++j)
        if (a[i] + a[j] == 0) ++ans;

枚举其中一个数之后，题目的条件已经确定了其他的要素（另一个数）的条件，如果能直接判断题目要求的那个数是否存在，就可以省掉枚举后一个数的时间喵。

这个方法很巧妙，可能有点难以理解。如果不能理解，请多次阅读这段话喵。

在这里，‘桶’这个数组的下标中，MAXN代表0，当迭代器到达元数组a中的i标元素时，met数组先进行一次判断，当前met数组的下标MAXN - a[i]是否和已经被标记为“遍历过的”met数组中元素的下标相同。然后无论如何，迭代器进行到这里，当前met中的元素就会被标记“遍历过的”。
哈气，意义难以理解，其实……
设想如果当前的i = 2，a[i] = a[2] = 3，MAXN = 10
经过memset，met数组已经全部被初始化为false。
那么，MAXN - a[i] = 10 - 3 = 7
met[MAXN - a[i]]也就是met[7]被标记为true；
之后假如i = 4，a[i] = a[4] = -3，而这个-3是我们要寻找的一个元素
那么，MAXN - a[i] = 10 - (-3) = 7
而met[7]已经被标记为true，所以ans增1
最终，这里只需要进行n次循环，就能覆盖所有的情况喵

#include <cstring>
constexpr int MAXN = 100000;  // 此处 MAXN 是数组内元素的值域

int solve(int n, int a[]) {
    bool met[MAXN * 2 + 1];  // 创建一个能装下 [-MAXN, MAXN] 的桶
    memset(met, 0, sizeof(met));
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (met[MAXN - a[i]]) ++ans;  // 如果桶内有想要的元素，答案加一
        met[MAXN + a[i]] = true;  // 无论如何，都要把当前元素放进桶里
    }
    return ans;
}

有一个由按钮组成的矩阵，其中每行有6个按钮，共5行。每个按钮的位置上有一盏灯。当按下一个按钮后，该按钮以及周围位置(上边、下边、左边、右边)的灯都会改变一次。即，如果灯原来是点亮的，就会被熄灭；如果灯原来是熄灭的，则会被点亮。在矩阵角上的按钮改变3盏灯的状态；在矩阵边上的按钮改变4盏灯的状态；其他的按钮改变5盏灯的状态。请你写一个程序，确定需要按下哪些按钮，恰好使得所有的灯都熄灭。

一开始看到题目，想要表示一个5x6的矩阵，我们就要定义一个二维数组了

这里玩花活用容器会慢

如果我们把所有可能的状态表示出来的话，就有$2^{30}$种可能，这样的开销太大了
我们的目标是给所有的灯都熄灭，所以我们发现：按下一个按钮，它正上面的灯会改变，当前行的情况可以先忽略让下一行去处理，而仅仅注意当前行每个按钮上面的灯的状态，按这个按钮去控制它，可以引入“串行”的思想。
第一行的状态，就对应了下面行操作的唯一一种情况，每一行的操作都是：尽力熄灭上一行的灯。
当到达最后一行时，如果有当前行无论如何操作都不能熄灭的情况，那这次第一行的状态就是不合法的。

还可以发现，在边/角上的按钮，操作范围也是周围四个灯，但是因为触及边界，所以只能操作界内的灯，如果按照5x6矩阵来表示，将会很麻烦，需要判断是否处于边界并做出相应更改。
为了简化这一过程，就在每个边外加入一行，使其变为7x8矩阵，这样忽略在界外的元素就好，不用去做特殊的处理了。

一个灯在被影响两次后，就会回到一开始的状态，这和一位二进制加法相似。所以，我们只需要表示“按下”这一动作为1，让两个“按下”作用的灯的“状态”相加，并将状态在二进制加法中表示，只考虑末尾一位就可。所以我们把这些1在十进制中相加再模除2，就是在二进制中表示的最后一位。

我们最后把最后一行的所有灯周围直接影响到它的所有操作都加一遍，看看它是不是0。如果它是1，这次的第一行operate1st[]是不可行的，就去到while (!operate(operate1st))进行更换，直到所有的情况都尝试一次……

#include <iostream>
using namespace std;

int row = 5;
int col = 6;

// 状态矩阵（包含边界）
int states[row+2][col+2] = {0};

// 操作矩阵（包含边界）
int operations[row+2][col+2] = {0};

/**
 * 根据第一行操作计算整个操作矩阵
 * 返回最后一行是否满足条件
 */
bool operate(int operate1st[]) {
    // 设置第一行操作
    for (int j = 0; j < col; j++) {
        operations[1][j+1] = operate1st[j];
    }

    // 计算2~5行的操作
    for (int i = 1; i < row; i++) {
        for (int j = 1; j <= col; j++) {
            operations[i+1][j] = (operations[i][j] + operations[i-1][j] + 
                                 operations[i][j-1] + operations[i][j+1] + 
                                 states[i][j]) % 2;
        }
    }

    // 检查最后一行是否满足条件
    for (int j = 1; j <= col; j++) {
        int check = (states[row][j] + operations[row][j-1] + 
                    operations[row][j] + operations[row][j+1] + 
                    operations[row-1][j]) % 2;
        if (check == 1) {
            return false;
        }
    }
    return true;
}

int main() {
    for (int i = 1; i <= row; i++) {
        for (int j = 1; j <= col; j++) {
            cin >> states[i][j];
        }
    }
    int operate1st[col] = {0}; // 第一行操作序列

    // 枚举所有可能的第一行操作组合 (2^6=64种)
    while (!operate(operate1st)) {
        // 二进制递增：类似二进制计数器
        operate1st[0]++;
        int index = 0;
        while (operate1st[index] > 1 && index < col - 1) {
            operate1st[index] = 0;
            index++;
            operate1st[index]++;
        }
    }

    // 输出结果矩阵 (5x6)
    for (int i = 1; i <= row; i++) {
        for (int j = 1; j <= col; j++) {
            cout << operations[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}