2.8　數學概念與方法

本節選解習題來源于《算法競賽入門經典（第2版）》一書的第10章。

習題10-1　砌磚（Add Bricks in the Wall，UVa11040）

對45塊石頭按照如圖2.60所示的方式排列，每塊石頭上有一個整數。

除了最后一行外，每個石頭上的整數等于支撐它的兩個石頭上的整數之和。目前只有奇數行的左數奇數個位置上的數已知，你的任務是求出其余所有整數。輸入保證有唯一解。

【分析】

把所有石頭看作一個二維數組B［9］［9］。從上到下依次是0～8行。則對于i＝0，2，4，6，8這樣的偶數行，已知數字就是B［0］［0］、B［2］［0］、B［2］［4］這樣的偶數列。我們觀察第8行的左數第1個空格，假設里面是x，則其上方的兩個石頭分別為2＋x、x＋1，繼續往上就有2＋x＋x＋1＝3，這樣就可以解出x。

推廣開來，對于奇數列來說，B_i，j滿足：

所以有：

從下到上把所有的偶數行奇數列的數字計算出來之后，奇數行的數字按照題目所述規則也自然可以計算出來。

習題10-2　勤勞的蜜蜂（Bee Breeding, ACM/ICPC World Finals 1999, UVa808）

如圖2.61所示，輸入兩個格子的編號a和b（a,b≤10000），求最短距離。例如，19和30的距離為5（一條最短路是19-7-6-5-15-30）。

【分析】

在一個平面上任選兩個向量，就可以建立一個坐標體系（本題中已經不是笛卡爾坐標系）表示平面上所有的點。如圖2.62所示，使用塊1→7的方向作為正X軸，1→6的方向作為正Y軸。XY軸把平面分成4個象限，同時用6個方向向量表示6個方向：{-1,0}, {-1,1}, {0,1}, {1,0}, {1,-1}, {0,-1}。

首先確定塊1和2的坐標(0,0)和(1,-1)，觀察后可以得出，點的坐標遵循如下規律。

第1圈：

2→3, 3→4, 4→5, 5→6,分別使用向量{-1,0}, {-1,1}, {0,1}, {1,0},每次生成1個點。

6→8，使用向量{1,-1}，生成2個點。

8→9，使用向量{0,-1}，生成1個點。

第2圈：

9→11, 11→13, 13→15, 15→17,分別使用向量{-1,0}, {-1,1}, {0,1}, {1,0},每次生成2個點。

17→20，使用向量{1,-1}，生成3個點。

20→22，使用向量{0,-1}，生成2個點。

……

依次類推，就可以生成所有點的坐標。對于任意的兩個點(x₁, y₁), (x₂, y₂)，記x=x₁–x₂, y=y₁–y₂，則這個兩點之間的距離就是原點到(x,y)的距離。

觀察之后不難發現：第1、3象限的點(x, y)到原點的距離為|x|+|y|；第2、4象限的點(x, y)到原點的距離為max{|x|, |y|}，問題得解。完整程序（C++11）如下：

本題代碼參考了http://www.cnblogs.com/AOQNRMGYXLMV/p/4202527.html。

習題10-4　素數間隔（Prime Gap，ACM/ICPC Japan 2007，UVa1644）

輸入一個整數n，求它后一個素數和前一個素數的差值。輸入是素數時輸出0。n不超過1299709（第100000個素數）。例如n＝27時輸出29-23＝6。

【分析】

首先篩選出符合條件的所有素數，存在一個vector＜int＞ primes中。對于n來說，令pl＝lower_bound（primes．begin（），primes．end（），n）。pl就指向第一個大于等于n的素數。如果*pl＝N，則說明N是素數；否則pl-1指向最后一個小于n的素數。

習題10-5　不同素數之和（Sum of Different Primes，ACM/ICPC Yokohama 2006，UVa1213）

