P1334 瑞瑞的木板
这道题想都没想直接合并果子过掉
P8743 [蓝桥杯 2021 省 A] 异或数列
思路
这道题是到思维题，我们先来看一看这道题如何理解：首先可以看作 \(A\)、 \(B\) 各有 \(20\) 个格子，然后对于每一个数，也分成二十个格子，每个格子就是填这个数在二进制下这一位是什么，那么题目就可以简化为，每个格子可以给自己异或一个 \(1\) 或 \(0\)，共有二十轮，从最高轮开始一点一点往下比，如果比出胜负了，就不比了，那就只要考虑一位了，我们发现，如果这个位置是 \(1\) 的数的个数是偶数个，那么不管怎么取，那两边的这一位的最终结果必然相同，因为相加的两个数要是偶数，那么它们的奇偶性必然相同，所以如果是偶数个，就可以往下比了，那如果是奇数个（因为更高位的已经比完了，所以可以将其看作最高位），那么如果是个数是 \(1\)，那 \(A\) 必然直接取它，然后获胜，否则就会有一个邪恶的做法，就是你取完以后，我不取它，然后等时机成熟，再去取它（好像也不是很邪恶），那这种做法的应对方式就是你不取，那我也不取，可是我们知道数字有限，所以总会有一个人先取这数，那成功的关键就在于有多少个 \(0\)，如果有偶数个，那么先手可以赢，如果有奇数个，那么后手可以赢。
code
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN = 2e5 + 10, MaxM = 22;
int cnt[MaxM], n, t;
int main() {
for (cin >> t; t; t--) {
fill(cnt, cnt + 21 + 1, 0);
cin >> n;
for (int i = 1, x; i <= n; i++) {
cin >> x;
for (int j = 21; j >= 0; j--) {
cnt[j] += bool(x & (1 << j));
}
}
int flag = 0;
for (int i = 21; i >= 0; i--) {
if (cnt[i] % 2 == 0) {
continue;
}
flag = (cnt[i] == 1 || (n - cnt[i]) % 2 == 0) ? 1 : -1;
break;
}
cout << flag << endl;
}
return 0;
}
P8756 [蓝桥杯 2021 省 AB2] 国际象棋
思路
状压 \(dp\)，由于当前行只与上两行有关系，所以只要记录上一行即可，直接 \(dp_{ijkl}\)（不是我偷懒，我是真的不知道还能怎么分析了，直接\(DFS\) 算算了），转移要注意不能被吃到。
code
#include <iostream>
using namespace std;
const int MaxN = 110, mod = 1e9 + 7;
long long dp[MaxN][21][1 << 6][1 << 6], n, m, k, ans;
int G(int x) {
int cnt = 0;
while (x) {
cnt += x % 2, x /= 2;
}
return cnt;
}
int main() {
cin >> n >> m >> k;
dp[0][0][0][0] = 1;
for (int i = 1; i <= m; i++) {
for (int j = 0; j <= k; j++) {
for (int k = 0; k < (1 << n); k++) {
for (int l = 0; l < (1 << n); l++) {
for (int p = 0; p < (1 << n); p++) {
if ((k & (l >> 2)) || (k & (l << 2)) || (k & (p >> 1)) || (k & (p << 1))) {
} else if (j >= G(k)) {
dp[i][j][k][l] = (dp[i][j][k][l] + dp[i - 1][j - G(k)][l][p]) % mod;
}
}
}
}
}
}
for (int i = 0; i < (1 << n); i++) {
for (int j = 0; j < (1 << n); j++) {
ans = (ans + dp[m][k][i][j]) % mod;
}
}
cout << ans << endl;
return 0;
}