枚举所有的地毯，判断哪⼀个地毯能够覆盖(x, y)这个位置。
优化枚举⽅式：

• 因为我们要的是最后⼀个能够覆盖x，y位置的地毯，那么逆序枚举所有的地毯，第⼀次找到覆盖x，y位置的就是结果；
• 如果从前往后枚举，我们⾄少要把所有地毯都枚举完，才能知道最终结果。
  

a要小于等于x
b要小于等于y
x要小于等于a+g
y要小于等于b+k

#include <bits/stdc++.h>
using namespace std;const int N = 1e4 + 10;
int n;
int a[N], b[N], g[N], k[N];
int x, y;int find()
{for (int i = n; i >= 1; i--){if (a[i] <= x && b[i] <= y && a[i] + g[i] >= x && b[i] + k[i] >= y){return i;}}return -1;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> g[i] >> k[i];cin >> x >> y;cout << find() << endl;return 0;
}

方法一：枚举x-y之间所有的数字，然后判断是否回文，如果回文，就拆分成年月日，判断是否是合法日期即可
方法二：仅需枚举年份，因为每个年份对应的回文日期只有一个，拆分成回文形式的月日，然后判断是否合法即可
方法三：枚举所有的月和日，然后拼接成相应的年份，判断是否合法

#include <bits/stdc++.h>
using namespace std;int x, y;
int day[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};int main()
{ios::sync_with_stdio(false);cin.tie(0);int ret = 0;cin >> x >> y;//枚举月日的组合for (int i = 1; i <= 12; i++){for (int j = 1; j <= day[i]; j++){int k = j % 10 * 1000 + j / 10 * 100 + i % 10 * 10 + i / 10;int num = k * 10000 + i * 100 + j;if (x <= num && num <= y) ret++;}}cout << ret << endl;return 0;
}

我们发现，当第⼀列中，第⼀⾏的⼩格⼦的状态确定了之后，其实后续⾏的状态也跟着固定下来。⽽第⼀列中，第⼀⾏的状态要么有雷，要么没有雷，所以最终的答案就在0, 1, 2中。
因此，我们枚举第⼀列中，第⼀⾏的两种状态：要么有雷，要么没雷。然后依次计算剩下⾏的值，看看是否能满⾜所给的数据。

#include <bits/stdc++.h>
using namespace std;const int N = 1e4 + 10;int n;
int a[N], b[N];int check1()
{a[1] = 0;for (int i = 2; i <= n+1; i++){a[i] = b[i-1] - a[i-1] - a[i-2];if (a[i] < 0 || a[i] > 1) return 0;}if (a[n+1] == 0) return 1;else return 0;
}int check2()
{a[1] = 1;for (int i = 2; i <= n+1; i++){a[i] = b[i-1] - a[i-1] - a[i-2];if (a[i] < 0 || a[i] > 1) return 0;}if (a[n+1] == 0) return 1;else return 0;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; i++) cin >> b[i];int ret = 0;ret += check1(); //a[1]不放地雷ret += check2(); //a[1]放地雷cout << ret << endl;return 0;
}

枚举1 ~1<<n之间所有的数，每⼀个数的⼆进制中1的位置可以表⽰数组中对应位置选上该元素。那么1 ~1<<n就可以枚举出原数组中所有的⼦集。
根据枚举的每⼀个状态，选出原数组中对应的元素，然后存在结果数组中

class Solution {
public:vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> ret;int n = nums.size();//枚举所有状态for (int st = 0; st < (1 << n); st++){//根据st的状态，还原出要选的数vector<int> tmp; //存子集for (int i = 0; i < n; i++){if ((st >> i) & 1) tmp.push_back(nums[i]);}ret.push_back(tmp);}return ret;}
};

在这个「拉灯游戏」中我们可以得到「三个性质」：