選擇K個質數，使它們的和等于N。給出N和K（N≤1120，K≤14），問有多少種滿足條件的方案？例如n＝24，k＝2時有3種方案：5＋19＝7＋17＝11＋13＝24。注意，1不是素數，因此n＝k＝1時答案為0。

【分析】

首先需要篩選出所有可能符合條件的素數。之后這個問題就轉換成一個背包問題：

（1）d（i，n，k）表示從第i個及其以后的素數中選擇k個素數其和為n的方案個數。

（2）遞推公式就是：d（i，n，k）＝d（i＋1，n，k）＋d（i＋1，n-p_i，k-1），分別對應是否使用第i個素數p_i的策略。

邊界條件如下：

（1）n＜2或者p_i＞ n時，則d＝0。

（2）k＝1時，如果n是素數，則d＝1，否則d＝0。

習題10-6　連續素數之和（Sum of Consecutive Prime Numbers，ACM/ICPC Japan 2005，UVa1210）

輸入整數n（2≤n≤10000），有多少種方案可以把n寫成若干個連續素數之和？例如輸入41，有3種方案：2＋3＋5＋7＋11＋13、11＋13＋17和41。

【分析】

首先篩選出所有符合條件素數組成的序列P，然后求出P的前綴和序列PS，則所求結果就是符合條件“PS［i］＋n依然在PS中”的i的個數。

習題10-7　幾乎是素數（Almost Prime Numbers，UVa10539）

輸入兩個正整數L、U（L≤U≤10¹²），統計區間［L，U］的整數中有多少個數滿足：它本身不是素數，但只有一個素因子。例如4和27都滿足條件。

【分析】

這種數的唯一分解中一定只包含一個素數：p^k，其中k≥2，記n ，則顯然有p≤n。我們對素數篩法進行改造：每發現一個素數p就把所有的p^k（k≥2且p^k≤10¹²）記錄下來。最后按照從小到大的順序把這些數字記錄下來存放到一個vector中，記為aps。

對于區間［L，U］，第一個大于等于L的數就是lower_bound（aps．begin（），aps．end（）），第一個大于U的數就是upper_bound(aps.begin(), aps.end(), U)，則這兩個位置形成一個左閉右開區間，區間中數字的個數即是所求的結果。

和《算法競賽入門經典（第2版）》中的第10.1.2節類似，雖然內循環多了一個步驟，但這個步驟的循環次數的最大值為log_p(10¹²) ≈39，整體的算法復雜度為O(nlogn)。完整程序（C++11）如下：

習題10-8　完全P次方數（Perfect Pth Powers, UVa10622）

對于整數x，如果存在整數b使得x=b^p，我們說x是一個完全p次方數。輸入整數n，求出最大的整數p，使得n是完全p次方數。n的絕對值不小于2，且n在32位帶符號整數范圍內。例如n=17, p=1；n=1073741824, p=30；n=25, p=2。

【分析】

對于x是正數的情況，首先求出x的唯一分解p1^k1p2^k2、…、pn^kn。如果x是一個全p次方數，則所有的ki必然都是p的倍數，然后求所有ki的最大公約數就是p。

需要注意的是，如果x是負數，則p不能是偶數，所以求出所有ki的最大公約數之后，還要把其中的2除盡才得到p。

習題10-9　約數(Divisors, UVa294)

輸入兩個整數L和U（1≤L≤U≤10⁹，U-L≤10000），統計區間[L,U]的整數中哪一個的正約數最多。如果有多個，輸出最小值。

【分析】

對于整數K來說，假設其唯一分解為Π，則約數個數為Πk_i。可以用篩法先求出所有1～10⁵之間的素數，然后對L, U之間的整數進行唯一分解并且遍歷，即可求出結果。

習題10-10　統計有根樹（Count, Chengdu 2012, UVa1645）

