T1 游戏
题目描述
Alice和Bob在玩一个游戏，游戏是在一个N*N的矩阵上进行的，每个格子上都有一个正整数。当轮到Alice/Bob时，他/她可以选择最后一列或最后一行，并将其删除，但必须保证选择的这一行或这一列所有数的和为偶数。如果他/她不能删除最后一行或最后一列，那么他/她就输了。两人都用最优策略来玩游戏，Alice先手，问Alice是否可以必胜？
分析
这个说辞...一看就知道是博弈论
众所周知，博弈论有两个重要结论：
1.一个状态是必败状态当且仅当它任意后继都是必胜状态
2.一个状态是必胜状态当且仅当它存在后继是必败状态
于是设 $f[i][j]$ 为矩阵为 $i$ 行 $j$ 列时该回合操作方的状态（$1$ 为必胜，$0$ 为必败），显然 $f[1][1]=1$
同时需要将 $f[1][i]$ 和 $f[i][1]$ 初始化，还要记录所有横轴和纵轴的前缀和
然后分别讨论删除最后一行和最后一列时的后继状态，若该行或该列无法被删除，则该后继视为必胜
考场上写这题的时候已经不早了，感觉有点慌，幸好最后过了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
#define N 1005
int T, n;
int g[N][N], f[N][N], p1[N][N], p2[N][N];
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
scanf("%d", &g[i][j]);
p1[i][j] = p1[i][j - 1] + g[i][j];
p2[i][j] = p2[i - 1][j] + g[i][j];
}
f[1][1] = 1;
for (int i = 2; i <= n; i++) {
int t1, t2;
if (p1[1][i] % 2) t1 = 1;
else t1 = 0;
if (p2[1][i] % 2) t2 = 1;
else if (f[1][i - 1]) t2 = 1;
else t2 = 0;
if (t1 && t2) f[1][i] = 0;
else f[1][i] = 1;
}
for (int i = 2; i <= n; i++) {
int t1, t2;
if (p2[i][1] % 2) t2 = 1;
else t2 = 0;
if (p2[i][1] % 2) t1 = 1;
else if (f[i - 1][1]) t1 = 1;
else t1 = 0;
if (t1 && t2) f[1][i] = 0;
else f[i][1] = 1;
}
for (int i = 2; i <= n; i++)
for (int j = 2; j <= n; j++) {
int t1, t2;
if (p1[i][j] % 2) t1 = 1;
else if (f[i - 1][j]) t1 = 1;
else t1 = 0;
if (p2[i][j] % 2) t2 = 1;
else if (f[i][j - 1]) t2 = 1;
else t2 = 0;
if (t1 && t2) f[i][j] = 0;
else f[i][j] = 1;
}
if (f[n][n]) printf("W\n");
else printf("L\n");
}
return 0;
}
T2 六边形
题目描述
棋盘是由许多个六边形构成的，共有5种不同的六边形编号为1到5，棋盘的生成规则如下：
1.从中心的一个六边形开始，逆时针向外生成一个个六边形。
2.对于刚生成的一个六边形，我们要确定它的种类，它的种类必须满足与已生成的相邻的六边形不同。
3.如果有多个种类可以选，我们选择出现次数最少的种类。
4.情况3下还有多个种类可以选，我们选择数字编号最小的。
现在要你求第N个生成的六边形的编号？
前14个六边形生成图如下：
原文：https://www.cnblogs.com/Pedesis/p/11284483.html