【基本计数方法---加法原理和乘法原理】UVa 11538 - Chess Queen

题目链接

题意:给出m行n列的棋盘,当两皇后在同行同列或同对角线上时可以互相攻击,问共有多少种攻击方式。

分析:首先可以利用加法原理分情况讨论:①两皇后在同一行;②两皇后在同一列;③两皇后在同一对角线( / 或 \ );

   其次利用乘法原理分别讨论:

   ①同一行时(A),先选某一行某一列放置其中一个皇后,共m*n种情况;其次在选出的这一行里的其他n-1个位置中选一个放另一个皇后;共m*n*(n-1)种情况;

   ②同一列时(B)情况相同,为n*m*(m-1)种情况;

   ③同一对角线(D)上时,先讨论 / 方向对角线:

    为方便假设m>=n,则从左到右每条对角线长度依次为:

      1,2,3,... ...,n-1,n,n,... ...,n,n,n-1,... ... 3,2,1

    其中中间的n有(m-n+1)个;

    则共有: (1*0 + 2*1 + ... + (n-1)*(n-2)) * 2 + (m-n+1)*n*(n-1) 种情况;

    其中∑[1,n-1] (i*(i-1)) = ∑[1,n-1] (i*i - i) = ∑[1,n-1] (i*i) - ∑[1,n-1] (i) ;

    又∑[1,n-1] (i*i) = n*(n-1)*(2n-1) / 6; ∑(1,n-1) (i) = n*(n-1) / 2;

    则原式可化简为 n*(n-1)*(2n-4)/3 + (m-n+1)*n*(n-1);

      再加上 \ 对角线的情况,与上述相同,则D = 2*(n*(n-1)*(2n-4)/3 + (m-n+1)*n*(n-1));

    

    答案为A+B+D;

代码如下

 #include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std; typedef unsigned long long ULL; int main()
{
ULL m, n;
while(cin >> m >> n)
{
if(!m && !n) break;
if(m<n) swap(m, n);
ULL A = m*n*(n-), B = n*m*(m-);
ULL D = *(n*(n-)*(*n-)/ + (m-n+)*n*(n-));
cout << A+B+D << endl;
}
return ;
}

  

      

上一篇:C# 抓取网页的img src带参数的图片链接,并下载


下一篇:[Entity Framework]获取部分字段的查询