题解 「SiR-1」Checkmate

· · 题解

前言：这题本来是 Div.2 A，结果因为你谷的通过率要求变成了 Div.2 B。个人认为这题放在这个位置难度过低了。赛后看看通过率。

Subtask 1

我会爆搜！

Subtask 2

我会状压！

Subtask 3

爆搜小数据，或者手玩，或者 DP，可以发现答案为 m-1。

Subtask 4

考虑搜出答案数列为 \{0,4,12,24,40,\cdots\}，注意到相邻两项的差为等差数列 \{4,8,12,16,\cdots\}，可以用等差数列求和，得到答案为 2n^2-2n。

Subtask 5

在刚刚的爆搜过程中，你可能已经发现，不管放置棋子的顺序如何，最终获得的分数都一样。这是为什么呢？

考虑一对相邻的格子，我们称它们为格子 i 和格子 j。我们发现，如果格子 i 放置棋子时格子 j 还没有棋子，那么格子 i 这次操作的得分就会多 1，反之亦然。我们又发现如果 i 比 j 先放置，j 就比 i 后放置。（这不是废话吗）

因此，一对相邻的格子一定会使最终答案恰好增加 1。

因此，最终答案就是相邻格子的对数。我们考虑分开统计横着相邻和竖着相邻的格子，不难得到答案为 m(n-1)+n(m-1)=2nm-n-m。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int T;
ll n, m;
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%lld%lld", &n, &m);
        printf("%lld\n", 2 * n * m - n - m);
    }
    return 0;
}