算法合集之《淺談信息學中狀態(tài)的合理設(shè)計與應(yīng)用》

淺談信息學中狀態(tài)的合理設(shè)計與應(yīng)用

福建省福州第三中學

劉弈

引言在日常生活中，工作時間與工作數(shù)量、單位效率的關(guān)系可以用下面的這個式子來表達：工作時間=工作數(shù)量*單位效率引言在信息學中，程序的運行時間是由兩個因素決定的，程序中所處理的狀態(tài)的總數(shù)目和處理每個狀態(tài)所花費的時間。程序運行時間=狀態(tài)總數(shù)*單位效率引言信息學中的狀態(tài)總數(shù)有時隱藏著許多冗余狀態(tài)。我們對狀態(tài)的合理設(shè)計與應(yīng)用不僅能優(yōu)化的算法效率，還能夠幫助編程人員理清思路，降低思維難度。例一 SquareRoot 狀態(tài)分析合理地分析狀態(tài)數(shù)目例二 BanalTickets 狀態(tài)優(yōu)化對狀態(tài)進行優(yōu)化例三 ShootYourGun 狀態(tài)設(shè)計重新設(shè)計狀態(tài)例三 ShootYourGun定義邊平行于坐標軸的簡單多邊形為矩形多邊形。已知在一個大的矩形多邊形M中有兩個小的矩形多邊形G和T。G邊上的任意一點可以向其左上、左下、右上、右下四個方向發(fā)射出射線。射線在遇到M的邊時會發(fā)生光的鏡面反射。求從G邊上的任意一點發(fā)出一條射線到T所需要的最少反射次數(shù)。矩形多邊形最多包含50條邊，頂點坐標為整數(shù)在[0，4000]之內(nèi)。下圖左描繪出了一個例子，下圖中描述了在特殊點時的反射規(guī)則。射線方向如下圖右。題目中G邊上的任意一點都可以發(fā)射出射線。枚舉？只需要處理整點和1/2點即可。 題目分析使用普通的狀態(tài)表示法，將每個點發(fā)射出的4個方向分別做為4個點，進行構(gòu)圖并使用最短路算法進行求解。這樣的狀態(tài)數(shù)是O(n2)級別的，不能很好的解決此題。分析條件題目條件：路線軌跡遵循光的傳播路線光是沿直線傳播的，只有在遇到障礙物時才會發(fā)生反射只有發(fā)生反射時，路線方向才會發(fā)生改變。也就是說，只有在邊上才可能使方向發(fā)生變化。如下圖，圖中加粗的邊為射線的軌跡。設(shè)計狀態(tài)因此我們不妨將邊上的點作為狀態(tài)使用spfa算法則可以滿足題目時間和空間的要求。用spfa算法解決此題效果并不好。深入思考光路是不會部分重疊的，要么完全不重疊，要么完全重疊。只需要枚舉起點，然后每次遇到多邊形的邊的時候模擬反射，直到到達T集合。這樣做之后，程序?qū)崿F(xiàn)起來十分簡單，運行效率也很高。至此，我們很好地解決了此題?？偨Y(jié)對狀態(tài)優(yōu)化的方法是基于對狀態(tài)的表示和對題目條件的深入分析而設(shè)計的。在很多時候，對單位效率進行優(yōu)化難以奏效，對狀態(tài)進行合理地優(yōu)化與設(shè)計卻能大顯身手，取得良好的效果。對狀態(tài)進行合理地分析及設(shè)計能幫助我們更好的理清頭緒并設(shè)計出簡潔的算法。謝謝例一 SquareRoot若整數(shù)x滿足x2≡a(modn)，則稱x是以n為模時a的平方根，記root(a,n)為滿足以上條件的x的集合。題目包含k個詢問，每次詢問給出a和n，其中n為質(zhì)數(shù)，且a與n互質(zhì)，要求出所有在(0,n-1)區(qū)間內(nèi)的root(a,n)。數(shù)據(jù)范圍

1<=a,n<=32767，n為質(zhì)數(shù)，a與n互質(zhì)

