【题目】在CCNU寻求ACM是否搞错了什么？

“菜鸟杯”华中师范大学程序设计新生赛

G - 在CCNU寻求ACM是否搞错了什么？

https://ac.nowcoder.com/acm/contest/26134/G

64bit IO Format: %lld

题目描述：

[1] 相邻： 指上下左右相邻，具体来说，对于两个坐标为[x, y], [i, j]的格子，两个格子相邻指的是 $(x=i \cap y=j\pm 1)\cup(x=i \pm 1 \cap y=j)$。

[2] 摆放方案：指对于一个从1到 $n*m$ 的排列 $p_1, p_2...p_{n*m-1},p_{n*m}$，把每个格子依次放上第$p_i$个水晶。

输入描述：

$2 \leq n,m \leq 10^4$

$1 \leq T \leq 10^6$

2
2 2
2 3

14
36

我的笔记：

分析

ans = 4 * (max + (max - beside4 + 1)) * beside4 / 2 +
3 * ((max - beside4) + (max - beside4 - beside3 + 1)) * beside3 / 2 +
2 * ((max - beside4 - beside3) + (max - beside4 - beside3 - beside2 + 1)) * beside2 / 2;

代码

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
int T;
cin >> T;
while (T--)
{
int n, m;
scanf("%d%d", &n, &m);
long long max = m * n;
long long ans = 0;
int beside2, beside3, beside4;
if (n % 2 == 0 || m % 2 == 0)
{
beside4 = (n - 2) * (m - 2) / 2;
beside3 = n + m - 4;
beside2 = 2;
ans = 4 * (max + (max - beside4 + 1)) * beside4 / 2 +
3 * ((max - beside4) + (max - beside4 - beside3 + 1)) * beside3 / 2 +
2 * ((max - beside4 - beside3) + (max - beside4 - beside3 - beside2 + 1)) * beside2 / 2;
}
else if (n % 2 != 0 && m % 2 != 0)
{
long long anstmp1 = 0, anstmp2 = 0;
beside4 = (n - 2) * (m - 2) / 2 + 1;
beside3 = 2 * (n / 2 + m / 2) - 4;
beside2 = 4;
anstmp1 = 4 * (max + (max - beside4 + 1)) * beside4 / 2 +
3 * ((max - beside4) + (max - beside4 - beside3 + 1)) * beside3 / 2 +
2 * ((max - beside4 - beside3) + (max - beside4 - beside3 - beside2 + 1)) * beside2 / 2;
beside4 = (n - 2) * (m - 2) / 2;
beside3 = 2 * (n / 2 + m / 2);
beside2 = 0;
anstmp2 = 4 * (max + (max - beside4 + 1)) * beside4 / 2 +
3 * ((max - beside4) + (max - beside4 - beside3 + 1)) * beside3 / 2 +
2 * ((max - beside4 - beside3) + (max - beside4 - beside3 - beside2 + 1)) * beside2 / 2;
ans = anstmp1 > anstmp2 ? anstmp1 : anstmp2;
}
printf("%lld\n", ans);
}
return 0;
}