輸入n（n≤1000），統計有多少個n結點的有根樹，使得每個深度中所有結點的兒子數相同。例如n=4有3棵，如圖2.63所示；n=7時有10棵。輸出數目除以10⁹+7的余數。

【分析】

令A[n]為所求的值，首先對于n=1,2來說A[n]=1。根據題意，一個結點的所有子樹結構都必須完全一致，則對n個結點數的子樹的結點個數j進行遍歷就可以得出： ，其中n-1能被j整除。注意要使用long long，防止數據溢出。

習題10-11　圈圖的匹配（Edge Case, ACM/ICPC NWERC 2012, UVa1646）

n（3≤n≤10000）個結點組成一個圈，求匹配（即沒有公共點的邊集）的個數。例如n=4時有7個（如圖2.64所示），n=100時有792070839848372253127個。

【分析】

首先看另一個問題，令F[n]為n個點組成線段鏈（不連成圈）中匹配的個數，則F[1]=1，F[2]=2，F[3]=3。考慮第n-1個線段是否在匹配中：如果在，則線段n-2不在，故有F[n-2]個匹配；否則有F[n-1]個匹配。由此可得F[n]=F[n-1]+F[n-2]，其實就是斐波那契數列。

回到本題，記所求匹配數為C[n]，根據點1和點2之間的線段是否在匹配中兩種情況，可得C[n]=F[n]+F[n-2]。遞推計算即可。注意，本題中的結果連long long（64位整數）也放不下，需使用大整數類。

習題10-12　漢堡（Burger, UVa557）

有n個牛肉堡和n個雞肉堡給2n個孩子吃。每個孩子在吃之前都要拋硬幣，正面吃牛肉煲，反面吃雞肉煲。如果剩下的所有漢堡都一樣，則不用拋硬幣。求最后兩個孩子吃到相同漢堡的概率。

【分析】

在正面或者背面的次數達到n次之后，就會出現符合題意的條件。但是情況太多，分類計數很麻煩，從另外一個角度來考慮，如果扔的前2n-2次，正面和反面出現的次數一樣多，則最后兩個孩子就會吃到不同的漢堡，記這種情況出現的概率為F_n，則所求結果為1-F_n，且有 。但是分式的上下兩項直接計算的話，必然會溢出。可從上述公式進一步得到F_n的遞推公式： ，直接遞推計算即可。

習題10-13　H(n)（H(n), UVa11526）

輸入n（在32位帶符號整數范圍內），計算下面C++函數的返回值：

例如n=5, 10時，答案分別為10和27。

【分析】

以n=10為例，i=1～10時累加的數字依次是10, 5, 3, 2, 2, 1, 1, 1, 1, 1。有5個1，2個2，1個3…。

由此考慮n/i=1時，i的范圍，顯然是n/2<i≤n/1，就有（n/1-n/2）個1。

n/i=2時，n/3<i≤n/2，就有（n/2-n/3）個2。

n/i=3時，n/4<i≤n/3，就有（n/3-n/4）個3。

…

n/i=k時，n/(k+1)<i≤n/k，有（n/(k+1)-n/k）個k。

需要注意的是，當開始，就按照正常的n/i計算。此時有 。算法的時間復雜度就是 。主循環邏輯如下：

注意n<0時循環不會運行，直接返回0。

習題10-15　零和一（Zeros and Ones, ACM/ICPC Dhaka 2004, UVa12063）

給出n, k（n≤64，k≤100），有多少個n位（無前導0）二進制數的1和0一樣多，且值為k的倍數？

【分析】

使用D(z,o, m)表示符合以下條件的數字的個數：

（1）以1開頭。

（2）1后面共有z個0，o個1。

（3）除k的余數為m。

則邊界條件為D(0,0,1)=1。每個二進制數后面每附加一個數字就有兩種轉移方式：

（1）D(z+1,o, (m*2)%k)+=D(z,o,m) //后面附加一個0

（2）D(z,o+1, (m*2+1)%k)+=D(z,o,m) //后面附加一個1

