福州大学第十七届程序设计大赛 1003 棋盘 题解

题目大意

给你$n\times m $的棋盘，现在任意挖走两个位置，剩下的需要你用$1\times 2$或者$2\times 1$的方块填满，求满足这个条件的挖法有多少种。

解题思路

我们假设是这样一个棋盘。

总共是有$n\times m$个格子。

假如$n\times m$为奇数，则所有情况都不可能实现，因为你每次都会需要填两个，而剩下的是奇数个。

如果$n\times m$为偶数，则答案为黑块选择情况乘上白块选择情况，即$\Large \frac{(n\times m)}{2}\times \frac {(n\times m)}{2}$。

因为黑块和白块的数量是相同的，所以只能选择一个黑块一个白块。

我们把这两个任意选择的黑块和白块当做一个矩形的对角。

很显然，除了这个矩形之外的地方是可以填满的。

那么对这个矩形进行分析，易知，这个矩形的边长一定是一个奇数，一个偶数，减去两个之后，会变成一个偶数，一个奇数。

可以将偶数的边填满，这样中间就只剩下一个边长减了2的矩形了，很明显，这个矩形是一定能被填满的。

所以答案为$\Large \frac{(n\times m)}{2}\times \frac {(n\times m)}{2}$。

需要注意只有一行（列）的情况，枚举所有的黑块，答案为黑块右边的白块数量。

（福州大学的这个OJ是真的菜，跑的时间巨长，且不支持万能头，连unordered_map都不能用。。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int N = 30;
char Map[N][N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m;
	while (cin >> n >> m) {
		if ((n * m) & 1) {
			cout << 0 << endl;
			continue;
		}
		if (n == 1 || m == 1) {
			int t = max(n, m);
			int ans = 0;
			for (int i = 1; i <= t; i+=2)	ans += (t - i + 1)/2;
			cout << ans << endl;
		}
		else {
			cout << (n * m / 2) * (n * m / 2) << endl;
		}
	}
	return 0;
}