ACM競賽中的數(shù)學(xué)方法初步

ACM競賽中的數(shù)學(xué)方法初步曾強2006-7-7計算幾何所謂計算幾何,一般就指向量方法來解幾何問題.為什么用向量?因為解析幾何方法在很多時候都顯得復(fù)雜,而且計算可能比較復(fù)雜,有精度損失問題.坐標法基礎(chǔ)計算幾何都是以坐標化為前提的必須知道一些基本的解析幾何的方法.例如:兩點距離的公式等向量的點積向量a,b點積(又稱內(nèi)積)的幾何意義是a在b(或b在a)上的投影長度(標量,注意可能為負值).計算方法是a·b=|a|·|b|·cosC,其中,C是向量a,b的夾角(下同).若向量a=(x1,y1,z1),b=(x2,y2,z2),則a·b=x1x2+y1y2+z1z2cosC可以由此計算出來應(yīng)用用于計算向量夾角.判斷兩向量是否垂直平面方程的向量形式:平面方程ax+by+cz=0(已通過移坐標軸去掉常數(shù)項),令平面法向量n=(a,b,c),點X(x,y,z),則平面方程記為n·X=0,實際上,如果平面過點P,則方程為n·(X-P)=0.應(yīng)用(續(xù))還可以計算點P(x0,y0,z0)到平面n·X=0的距離.把n單位化,不妨仍記為n,把向量OP往n上投影,即可得距離d=|n·OP|.判斷P是否在平面的哪一邊:n·OP為正時P在n指向的一側(cè),否則與n的指向相反向量叉積叉積又稱外積,a×b的結(jié)果是一個矢量,其數(shù)值是以a,b為邊的平行四邊形面積,即|a||b|sinC,其方向和a,b都垂直,并且,a,b,a×b構(gòu)成右手系.計算方法:應(yīng)用計算三角形或者平行四邊形面積計算點到直線(進一步,線段)的距離判斷向量(或者直線,線段)平行關(guān)系內(nèi)積和外積結(jié)合可以判斷復(fù)雜的位置關(guān)系點的旋轉(zhuǎn)變換原來的點(x,y)和變換后的點(x’,y’)的坐標之間滿足下面的公式: x’=xcosθ-ysin

θ y’=xsin

θ+ycos