當n為奇數或k=0時無解。當n是偶數時，所求答案為：D(n/2, n/2-1,0)。

習題10-16　計算機變換（Computer Transformations, ACM/ICPC SEERC 2005, UVa1647）

初始串為一個1，每一步會將每個0改成10，每個1改成01，因此1會依次變成01, 1001, 01101001, …輸入n（n≤1000），統計n步之后得到的串中，“00”這樣的連續兩個0出現了多少次。

【分析】

我們分析所有可能的變換：

0→10

1→01

00→1010

10→0110

01→1001

11→0101

記F_n為第n步之后的00的個數，由前文所示，00是由01得到的，只需知道n-1步后01的個數E_n-1就得到F_n。再看前文推導，01由1和00得到，而第n步后1的個數是2^n-1,所以F_n=E_n-1=2^n-3+F_n-2，由此直接遞推即可。注意n≤1000，所以必須使用高精度整數運算。

習題10-17　H-半素數（Semi-prime H-numbers, UVa11105）

所有形如4n+1（n為非負整數）的數叫H數。我們定義1是唯一的單位H數，H素數是指本身不是1，且不能寫成兩個不是1的H數的乘積。H-半素數是指能寫成兩個H素數的乘積的H數（這兩個數可以相同，也可以不同）。例如25是H-半素數，但125不是。

輸入一個H數h（h≤1000001），輸出1到h之間有多少個H-半素數。

【分析】

參考素數篩法，用vis[i]記錄4i+1是否是H-素數。對于每個整數i（4i+1不是H-素數），令h_i=4*i+1，對于所有的j=(k*h_i)*h_i（k≥h_i），如果j%4=1，則說明j不是h素數，記vis[(j-1)/4]=1。否則記錄h_i為H-素數。篩法部分外層循環的次數為n，給定外層的循環變量，內層循環的次數小于。所以參考《算法競賽入門經典（第2版）》10.1.2節的時間復雜度分析可以得出，本題篩法部分的時間復雜度上限依然為O(nlogn)。

篩出所有的H素數之后，兩兩相乘將所有的乘積記錄下來，注意可能重復，然后用一個cnt[N]數組記錄H半素數的個數，其中cnt[i]表示1到4i+1之間所有的H半素數的個數，用O(n)的時間就可以將cnt處理完成。這樣問題的解就是 。完整程序如下：

習題10-18　一個研究課題（A Research Problem, UVa10837）

輸入正整數m（m≤10⁸），求最小的正整數n，使得φ(n)=m。輸入保證n小于200000000。

【分析】

記N=200000000。假設p₁, p₂…p_k為n的素因子，則，注意其中的m_i有可能為0。且如果，m_k一定為1。

首先篩選出所有小于的素數。然后對于n，遍歷所有不大于的素數p，如果φ(n)能被p-1整除，則p有可能是n的素因子，但出現在n的唯一分解中的次數未知。

然后對所有可能是n的素因子的p的次數進行回溯，每一步嘗試p的次數為0,1,2…，在φ(n)除去相應的p^m以及(p-1)。最后當所有可能素數決策完之后，φ(n)還可能沒除干凈，剩余一個x，此時就要判斷x+1是未被使用過的素數，如果是，則說明我們得到了一個合法的n。完整程序（C++11）如下：

習題10-19　蹦極（Bungee Jumping, UVa10868）

007為了擺脫敵人的追擊，逃到了一座橋前。橋上正好有一條蹦極繩，于是他打算把它拴到腿上，縱身跳下橋，落地后切斷繩子，繼續逃。已知繩子的正常長度為l，Bond的體重為w，橋的高度為s，你的任務是替007判斷能否用這種方法逃生。

當從橋上跳下后，繩子繃緊前Bond將做自由落體運動（重力按9.81w計），而繃緊后繩子會有向上的拉力，大小為k*Δl，其中Δl為繩子當前長度和正常長度之差。當且僅當Bond可以到達地面，且落地速度不超過10米/秒時，我們才認為他安全著落。

