uva 11538 Chess Queen

点击打开链接

题意：给定一个n*m的矩阵，问有多少种方法放置两个相互攻击的皇后？规定在同一行同一列和同对角线的能够相互攻击

思路：

1 先考虑同一行的情况，n行就有n种情况，每一行有m*（m-1）种，总的是n*m*(m-1);

2 考虑同一列的情况，m列就是m种情况，每一列有n*(n-1)种，总的是m*n*(n-1);

3 最后考虑同对角线的情况，因为n > m和 n <= m的情况是不一样的，我们先假设 n <= m

   通过画图我们知道，所有的/对角线，从左到右的长度分别为1 2 3 ... n-1 n n ...n n(有m-n+1个) n-1 ... 1

   那么总的就是1*(1-1)+2*(2-1)+...(n-1)*(n-1-1)+(m-n-1)*n*(n-1)+(n-1)*(n-1-1)+...+2*(2-1)+1*(1-1)

   因为还有\的情况，因为总的还要乘2

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long int64;

int64 n , m;

int64 solve(){
    int64 ans = 0; 
    if(n > m)
        swap(n , m);
    // same row
    ans += n*m*(m-1); 
    // same col
    ans += m*n*(n-1);
    // same duijiao
    ans += 2*(2*((n-1)*n*(2*n-1)/6-n*(n-1)/2)+(m-n+1)*n*(n-1));
    return ans;
}

int main(){
    while(cin>>n>>m && n+m){
        cout<<solve()<<endl;
    }
    return 0;
}