UVa 11538 Chess Queen

題意：
　　兩個Chess Queen在同一欄，或同一行，或同一對角線上表示為attacking position，給定a*b棋盤，問為attacking position的情況有幾種?

想法：
　　分成位在同一欄(直)，同一行(橫)，和同一對角線三種情況分開算，假設a為寬(橫的)，b為長(直的)，a必須<=b：

• 兩個棋子位在同一直線共有 a*C(b,2)*2!
• 位在同一橫線共有 b*C(a,2)*2!
• 位在對角線上可以自己畫圖觀察得到，對角線最長為a，且最長的共有(b-a+1)條，其他比a還短的對角線(長度2~a-1)都各有2條，記得對角線有左斜和右斜兩個方向。
  ....
  ....   4x5的棋盤 對角線最長為4，共2條
  ....
  ....
  ....
  因此可得 2(左斜右斜)*[(b-a+1)*C(a,2) + 2*(C(2,2)+C(3,2)+C(4,2)+...+C(a-1,2))]
  = 2*[(b-a+1)*C(a,2) + 2*C(a,3)]
• 把以上三式加起來即是答案

	#include <cstdio>
	#include <iostream>
	using namespace std;
	int main()
	{
	long long a,b;
	while (scanf("%lld%lld",&a,&b)){
	if (!a && !b) break;
	if (a > b) swap(a,b); // a:寬 b:長
	long long ans = a*b*(a-1) + a*b*(b-1); //寬 + 長
	ans += 4* (2*(a*(a-1)*(a-2)/6) + (b-a+1)*a*(a-1)/2); // 對角線
	printf("%lld\n",ans);
	}
	return 0;
	}

view raw [UVa] 11538 Chess Queen..cpp hosted with ❤ by GitHub