輸入每組數據包含4個非負整數k、l、s、w（s<200）。對于每組數據，如果可以安全著地，輸出“James Bond survices.”，如果到不了地面，輸出“Stuck in the air.”，如果到達地面速度太快，輸出“Killed by the impact.”。

【分析】

彈簧彈力和Δl的關系是一個三角形（如圖2.65所示），彈簧伸長的長度從0到Δl，對Bond做的功剛好是這個三角形的面積，即k*Δl²/2。

記v為觸底的速度，根據動能定理，合外力對物體所做的功，等于物體動能的變化，，因此有，其中L=s-l，s< l時L=0。針對v²的值分情況討論：

（1）如果v²≤0，說明卡在半空。

（2）如果v²≤100，說明安全著陸。

（3）否則說明觸底速度大于10，摔死了。

習題10-20　商業中心（Business Center, NEERC 2009, UVa1648）

商業中心是一幢無限高的大樓。在一樓有m座電梯，每座電梯只有兩個鍵：上、下。對于第i座電梯，每按一次“上”會往上走u_i層樓，每按一次“下”會往下走d_i層樓。你的任務是從一樓開始選一個電梯，恰好按n次按鈕，到達一個盡量低（一樓除外）的樓層。中途不能換乘電梯。1≤n≤1000000，1≤m≤2000，1≤u_i，d_i≤1000。

【分析】

不妨設對于每一個電梯，向上按了a次，向下按了b次，則a+b=n，則這個電梯最終停靠的層數就是m=a*u-b*d=a*(u+d)-n*d。本題就是要對每個電梯求m的最小正整數值。這個最小值，就是在a=n*d/(u+d)+1時取得，這里的除法就是整數除法。

最終的答案就是所有電梯的m的最小值。注意，此題需使用long long。

習題10-23　Hendrie序列（Hendrie Sequence, UVa10479）

Hendrie序列是一個自描述序列，定義如下：

（1）H(1)=0。

（2）如果把H中的每個整數x變成x個0后面跟著x+1，則得到的序列仍然是H（只是少了第一個元素）。

因此，H序列的前幾項為0,1,0,2,1,0,0,3,0,2,1,1,0,0,0,4,1,0,0,3,0,...。輸入正整數n（n<2⁶³），求H(n)。

【分析】

可以將H序列分塊，寫出H序列的前幾塊（第0塊特殊），如表2.2所示。

同時可以發現第m塊由以下序列組成：

1個第m-2塊

2個第m-3塊

...

m-1個第0塊

m

根據以上規律，對于一個輸入數字n，首先讓n=n-1（因為使用以0為起始下標統計更方便）。然后根據上述規律，找到n所在的那個塊m，并且找到n在m塊中的位置。如果正好是塊結尾，直接返回m即可。如果不是，找到n所屬的子塊以及在子塊中的位置，遞歸計算即可。完整程序如下：

習題10-28　數字串（Number String, ACM/ICPC Changchun 2011, UVa1650）

每個排列都可以算出一個特征，即從第二個數開始每個數和前面一個數相比是增加（I）還是減少（D）。例如{3,1,2,7,4,6,5}的特征是DIIDID。輸入一個長度為n-1（2≤n≤1001）的字符串（包含字符I、D和?），統計1～n有多少個排列的特征和它匹配（其中?表示I和D都符合）。輸出答案除以1000000007的余數。

【分析】

參考LCS等字符串相關的DP問題，不難想到把排列長度以及最后一位數字考慮進去作為狀態考慮：記dp(i,j)為由數字1～i組成的排列中，以j結尾的符合指定特征的排列個數。但是確定最后一位之后發現，前面的1～i-1位并不是1～i-1組成的排列，而是{1,2…j-1, j+1…i}組成的排列，無法進行狀態轉移。而且n又比較大，無法簡單地用一個位向量來表示這個排列。