θ其中,θ是逆時針旋轉(zhuǎn)的角度,這個公式適用于旋轉(zhuǎn)點在原點的情況.球面距離已知球半徑R,球面上兩點A,B的坐標A(x1,y1,z1),B(x2,y2,z2),球心在原點O,球面距離已知兩點的極坐標,其中, 為經(jīng)度數(shù), 為緯度數(shù),則可以證明球面距離為極坐標與直角坐標之間的換算關(guān)系:其中,θ是緯度,φ是經(jīng)度已知極坐標,也可以先用上面的公式計算直角坐標,然后算球面距離,但是會有精度損失計算幾何進一步的話題內(nèi)容很豐富,以上列舉的是基本的武器參加ACM競賽至少還需要了解二維凸包的算法(比較復(fù)雜)例題BOJ1012TheCircumferenceoftheCircle給出了三個點的坐標，請輸出由這三個點所確定的圓的周長，結(jié)果保留二位小數(shù)如圖,關(guān)鍵是求出外接圓半徑RABC可以由向量外積算出面積s,并得到sinA.由正弦定理,a/sinA=2R由此可以計算外接圓面積ABCabcBOJ1062PolygonProgrammingwithEase給了n邊形的n條邊的中點,求n個頂點的坐標,n是奇數(shù)可以建立兩個(x坐標和y坐標)聯(lián)系n個頂點和n個中點的n元一次方程組,注意到n是奇數(shù),這樣的方程有唯一解另一種思路可以證明以下事實:將一個n邊形依次以其每邊中點為對稱中心做中心對稱(反射)變換,n次變換之后,等價于對此多邊形做了一個以第一個頂點為中心,180度的旋轉(zhuǎn)變換.可以任意選定一個點p,依次對每個中心做反射變換,n次之后得到q,則第一個頂點是(p+q)/2,由此可以得到其它頂點BOJ1054Equidistance給定球面兩點A,B的極坐標,再給定第三點P的極坐標,求球面上到A,B兩點距離相等的點(組成一個大圓O1)到P點的最短球面距離首先,把極坐標轉(zhuǎn)換成直角坐標.以a,b,p代表A,B,P對應(yīng)的向量.到A,B距離相等的點集構(gòu)成一個平面,法向量是a-b,過點(a+b)/2,圓O1在這個平面上向量a-b和p之間的夾角theta可以比較容易計算出來(使用內(nèi)積方法和反三角函數(shù)),用球半徑乘以theta的余角即可以得出所求球面距離.注意特殊情況:如果AB兩點重合,則整個球面上的點到AB的距離都是相等的,那么P點到AB的距離也是相等的,所以此時所求的球面距離為P到自身的距離,為零.需要單獨處理BOJ1059BalancedFood給了扇形的桌子和其上的圓形pizza的位置和大小,pizza被切成若干塊(第一刀是沿x軸正向來切的),求一個取pizza的順序,使得pizza不從桌子上掉下來如右圖,左邊的兩塊pizza先取下面的后取上面的,可以不掉下來,右邊的pizza一定會掉下來扇形重心公式如果剩下的pizza的重心不在桌子上,pizza會掉下來.剩下的pizza的重心就是所有pizza片的幾何中心(坐標的算術(shù)平均值),pizza片的重心可以通過積分手算出來由此可以算得每塊pizza片的重心坐標,計算剩下來的這些pizza片的重心坐標的算術(shù)平均值就得到整塊剩下的pizza的重心(記做C)坐標.下面的問題是判斷C是否在桌子上.判斷重心是否在桌上如圖,tuv是桌子,c是pizza的重心坐標.注意到桌子不會比半圓更大,并且tuv是按照逆時針標號,于是得到c不在桌子上有以下情形:tu×tc<0tv×tc>0dist(t,c)>dist(t,u)ctuv實際上,還有更初等的判斷方法,就是通過內(nèi)積計算∠utc+∠ctv與∠utv是否相等,不等就說明c不在桌上.只是,此法需要計算反三角函數(shù),可能會損失精度.下面的問題是,如何來取這些pizza片才能使得整塊pizza不掉下去呢?吃pizza的順序如果注意到n的大小只有10,那么可以考慮最穩(wěn)妥的方法:回溯搜索.就是把所有可能的排列情況按照字典順序都搜索一遍,找到第一個可行的順序就退出搜索.如果搜索完成之后都沒有找到可行的取法,說明沒有可行方法存在.時間復(fù)雜度O(n!)具體方法,如果你曾寫過求迷宮的所有可行路的程序,應(yīng)該很容易實現(xiàn).以上是深度優(yōu)先搜索的策略實際上,本題使用貪心策略也是可以AC的(未能證明)每次都選一塊編號最小的可行的pizza片,如果某一步進行不下去,就退出報告無可行取法.時間復(fù)雜度O(n2).題外話本題的操作比較復(fù)雜,使用標準C++的算法庫配合復(fù)數(shù)類,可以簡化操作,但是要求熟悉上述工具.BOJ1072GlobalRoaming給了衛(wèi)星的極坐標,球面上一些點的極坐標,判斷哪些點可以看到衛(wèi)星解法甚多,以下為一種可能是比較簡單的考慮地球上一點的切平面,它的法向量從地心指向該點.下面只需要判斷衛(wèi)星位于切平面的那一側(cè)即可,這是我們已經(jīng)解決的問題.初等數(shù)論初等數(shù)論的內(nèi)容也是比較多的,本次主要介紹素數(shù)的測試,數(shù)的整除性和跟同余有關(guān)的一些知識.素數(shù)測試這是數(shù)論里的一個基本問題,而且現(xiàn)代社會應(yīng)用也很廣泛,發(fā)展了很多算法.首先要知道下面的方法.給了一個數(shù)n,從i＝3開始到n的算術(shù)根以步長2進行循環(huán)，如果n都不能整除i，那么n就是一個素數(shù)這種方法效率比較低,判斷一個數(shù)需要O(n1/2)的時間復(fù)雜度Eratosthenes篩法篩法(續(xù))篩法并不僅用于計算素數(shù),它還用于很多其它類似機理的場合(如BOJ1074AssistanceRequired)例如,計算Euler函數(shù)時,可以利用篩法來標號概率型算法注意到上述兩種方法其實都是比較慢的,為了快速判斷是否素數(shù),出現(xiàn)了多種測試素數(shù)的方法Miller-Rabin測試:基于Fermat小定理的測試,一次測試把一個合數(shù)判斷成素數(shù)的概率小于1/4,多次測試使得犯錯誤的概率更小.參加ACM競賽需要知道這個算法,具體細節(jié)可在網(wǎng)上找到唯一分解定理每個正整數(shù)都可以惟一地表示成素數(shù)的乘積，其中素數(shù)因子從小到大依次出現(xiàn),換句話說,任意正整數(shù)n可以寫成n=2a1*3a2*5a3*…,其中a1,a2,a3等為非負整數(shù),這稱為n的素因子標準分解式數(shù)的整除性令a和b是不全為0的兩個整數(shù)，能使d|a和d|b的最大整數(shù)稱為a和b的最大公約數(shù)，用gcd(a,b)表示，或者記為(a,b)令a和b是不全為0的兩個整數(shù)，能使a|d和b|d的最小整數(shù)稱為a和b的最小公倍數(shù)，用lcm(a,b)表示，或者記為[a,b]定理:ab=gcd(a,b)*lcm(a,b)GCD的計算計算gcd(m,n),使用Euclid除法:while(m>n?(m%=n):(n%=m));GCD為m,n中的非零數(shù),也可以寫為m+n.時間復(fù)雜度O(logn),若m>n上面為循環(huán)算法,可以寫出遞歸算法.GCD的計算(2)如果(a,b)=d,則一定存在整數(shù)x,y,使得xa+yb=d.求x,y,仍然使用(擴展的)Euclid算法(遞歸實現(xiàn)):int

