MYF

UVa 11538 Chess Queen

Posted on | In | | Visitors

题目链接

UVa 11538

解题方法：推公式

题目分析

题目大意

    有n行m列的棋盘，上面有黑白两个皇后，如果两个皇后在同一对角线/同一行/同一列，那么就称这两个皇后in attacking position，问有多少种attacking position的组合。

解析

先把棋盘转一下，使行数大于等于列的数量(m≤n)。

对于每一个格子，横竖各有m-1和n-1种组合，所以上下左右方向共有mn(m+n-2)种组合。

然后就是对角线了，如图所示。

蓝线圈出来的部分共有m+n-1条，其中分为共n-m+1条长度为m的对角线，长度为1～m-1的各两条。对于任何一条长度为l的对角线，共有l(l-1)个组合，由此可推得对角线部分的公式为：

根据平方和公式化简，并且加上水平竖直方向的组合得出结果为:mn(m+n-2)+2m(m-1)(2m-1)/3-2m(m-1)+2m(m-1)(n-m+1)

代码

1
2
3
4
5
6
7
8
9
10
11
12
//Memory 0KB Times 6ms
#include <cstdio>
#include <algorithm>
int main(){
    long long n,m;
    while (scanf("%lld %lld",&m,&n),n&&m) {
        long long ans=0;
        if (m>n) swap(m, n);
        ans=n*m*(n+m-2)+2*((m-1)*(2*m-1)*m/3-m*(m-1)+(n-m+1)*m*(m-1));
        printf("%lld\n",ans);
    }
}