觀察{3,1,2,7,4,6,5}，將其中所有大于4的數字加1，轉換成由{1～4,6～8}組成的排列{3,1,2,8,4,7,6}，其特征字符串依然是DIIDID。不難由此推廣出以下結論：給定一個長度為i的特征字符串，由{1,2,…,i}組成的匹配排列和由{1,2,…,j-1,j+1,…,i+1}組成的匹配排列一一對應。這樣就可以進行先進行等價轉換，再狀態轉移。

按照i=1～n的順序對第i位的數字進行決策，決策時，把{1,2,…j-1,j+1,…i}的排列轉換為{1,2…i-1}的排列，則狀態轉移可以分3種情況來討論：

（1）s[i]=='I'，則第i-1位必須小于j，于是有dp(i,j)=dp(i-1,1)+dp(i-1,2)+…+dp(i-1,j-1)=

（2）s[i]=='D'，則j之前就是以j+1～i其中之一為結尾的{1,2…j-1, j+1…i}的排列，也就是以j～i-1為結尾的{1,2…i-1}的排列，dp(i, j)=dp(i-1, j)+dp(i-1, j+1)+…+dp(i-1,i-1)=

（3）s[i]=='?'，則dp(i,j)=dp(i-1,1)+dp(i-1,2)+…+dp(i-1,i-1)=dp(i-l,k)。

觀察以上的狀態轉移方程，不難想到引入sum(i,j)dp(i,k)，則上述的狀態轉移就簡化成：

（1）s[i]=='T'，dp(i,j)=sum(i-1,j-1)。

（2）s[i]=='D'，dp(i,j)=sum(i-1,i-1)-sum(i-1,j-1)。

（3）s[i]=='?'，dp(i,j)=sum(i-1,i-1)。

初始條件為sum(1,1)=dp(1,1)=1，剩下的按照i從小到大,j從1到i，依次求dp(i,j)之后更新sum(i,j)。這樣通過引入sum(i,j)，時間復雜度就從O(n³)變成O(n²)。完整程序如下：

習題10-37　倍數問題（Yet Another Multiple Problem, Chengdu 2012, UVa1653）

輸入一個整數n（1≤n≤10000）和m個一位十進制數字，找n的最小倍數，其十進制表示中不含這m個數字中的任何一個。

【分析】

簡單的暴力做法，就是從最左邊開始逐位使用所有的可用數字嘗試構造，看看能不能整除n。但是這樣算法復雜度是指數級的，必然會超時。仔細觀察不難發現，每構造一位，除n的余數就會發生變化。把模n的每個余數作為一個結點，每構造一位就是沿著這張圖走一步，則本題實際上就是求到結點0的最短路徑，使用BFS非常合適。

具體來說，建一張圖，結點i代表除以n的余數等于i，然后每次附加一位數字就進行狀態轉移，轉移是基于模運算：(10*a+b)mod n=(amod n)*10+bmod n。那么主要的搜索邏輯就是從可用數字開始，搜索到結點0的最短路徑。另外，每擴展出一個結點，都記錄下結點前驅以及引起這次狀態轉移的數字，方便最終輸出結果。另外本題的BFS過程使用結點前驅判重，如果已經有前驅結點，則不再繼續搜索。

舉例來說，考慮n=14，m=3，3個禁用的數字分別是7、8和4。為方便討論起見，加入一個虛擬的根結點x，表示根結點，則一開始附加所有可用的數字（1,2,3,5,6,9，參見圖2.66中邊上的數字）。一開始就建立從x到每個數字對應的余數結點的所有邊。然后每個余數結點再添加一位進行狀態轉移，直到搜索出從x到0結點的最短路徑。最短路徑上每條邊上的數字拼接起來就是所求的數字。

算法的時間復雜度為O(n)，完整程序（C++11）如下：

