自动搬运

查看原文

来自洛谷，原作者为

	printfmingren **

搬运于2025-08-24 22:47:37，当前版本为作者最后更新于2023-05-23 14:11:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题外话：本体题目出自番剧《NO GAME NO LIFE》且题目背景中「来吧，游戏开始了。」是第一季中男主“空”的口头禅。（强烈推荐观看《NO GAME NO LIFE ZERO》）

言归正传：

题目解读：

在 $n$ 行 $m$ 列的棋盘中放置一颗棋子，获得上下左右的未被放置棋子的格子数的值。

题目分析：

由题目可以得到在完全空白的棋盘中，放置在角能得到 $2$ 分，放置在棱能得到 $3$ 分，放置在中心块能得到 $4$ 分。（在 $1$ 行或 $1$ 列时，角能得 $1$ 分，棱能得 $2$ 分，无中心块）
$2 × 1$ 的方块中，放置在左方块（或右方块），能得到 $1$ 分，接下来放置另一方块会不得分。拓展到 $3 × 1$ 的方块中，无论先放置中间的块，能得到 $2$ 分，还是放置左右两块能得到 $1$ 分，亦或是从左到右（从右到左）依次排列都是 $2$ 分。
如果我们不考虑空白位置（即任意位置都能得分），我们会发现刚好是上述分值的 $2$ 倍。

准备午休时想到了另一种理性的证明（应该能理解的）

首先我们先思考放置一枚棋子能带来什么影响。(可以先思考一下再接着看)
我们在理想的情况下得到的分数是角 $×2+$ 棱 $×3+$ 中心块 $×4$ ，也就是每个块都拿到了能拿到的最大分值。（但是毕竟我们应该考虑影响）
于是乎在考虑影响的情况下，我们的每一步行动都将获得一个分值，但是总分数（就是理想情况下的分数）将减去这个分值。因此，我们在考虑影响的情况下的能获得的分值是(角的值 $+$ 棱的值 $+$ 中心块的值) $/2$

如图所示：

分类讨论情况如下：（也可以合并,因为考场没有想到第一个式子包含了第二个式子）

$n≥2$ 且 $m≥2$ 时

$val=$ ( $angel×2+edge×3+center×4$ ) $/2$

$n<2$ 且 $m<2$ (就是 $1$ 行或者 $1$ 列的情况)

$val=n+m- 2$ （每个块能得 $2$ 分，左右或上下块与中间的块相比各少 $1$ 分）
由于 $n=1$ 或 $m=1$ ,可得 $val=n-1$ 或 $val=m-1$ (合并的时候能用到)
从某种意义上来讲就是影响互相抵消

以上是考场时写出来的，以下是考后的优化（算是吧）

$val=$ ( $angel×2+edge×3+center×4$ ) $/ 2$
根据上式并列得出完整式子，式子得出过程如下：

//sum==val,a==angel,b==edge,c==center
a=4;
b=2*n+2*m-2*a;
c=n*m-a-b;
sum=(a*2+b*3+c*4)/2;	//将此式化简可得:sum(val)=2*n*m-n-m;

将 $n=1$ 或 $m=1$ 带入得此式为： $sum=m-1$ 或 $sum=n-1$
由此可知 $val=$ ( $angel×2+edge×3+center×4$ ) $/2$ 包含 $val=n+m-2$

AC代码如下

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	ll T;
	scanf("%lld",&T);
	for(ll i=1;i<=T;++i)
	{
		ll n,m,a,b,c,sum;
		scanf("%lld%lld",&n,&m);
		if(n>=2&&m>=2)
		{
			a=4;
			b=2*n+2*m-2*a;
			c=n*m-a-b;
			sum=(a*2+b*3+c*4)/2;
		}
		else
			sum=n+m-2;
		printf("%lld\n",sum);
	}
	return 0;
}

于是乎我推荐大家试试[THUPC 2023 初赛] 大富翁
感觉两题都有相似之处。
本蒟蒻的第一篇题解（问题已改正），求管理员通过，还请各位大佬指出错误，一同进步。（点个赞再走吧，QAQ）