gcd(inta,intb,int&x,int&y){

if(!b){x=1;y=0;returna;}else{intr=gcd(b,a%b,x,y);t=x;x=y;y=t–a/b*y;returnr;}}同余設(shè)m是一個正整數(shù),若a,b是整數(shù),且m|(a-b),則稱a和b模m同余,記做a≡b(modm)整數(shù)的一種分類方法:給了一個整數(shù)m,則可以把整數(shù)按照除m的余數(shù)分為m類.特別地,m=2時,分為奇數(shù)和偶數(shù)同余性質(zhì)設(shè)m是正整數(shù),則下面命題成立:(i)b1≡a1(modm),b2≡a2(modm),則:b1±b2≡a1±a2(modm),b1b2≡a1a2(modm)若ac≡bd(modm),c≡d(modm),且(m,c)=1,則a≡b(modm)Euler函數(shù)定義:1~n中和n互素的正整數(shù)個數(shù)記做

(n),

即為Euler函數(shù)

Euler函數(shù)的性質(zhì):(mn)=(m)(n),m,n是互素正整數(shù).設(shè)正整數(shù) 為n的素因子標準分解式,則:上述兩條性質(zhì)可以用于計算Euler函數(shù)的數(shù)值涉及計算Euler函數(shù)值的ACM賽題,可以參見POJ2480Longge'sproblem,POJ2478FareySequenceEuler定理設(shè)k是與正整數(shù)m互素的整數(shù),則k(m)≡1(modm)推論(Fermat小定理):設(shè)p是素數(shù),若p不能整除k,則kp-1≡1(modp)中國剩余定理(孫子定理)設(shè)m1,m2,…,mk是k個兩兩互素的正整數(shù),任給k個整數(shù)a1,a2,…,ak,必存在整數(shù)x,使得x≡ai(modmi)(i=1,2,…,k),且在0<=x<M=m1m2…mk內(nèi)有唯一解從此定理的證明過程我們可以得到求出x具體算法記Mi=M/mi，則(Mi,mi)=1存在pi,qi，Mipi+miqi=1記錄ei=Mipi，則j=i時ei≡1(modmj)J≠i時ei≡0(modmj)則e1a1+e2a2+…+ekak就是一個解,調(diào)整(加減M)得到[0,m)內(nèi)的唯一解.此算法用到先前的(擴展的)Euclid除法此問題的一個實例可以參看POJ1006BiorhythmsBOJ1040Goldbach's

Conjecture

