每个点都可能会与周围距离为 \(3\) 的点配对，从而放下棋子。
但当你在另一个位置放棋子时，若其周围距离为 \(3\) 的点与之前放棋子的点冲突，那该如何解决？
问题突然变成二分图最大匹配，我们把方格看成点构成一张图跑二分图匹配即可。
BUTT！
若 \(n\) ， \(m\) 小于 \(100\) 还好说，此题的 \(n\) ， \(m\) 是爆炸级别的，根本没法跑复杂度平方级别的算法，那就用刚刚写的程序打表找找规律吧。
这里又有一个很神奇的地方，当 \(n\) 和 \(m\) 为奇数的时候，输出 $ n\times m-1$；
当其中一个为偶数的时候，输出 \(n\times m\) 。
BUTT！
当 \(n\) 和 \(m\) 小于 \(20\) 的时候，这种情况就不在符合。
所以对 \(n\) 和 \(m\) 小于 \(20\) 的情况，跑二分图匹配，其余的按照规律输出即可。（还不如好好找规律）
补充: 对与 \(n=1\) 或者 \(m=1\) 的情况要特殊处理下，明显 \(1\times 6\) 的矩阵可以摆满棋子，所以答案为 $6\times \lfloor\frac{m}{6}\rfloor+2\times max{ (m\bmod\ 6)- 3,0} $。
\(\text{code :}\)
#include "cstdio"
#include "cstring"
#include "queue"
#include "map"
#define pii std::pair<int, int>
#define oo 0x3f3f3f3f
#define M 2000
const int dr[] = {3, 2, 1, 0, -3, -2, -1, 0, 2, 1, 0, -3, -2, -1};
const int dc[] = {0, 1, 2, 3, 0, 1, 2, 3, -1, -2, -3, 0, -1, -2};
long long n, m;
int cnt, g[M][M];
std::map<pii, int> MAP;
inline int FIND(pii p)
{
if (MAP.count(p))
return MAP[p];
return MAP[p] = ++cnt;
}
int sx, sy;
inline void build()
{
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
{
for (int k = 0; k < 14; ++k)
{
int ni = i + dr[k], nj = j + dc[k];
if (ni < 0 || ni >= n || nj < 0 || nj >= m)
continue;
g[FIND(pii(i, j))][FIND(pii(ni, nj))] = 1;
sy++;
}
}
}
int zx[M], zy[M];
int dx[M], dy[M], dis;
bool vis[M];
inline bool bfs()
{
std::queue<int> Q;
dis = oo;
memset(dx, -1, sizeof dx);
memset(dy, -1, sizeof dy);
for (int i = 1; i <= sx; i++)
if (zx[i] == -1)
Q.push(i), dx[i] = 0;
while (!Q.empty())
{
int u = Q.front();
Q.pop();
if (dx[u] > dis)
break;
for (int v = 1; v <= sy; v++)
if (g[u][v] && dy[v] == -1)
{
dy[v] = dx[u] + 1;
if (zy[v] == -1)
dis = dy[v];
else
{
dx[zy[v]] = dy[v] + 1;
Q.push(zy[v]);
}
}
}
return dis != oo;
}
inline bool dfs(int u)
{
for (int v = 1; v <= sy; v++)
if (!vis[v] && g[u][v] && dy[v] == dx[u] + 1)
{
vis[v] = 1;
if (zy[v] != -1 && dy[v] == dis)
continue;
if (zy[v] == -1 || dfs(zy[v]))
{
zy[v] = u;
zx[u] = v;
return 1;
}
}
return 0;
}
inline int work()
{
int res = 0;
memset(zx, -1, sizeof zx);
memset(zy, -1, sizeof zy);
while (bfs())
{
memset(vis, 0, sizeof vis);
for (int i = 1; i <= sx; i++)
if (zx[i] == -1 && dfs(i))
res++;
}
return res;
}
int main()
{
scanf("%lld%lld", &n, &m);
if (n > m)
std::swap(n, m);
if (n == 1)
printf("%lld", 6 * (m / 6) + 2 * std::max(m % 6 - 3, 1ll * 0));
else if (n <= 20 && m <= 20)
{
sx = n * m;
sy = 0;
build();
printf("%d", work());
}
else
{
if (n % 2 == 0 && m % 2 == 0)
printf("%lld", n * m);
else if (n % 2 == 0 && m % 2 || n % 2 && m % 2 == 0)
printf("%lld", n * m);
else
printf("%lld", n * m - 1);
}
return 0;
}
题解 CF1034B 【Little C Loves 3 II】
原文：https://www.cnblogs.com/nakiri-ayame-suki/p/13905093.html