1<=k<=100000初步設(shè)計不難想到如下算法： 枚舉x，然后算出value(x)=x^2modn，如果value(x)等于a，那么就稱這個x∈Root(a,n)。每次枚舉復(fù)雜度為O(N)，總復(fù)雜度為O(KN)，因此這個算法是十分低效的。重要條件 n為質(zhì)數(shù)，a與n互質(zhì)如何利用？狀態(tài)分析K最多為100000N最多為32767根據(jù)鴿巢原理即可知N不同的詢問最多只有32767個。事實上，由于n為質(zhì)數(shù)，因此當N為32767時最多只有3500多個取值。我們在使用枚舉法的時候，是對x進行枚舉，然后判斷x是否∈Root(a,n)。仔細分析，不難發(fā)現(xiàn)，在求Root(a,n)的同時，我們可以順便求出Root(m,n)（0<=m<n)因此，我們可以在對詢問進行分類后，對于n相同的詢問，花O(N)的時間對第1個詢問進行枚舉，這樣剩下的詢問就可以用O(1)的時間得出結(jié)果了。時間復(fù)雜度變成O(prime(n)*n+klogk)例二 BanalTickets給定一個長度為2n(n<=18)的數(shù)字串，數(shù)字串中有的位置的數(shù)字是已知的，以[0,9]的數(shù)字表示；有的位置的數(shù)字是未知的，以?表示。當且僅當一個數(shù)字串滿足以下條件時，稱這個數(shù)字串interesting，否則為banal:要求求出所有interesting串和所有banal串的個數(shù)。初步分析求interesting串的個數(shù)和求banal串的個數(shù)這兩個問題是等價的，兩者為互補關(guān)系。這樣，就可以通過求其中的一個命題，來直接得到另一命題的解。而求interesting串的個數(shù)明顯比求banal串的個數(shù)簡單，因此只考慮求interesting串的個數(shù)的命題。初步設(shè)計不難得出這樣的一組方程：邊界條件

當時 當時dp[i,j]表示前i位，乘積為j時的方案數(shù)。設(shè)dpa表示對前半部分進行動態(tài)規(guī)劃所得出的結(jié)果，dpb表示后半部。 則interesting串的個數(shù)為：其中，m為最大的狀態(tài)數(shù)。分析狀態(tài)當s每位都取9時，總乘積達到最大天文數(shù)字！需要優(yōu)化！剔除冗余狀態(tài)j只可能是[0,9]這10個數(shù)的乘積，而這幾個數(shù)字只包含2,3,5,7這4個質(zhì)數(shù)。因此可以將狀態(tài)改為dp[i,a,b,c,d]，表示前i位，乘積為2a3b5c7d的方案數(shù)。因為0無法用2a3b5c7d表示，所以用2(-1)替代。狀態(tài)總數(shù)

a最多為3n(考慮全部數(shù)字為8的情況)，b最多為2n(全部為9)，c最多為n(全部為5)，d最多為n(全部為7)。當n=18時，狀態(tài)數(shù)目達到最大，為2*3*2*18^4=1259712(使用滾動數(shù)組)。但是本題需要使用高精度計算，這種做法并不能令人滿意。用2a3b5c7d這樣的狀態(tài)表示仍然含有許多冗余狀態(tài)！例如，23n32n5n7n這個狀態(tài)就不可能出現(xiàn)，因為23n就已經(jīng)決定了n位數(shù)字全為8，所以其他質(zhì)數(shù)的個數(shù)不可能大于0我們可以使用hash，通過一個BFS的過程，遍歷出所有的可用狀態(tài)，并建立一一對應(yīng)的映射關(guān)系經(jīng)實踐發(fā)現(xiàn)，對于極限狀態(tài)，使用hash可以將原來的62萬左右的狀態(tài)數(shù)減少到5萬以下，這樣我們就可以有效地剔除冗余了。圖中從A點向右下方向發(fā)射的射線與方格的邊交于B，C點向右下方向發(fā)射的射線與方格的邊交于D。更一般的非整點(x,y)向右下方向發(fā)射的射線與方格的邊交于點(