給了偶數(shù)n,求兩個素數(shù)a,b,使得n=a+b,并且b-a的值最大.使用篩法選出一個到1000000的素數(shù)表,然后從i=3開始枚舉素數(shù),遇到合適的就停下來BOJ1074AssistanceRequired也是篩法的例子,把2的倍數(shù)篩掉,再把3的倍數(shù)篩掉,…,求剩下來的數(shù)中的第n個.在篩的過程中,把沒有篩掉的放到一個數(shù)組中,可以直接輸出第n個數(shù).BOJ1008Happy20042004x的所有因數(shù)的和,除以29的余數(shù)是多少?首先,根據(jù)Fermat小定理,200428≡1(mod29),根據(jù)同余性質(zhì),200428n≡1(mod29).又知(a+b)%c=(a%c+b%c)%c,(ab)%c=(a%c)(b%c)%c簡化計算的因子考慮2004x的因子,把它們分成以下幾類:是2004x-28n的因子,當然也是2004x的因子不是2004x-28n的因子,但是2004x的因子首先說明,第二類因子的和模29等于0.2004=22*3*167,根據(jù)同余性質(zhì),只需要考慮4,3,22(=167%29)作為2004的因子.令y=x-28n,則第二類因子必然可以寫為ay*2s*3r*22t的形式,其中a=22,3,22證明細節(jié)在上述表達式中,2s*3r*22t一定是200428n的因子.從而,s,r,t一定可以取遍1~28n(s到56n)的值.固定r,t的取值,對s求和,只需證明∑say*2s*3r*22t%29=0,其中y,r,t是常數(shù).上式等價于證明∑s2s%29=0,s=1,…,56n,由等比數(shù)列求和公式得到∑s2s=256n-1.另一方面,根據(jù)Fermat小定理,228≡1(mod29),從而256n-1%29=0,得證.求解我們只需要考慮2004y的因子的和模29.其中y=x%28.2004y的素因子標準分解式為22y3y167y,只需考慮形如22s*3r*22t(s,r,t<=y<28)的因子.可以通過枚舉法得出所有因子.進一步,這些因子的和模29的結(jié)果就可以得出來了

優(yōu)化建議不用考慮所有因子,只分別考慮4,3,22的冪這部分因子的和模29的結(jié)果,相乘后再模29可得最后結(jié)果.依據(jù):求余操作可以與加法和乘法交換次序.基于上面的結(jié)果,注意到這些冪的指數(shù)最大到27,可以做三個表,分別存放4,3,22的冪的和模29的結(jié)果.如p4[i]表示∑0<=s<=i4s%29的結(jié)果.如此,只要知道了y,最后的結(jié)果為(p4[y]*p3[y]*p22[y])%29組合數(shù)學(xué)組合數(shù)學(xué)的內(nèi)容很多,題目也可以出到很困難,只介紹最基礎(chǔ)的跟本次題目相關(guān)的內(nèi)容.排列數(shù)和組合數(shù)組合數(shù)的計算組合數(shù)由于階乘的數(shù)量級很大,所以通常在計算時都采用邊乘邊除的方法,以避免溢出.更強的優(yōu)化方法是在乘之前先把分子的所有數(shù)與分母約分,這樣,如果能保證最后不溢出,那么中間步驟也一定不會溢出圓排列(循環(huán)排列)定理:n個元素的集合的循環(huán)r排列的個數(shù)為多重集的排列定理1:令S是一個多重集,它有k個不同類型的元素,每一個元素都有無窮重復(fù)個數(shù).則S的r排列的個數(shù)是kr定理2:令S是一個多重集,有k個不同類型的元素,個元素的重述分別為n1,n2,…,nk.設(shè)S的大小為n=n1+n2+…+nk,

則S的排列數(shù)等于多重集的組合定理:令S為具有k種類型元素的一個多重集,每種元素均有無窮重復(fù)數(shù),則S的r組合的個數(shù)等于當元素的重復(fù)數(shù)不是無窮時,計算這樣的r組合需要使用生成函數(shù)(母函數(shù)),容斥原理等工具.組合數(shù)學(xué)的大致內(nèi)容對于要參加ACM競賽的同學(xué),最好要掌握下面的一些知識(主要是用于計數(shù)):排列組合原理(包括禁位排列等非常規(guī)情形)容斥原理生成函數(shù)和遞推關(guān)系一些特殊的計數(shù)序列,例如Catalan數(shù)(如BOJ1007就是計算這個數(shù))Polya計數(shù)法(復(fù)雜的計數(shù),如BOJ1051)此外,ACM競賽中還可能考離散概率論,主要也是結(jié)合組合計數(shù)來考的.概率論的古典概型(不一定是離散的)也可能會出現(xiàn)在ACM賽場上(如POJ2598MatchThrowingGame,蒲豐投針問題)BOJ1064PathsonaGrid為多重集的排列問題,歸結(jié)為計算組合數(shù)BOJ1027BinomialShowdown,計算組合數(shù)BOJ1085InDanger經(jīng)典的Josephus問題:n個人圍成一圈從1到n編號,從第一個人開始進行一二報數(shù),報到二的出隊,問最后留下來的是哪一個人.這個問題的一般形式是報數(shù)從1到m報數(shù),但是當m=2時(也就是本題的情形),可以推出形式比較簡單的公式.推導(dǎo)過程我們可以從數(shù)字比較小的情況開始來猜測公式的形式,然后使用數(shù)學(xué)歸納法來證明.我們記J(n)為n個人時的最后剩下來的編號,顯然,J(1)=1