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

1、淺談信息學中狀態(tài)的合理設計與應用福建省福州第三中學 劉弈,引言,在日常生活中，工作時間與工作數(shù)量、單位效率的關系可以用下面的這個式子來表達：工作時間=工作數(shù)量*單位效率,引言,在信息學中，程序的運行時間是由兩個因素決定的，程序中所處理的狀態(tài)的總數(shù)目和處理每個狀態(tài)所花費的時間。程序運行時間=狀態(tài)總數(shù)*單位效率,引言,信息學中的狀態(tài)總數(shù)有時隱藏著許多冗余狀態(tài)。我們對狀態(tài)的合理設計與應用不僅能優(yōu)化的算法效率，還能夠幫助編程

2、人員理清思路，降低思維難度。,例一Square Root狀態(tài)分析合理地分析狀態(tài)數(shù)目例二Banal Tickets狀態(tài)優(yōu)化對狀態(tài)進行優(yōu)化例三Shoot Your Gun狀態(tài)設計重新設計狀態(tài),例三Shoot Your Gun,定義邊平行于坐標軸的簡單多邊形為矩形多邊形。已知在一個大的矩形多邊形M中有兩個小的矩形多邊形G和T。G邊上的任意一點可以向其左上、左下、右上、右下四個方向發(fā)射出射線。射線在遇

3、到M的邊時會發(fā)生光的鏡面反射。求從G邊上的任意一點發(fā)出一條射線到T所需要的最少反射次數(shù)。矩形多邊形最多包含50條邊，頂點坐標為整數(shù)在[0，4000]之內(nèi)。,,下圖左描繪出了一個例子，下圖中描述了在特殊點時的反射規(guī)則。射線方向如下圖右。,,題目中G邊上的任意一點都可以發(fā)射出射線。,枚舉？,,只需要處理整點和1/2點即可。,題目分析,使用普通的狀態(tài)表示法，將每個點發(fā)射出的4個方向分別做為4個點，進行構圖并使用最短路算法進行求解。這樣

4、的狀態(tài)數(shù)是O(n2)級別的，不能很好的解決此題。,分析條件,題目條件：路線軌跡遵循光的傳播路線 光是沿直線傳播的，只有在遇到障礙物時才會發(fā)生反射 只有發(fā)生反射時，路線方向才會發(fā)生改變。也就是說，只有在邊上才可能使方向發(fā)生變化。,,如下圖，圖中加粗的邊為射線的軌跡。,設計狀態(tài),因此我們不妨將邊上的點作為狀態(tài)使用spfa算法則可以滿足題目時間和空間的要求。用spfa算法解決此題效果并不好。,深入思考,光路是不會部分重疊的，要么完全

5、不重疊，要么完全重疊。只需要枚舉起點，然后每次遇到多邊形的邊的時候模擬反射，直到到達T集合。 這樣做之后，程序?qū)崿F(xiàn)起來十分簡單，運行效率也很高。至此，我們很好地解決了此題。,總結(jié),對狀態(tài)優(yōu)化的方法是基于對狀態(tài)的表示和對題目條件的深入分析而設計的。 在很多時候，對單位效率進行優(yōu)化難以奏效，對狀態(tài)進行合理地優(yōu)化與設計卻能大顯身手，取得良好的效果。對狀態(tài)進行合理地分析及設計能幫助我們更好的理清頭緒并設計出簡潔的算法。,謝 謝,例

6、一Square Root,若整數(shù)x滿足 x2 ≡ a (mod n)，則稱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,,,初步設計,不難想到如下算法：枚舉x，然后算出v

7、alue(x)=x^2 mod n，如果value(x)等于a，那么就稱這個x∈Root(a,n)。每次枚舉復雜度為O(N)，總復雜度為O(KN)，因此這個算法是十分低效的。,重要條件n為質(zhì)數(shù)，a與n互質(zhì),如何利用？,狀態(tài)分析,K最多為100000N最多為32767根據(jù)鴿巢原理即可知N不同的詢問最多只有32767個。事實上，由于n為質(zhì)數(shù)，因此當N為32767時最多只有3500多個取值。,,我們在使用枚舉法的時候，是對x進行

8、枚舉，然后判斷x是否∈Root(a,n)。仔細分析，不難發(fā)現(xiàn)，在求Root(a,n)的同時，我們可以順便求出Root(m,n) （0<=m<n)因此，我們可以在對詢問進行分類后，對于n相同的詢問，花O(N)的時間對第1個詢問進行枚舉，這樣剩下的詢問就可以用O(1)的時間得出結(jié)果了。時間復雜度變成O(prime(n)*n+klogk),例二Banal Tickets,給定一個長度為2n(n<=18)的數(shù)字串，數(shù)

9、字串中有的位置的數(shù)字是已知的，以[0,9]的數(shù)字表示；有的位置的數(shù)字是未知的，以?表示。當且僅當一個數(shù)字串滿足以下條件時，稱這個數(shù)字串interesting，否則為banal:要求求出所有interesting串和所有banal串的個數(shù)。,,初步分析,求interesting串的個數(shù)和求banal串的個數(shù)這兩個問題是等價的，兩者為互補關系。這樣，就可以通過求其中的一個命題，來直接得到另一命題的解。而求interesting串的

10、個數(shù)明顯比求banal串的個數(shù)簡單，因此只考慮求interesting串的個數(shù)的命題。,初步設計,不難得出這樣的一組方程：邊界條件當 時當 時,,,dp[i,j]表示前i位，乘積為j時的方案數(shù)。設dpa表示對前半部分進行動態(tài)規(guī)劃所得出的結(jié)果，dpb表示后半部。則interesting串的個數(shù)為：其中，m為最大的狀態(tài)數(shù)。,,分析狀態(tài),當s每位都取9時，總乘積達到最大,,天文數(shù)字！,需要

11、優(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

12、^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)，并建立一一對應的映射關系經(jīng)實踐發(fā)現(xiàn)，對于極限狀態(tài)，使用hash可以將原來的62萬左右的狀態(tài)數(shù)減少到5

13、萬以下，這樣我們就可以有效地剔除冗余了。,,圖中從A點向右下方向發(fā)射的射線與方格的邊交于B，C點向右下方向發(fā)射的射線與方格的邊交于D。更一般的非整點(x,y) 向右下方向發(fā)射的射線與方格的邊交于點(y,x)。同樣的，因此，對于所有在同一條邊上的非整點(x,y)，會且只會落在該方格的另一條邊上。即非整點只能到達非整點，且落點在同一條邊上。而落點所在的邊上的點又可以同理證明其發(fā)射的射線在到達另外一個方格的邊時，仍有如上性質(zhì)。因此同一條邊上的