UVA11538 Chess Queen

cxy-xlf-1003 / 2023-08-05 / 原文

UVA11538 Chess Queen

题目传送门
挺有意思的一个题目。

题目大意

给定一个棋盘，在棋盘上放两个皇后（一白一黑），求使得两个皇后相互攻击（在一行、一列或对角线）的方案数。

分析

我们首先可以想到的是一个皇后在一个任意的位置，另一个皇后可以放的在同一行或在同一列的方案数有

\[m-1+n-1 \]

棋盘上一共有 \(m \times n\) 个格子，所以可放在同行或同列相互攻击的方案是 ans=(m-1+n-1)*m*n;

同行同列的方案数已经算好了，现在我们计算对角线上的方案数。因为左斜线上和右斜线上的方案是一样多的，所以我们只要求出左斜线即可知道右斜线的方案数。

首先我们要考虑到的是：斜线的最大值，是 \(\min(m,n)\)。那我们就把 x=max(m,n) 看作行，y=min(m,n) 看作列，所以我们的 \(2\) 至 \(y-1\) 行每行的格子数就是行号数，大于等于 \(y\) 的行号数都只有 \(y\) 个格子，所以等于 \(y\) 个格子的左斜线有

\[y-x+1 \]

每一条上可以任选两个点放置皇后，即

for(long long i=2;i<m;i++) cnt+=(long long)i*(i-1)*2;
cnt+=(long long)(n-m+1)*m*(m-1));

即总方案数：\(ans+2 \times cnt\)。

AC Code

#include <bits/stdc++.h>
using namespace std;
#define LL long long

int main()
{
    LL m,n;
    while(scanf("%lld%lld",&m,&n)==2&&(m+n))
    {
        if(m>n) swap(m,n);  // 确保m小于等于n，便于后续计算
        LL ans=0,cnt=0;
        ans+=n*m*(n-1+m-1); // 计算第一部分的结果
        for(LL i=2;i<m;i++)    cnt+=(LL)i*(i-1)*2; // 计算第二部分的结果
        cnt+=(LL)(n-m+1)*m*(m-1); // 计算第三部分的结果
        ans+=cnt*2; // 计算总结果
        printf("%lld\n",ans);
    }
    return 0;
}