題目描述

Bessie結束了國外長途旅游回來。為了迎接她的歸來，Farmer John準備在牧場給她掛起一個"Welcome Home"的橫幅。橫幅會掛在兩個柱子間的長度介于L1..L2的金屬絲上。(1 <= L1 <= L2; L1 <= L2 <= 1,500)。牧場是一個W×H 的矩陣 (1 <= W <= 1,000; 1 <= H <= 1,000)并且FJ在每個坐標點上都樹立起了柱子，在這 (W + 1) * (H + 1)個柱子上，FJ要選兩個連上金屬絲以掛上橫幅。 FJ不希望在橫幅之間有任何雜物，就是說在這條金屬絲下面沒有別的柱子。 FJ需要你編程幫他算出有多少種掛橫幅的可能。但是這個數據很大，也許32位整數都放不下。例如如下的牧場地圖： W = 2 H = 1 *** *** 而橫幅長度為2和3之間。這個牧場共有 (2+1) * (1+1) = 6個點以及有(6 take 5) = (6*5)/(2*1) = 15 種配對方法

(0,0)-(0,1) (0,0)-(2,1) (0,1)-(2,1) (1,1)-(2,0)

(0,0)-(1,0) (0,1)-(1,0) (1,0)-(1,1) (1,1)-(2,1)

(0,0)-(1,1) (0,1)-(1,1) (1,0)-(2,0) (2,0)-(2,1)

(0,0)-(2,0) (0,1)-(2,0) (1,0)-(2,1)

在這之中，只有四種是可以配對的

始位 末位 長度 始位 末位 長度(0,0)-(2,0) 2.00 (0,1)-(2,0) 2.24(0,0)-(2,1) 2.24 (0,1)-(2,1) 2.00

但在這四種之中，(0,0)-(2,0)和(0,1)-(2,1)都不符合“沒有雜物”的要求，所以這個樣例中只有2種結果。

輸入

一行，4個整數W, H, L1和 L2

輸出

一行，表示可能的方案數。

樣例輸入

2 1 2 3

樣例輸出

2

分析?
找規律+數學：?
①我們手動推理發現，如果矩陣的長寬互質，那么它們的任意一條對角線都不經過其內的任意一個整數坐標點，即不經過柱子，所以我們可以枚舉枚舉矩形長i寬j的可能性，然后判斷它們的gcd是否為1。?
如果為1則?
長寬互質，所以其對角線是不經過整數坐標點的，所以可能性+1，?
然后乘上(w-i+1)*(h-j+1)，因為在矩形中有這么多個這種小矩形，就有這么多的可能性?
還要乘上2，因為矩形的對角線有2條

②因為上面僅僅只是處理了對角線，但是，我們要考慮！?
l1=1的情況，因為任意2個柱子間距為1，這，也是一種情況！！！！?
因此這時候我們還要給答案加上h*(w+1)+w*(h+1)，因為有這么多個間距

時間復雜度：O（(w+1)*(h+1)）

程序：

var i,j,w,h,e:longint; l1,l2,k:real; ans:int64;function work(x,y:longint):longint; beginif x=0 then exit(y) else exit(work(y mod x,x)); end;beginreadln(w,h,l1,l2);ans:=0;for i:=1 to w+1 dofor j:=1 to h+1 dobeginif i<=j then e:=work(i,j) else e:=work(j,i);if e=1 thenbegink:=sqrt(sqr(i)+sqr(j));if (k>=l1) and (k<=l2) then ans:=ans+(w-i+1)*(h-j+1)*2;end;end;if l1=1 then ans:=ans+h*(w+1)+w*(h+1);write(ans); end.

轉載于:https://www.cnblogs.com/YYC-0304/p/9500077.html

總結

以上是生活随笔為你收集整理的JZOJ__Day 10:【普及模拟】【USACO】横幅的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。