習題10-38　正多邊形（Regular Polygon, UVa10824）

給出圓周上的n（n≤2000）個點，選出其中的若干個組成一個正多邊形，有多少種方法？輸出每行包含兩個整數S和F，表示有F種選法得到正S邊形。各行應按S從小到大排序。

【分析】

一個圓上的正K邊形的頂點把圓分成K個角度相等的弧。從其中一個頂點就可以得到其他所有的頂點。

回到本題，輸入時將每個點轉換為弧度，然后排序。之后遍歷所有的多邊形頂點數F，嘗試從每個點出發構造一個正F邊形，構造成功就記錄下來。注意任何一個點都記錄一下曾經判斷過的以其為頂點的多邊形的頂點數，避免重復判斷。算法的時間復雜度為O(n³*log(n))。完整程序（C++11）如下：

習題10-39　圓周上的三角形（Circum Triangle, UVa11186）

在一個圓周上有n（n≤500）個點。不難證明，其中任意3個點都不共線，因此都可以組成一個三角形。求這些三角形的面積之和。

【分析】

三角形的面積都可以通過圓的面積減去3個弓形（圖2.67左邊的圓中的灰色部分）的面積得出。那么所有三角形的面積之和就可以如下計算：個圓面積–所有的三角形對應的弓形面積之和。

首先對于所有輸入的點，將其轉換為弧度，然后進行遞增排序存到一個數組A[n]中。而對于每兩個弧度i和j（i<j且A_i<A_j）來說，i到j之間會有j-i-1個點，也就是說，會有j-i個頂點在ij上方，并且以弦ij為底的三角形。也就是說，弦ij下方的弓形面積會在上述公式中出現j-i-1次。而同理可知弦ij上方的弓形會出現n-2-(j-i-1)次。記a=A_j-A_i，則上方的弓形面積是 。下方的弓形面積就是πR²-S。二者的面積分別乘以出現次數再加起來就是：

S(n-2-（j-i-l）)+（j-i-l）(πR²-S)=S（n-2j+2i）+（j-i-l）πR²

首先令 ，遍歷每一對i<j，然后在sum上減去上述結果即可。注意當n<3時，sum=0。而且可以先當作單位圓計算，令R=1，輸出時再乘以R²即可。時間復雜度為O(n²)。完整程序（C++11）如下：

習題10-40　實驗法計算概率（Probability Through Experiments, ACM/ICPC Hatyai 2012, UVa12535）

輸入圓的半徑和圓上n（n≤20000）個點的極角，任選3點能組成多少個銳角三角形？

【分析】

如圖2.68所示，圓上的三角形，按順時針方向記其頂點為A、B、C。如果是鈍角三角形，則圓周上A到C的角AOC<180°。如果是直角三角形，則AOC=180°，B在A、C之間。如果是銳角三角形，則AOC>180°。顯然判斷銳角三角形更麻煩些，所以可以使用排除法，求出所有三角形的個數減去直角和鈍角三角形的個數即可。

輸入之后按弧度θ排序，為了方便處理，點集中要加入所有的θ+360。遍歷所有的極角A，然后查找所有的符合A<B<C≤A+180的B和C的個數。如果A到A+180中有M個點，則在總的三角形個數N(N-1)(N-2)/6中減去M(M-1)/2。完整程序（C++11）如下：

習題10-42　網格中的三角形（Triangles in the Grid, UVa12508）

一個n行m列的網格有n+1條橫線和m+1條豎線。任選3個點，可以組成很多三角形。其中有多少個三角形的面積位于閉區間[A,B]內？1≤n, m≤200，0≤A<B≤nm。

【分析】

直接枚舉三角形會非常麻煩，但是考慮到三角形的頂點都在橫線和豎線的交點上，不難想到每個這種三角形都有一個最小包圍矩形。那么首先是按照長寬來遍歷這種矩形的個數，考慮矩形的左上角坐標以及長寬即可。因為三角形的面積在計算時都要除以2，所以可以事先把A和B乘以2，然后在計算三角形面積時就不除了，同時也避免計算誤差。