1. 每⼀个开关「最多只会被按⼀次」。因为按两次及以上是没有意义的，只会让按的次数增多；
2. 按每⼀个开关的「先后顺序」不会影响最后的结果。可以想象，当所有开关按的⽅式确定之后，每⼀个开关被改变的「次数」也就被确定了，也就是说不管你先按谁后按谁，改变的次数是固定的，那么结果就是固定的；
3. 如果「确定了第⼀⾏」的按法，后续⾏的按法就也固定下来了。因为第⼀⾏的按法固定之后，第⼆⾏的按法需要把第⼀⾏「全部点亮」；当第⼆⾏的按法确定之后，第三⾏的按法需要把第⼆⾏「全部点亮」…，依次类推，后续⾏的按法就都确定下来了。

1. 每⼀个0 如果变成1 ，只会「变⼀次」；
2. 当第⼀⾏的「最终状态」确定之后，第⼆⾏的「最终状态」也会确定。所以我们可以「暴⼒枚举」第⼀⾏的最终状态，在这个最终状态「合法」的前提下，「递推」出来第⼆⾏的状态，「以此类推」下去。
   考虑⼀下⼏个问题：
3. 如何枚举第⼀⾏所有的「最终状态」st ：
   枚举1 ∼ (1 << n) - 1 之间所有的数，「每⼀个数」就是第⼀⾏的最终状态；
4. 由于本题只能0 变1 ，所以我们还要「判断」每⼀⾏的最终状态y 「是否合法」：
   很简单，⽐较初始状态x以及最终状态y中「⼆进制表⽰的每⼀位」，如果是0变1 ，就是
   「合法」操作，计数；如果是1变0 ，「⾮法」操作，直接「跳出本次循环」，枚举第⼀⾏的下
   ⼀个状态；
5. 当前⾏的最终状态a[i]确定之后，如何「递推」下⼀⾏的最终状态a[i + 1]：
   规则是当前位置「上下左右」1的个数之和是「偶数」，根据「异或」运算「⽆进位相加」的特
   性，正好就是上下左右位置「异或」的结果是0 。那么下⼀⾏对应位置的状态就是「当前⾏右移⼀位」与「当前⾏左移⼀位」与「上⼀⾏对应位置」异或的结果：

a[i + 1] = (a[i] >> 1) ^ (a[i] << 1) ^ a[i - 1];  

其中a[i] << 1 会造成不合法的位置是1的情况，注意「⾼位截断」：

(a[i] << 1) & ((1 << n) - 1)

#include <iostream>
#include <cstring>
using namespace std;
const int N = 20;
int n;
int a[N]; // ⽤⼆进制存储状态
int t[N]; // 备份
// 判断 x->y 是否合法
// 返回 -1，表⽰不合法
// 其余的数，表⽰合法，并且表⽰ 0->1 的次数
int calc(int x, int y)
{int sum = 0;for(int i = 0; i < n; i++){if(((x >> i) & 1) == 0 && ((y >> i) & 1) == 1) sum++;if(((x >> i) & 1) == 1 && ((y >> i) & 1) == 0) return -1;}return sum;
}
int solve()
{int ret = 0x3f3f3f3f; // 记录最⼩的改变次数// 枚举第⼀⾏的最终状态for(int st = 0; st < (1 << n); st++){memcpy(t, a, sizeof a);int change = st;int cnt = 0; // 统计 0->1 的次数bool flag = 1;for(int i = 1; i <= n; i++){// 先判断 change 是否合法int c = calc(t[i], change);if(c == -1){flag = 0;break;}cnt += c; // 累加次数// 当前⾏的最终状态t[i] = change;// 计算下⼀⾏的最终状态change = t[i - 1] ^ (t[i] << 1) ^ (t[i] >> 1);change &= (1 << n) - 1;}if(flag) ret = min(ret, cnt);}if(ret == 0x3f3f3f3f) return -1;else return ret;
}
int main()
{int T; cin >> T;for(int k = 1; k <= T; k++){// 多组测试数据，记得清空memset(a, 0, sizeof a);cin >> n;for(int i = 1; i <= n; i++) // 避免越界访问{for(int j = 0; j < n; j++){int x; cin >> x;if(x) a[i] |= 1 << j;}}printf("Case %d: %d\n", k, solve());}return 0;
}