網頁

2014年2月17日 星期一

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)]
  • 把以上三式加起來即是答案