對于一個長寬為(r,c)的矩形cell來說，不妨對如圖2.69所示的矩形的頂點做如下標記：

其包圍的三角形可以分為以下幾種情況，如圖2.70所示。

（1）3個頂點都在cell頂點上，共4種，面積都是r*c。

（2）只有兩個頂點在cell頂點上，這兩個頂點相鄰，則第三個頂點在對邊上。對第三個頂點進行計數可以得出這種三角形的個數為2*(r-1)+2*(c-1)。

（3）有兩個頂點形成對角線，另外的頂點在水平邊上。不妨設水平的那條邊長度為i，則i就需要滿足：A≤r*i≤B且1≤i< c– 1-> r≤r*i< r*(c-1)，也就是說max(A,r)≤r*i≤min(B,r*c-r)。符合這個不等式的i的個數乘以4就是這種情況下的三角形個數。

（4）跟上述情況類似，有兩個頂點形成對角線，另外的頂點在垂直邊上。不妨設垂直的那條邊長度為i，則這種情況下三角形的個數就是符合以下不等式的i的個數乘以4：max(A,c)≤c*i≤min(B, r*c-c)。

（5）有兩個頂點形成對角線，另外的頂點在矩形內部。令第三個頂點的坐標為(i,j)，意思是離邊AB的距離為i，離AD的距離為j。那么遍歷所有的i=1～r-1，當i確定時j就需要滿足：r*c-B-col * i≤r* j≤r*c-A-Col * i。就是要計算符合此條件的j的個數然后乘以4（對稱性考慮）。

（6）只有一個頂點在四角上，另外兩個點肯定都在跟這個點不相鄰的邊上。不妨設這個頂點就是A，則另外兩個頂點一定在CD和BC上，不妨設在CD上的頂點離D的距離為i，在BC上的頂點距離B為j。則三角形的面積為：2rc-(i*c+j*r+(r-i)*(c-j))=r*c-i*j，遍歷所有的i=1～r-1，對于指定的i，j就要滿足A≤r*c– i*j≤B→ r*c-B≤i*j≤r*c–A以及1≤j≤c– 1 → i≤i*j≤i*(c-1)，那么符合max(r*c-B,i)≤i*j≤min(r*c-A, i*(c-1))這個不等式的j的個數乘以4就是符合這種情況的三角形個數。

遍歷所有的r和c，大小為(r,c)的矩形個數就是(n-r+1) * (m-c+1)。對這些矩形分別進行三角形計數并且加起來就是最終所求的三角形個數。

需要注意的是，各種情況都牽涉求符合形如L≤K*X≤R的不等式的X的個數，可以將這個過程提取出來復用。完整程序如下：

習題10-43　整數對（Pair of Integers, ACM/ICPC NEERC 2001, UVa1654）

考慮一個不含前導零的正整數X，把它去掉一個數字以后得到另外一個數Y。輸入X+Y的值N（1≤N≤10⁹），輸出所有可能的等式X+Y=N。例如N=34有兩個解：31+3=34；27+7=34。

【分析】

記n的十進制表示形式的長度為L，不妨設從X右邊數第i（0≤i<L）位刪除數字x（0≤x<10）得到Y（如圖2.71所示），記X=a*10ⁱ⁺¹⁺x*10ⁱ+b，b<10ⁱ，則Y=a*10ⁱ+b。X+Y=n，故有11*a*10ⁱ+x*10ⁱ+2*b=N。

遍歷所有的i和x，固定i和x之后，求不定方程11*a*10ⁱ+2*b=N-x*10ⁱ的所有滿足a≥0且0≤b<10ⁱ整數解(a,b)，直接計算并輸出X和Y即可。完整程序（C++11）如下：