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

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

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

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

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

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

6、一Square Root,若整數(shù)x滿足 x2 ≡ a (mod n)，則稱x 是以n為模時(shí)a的平方根，記root(a,n)為滿足以上條件的x的集合。題目包含k個(gè)詢問，每次詢問給出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è)計(jì),不難想到如下算法：枚舉x，然后算出v

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

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

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

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

11、優(yōu)化！,剔除冗余,狀態(tài)j只可能是[0,9]這10個(gè)數(shù)的乘積，而這幾個(gè)數(shù)字只包含2,3,5,7這4個(gè)質(zhì)數(shù)。因此可以將狀態(tài)改為dp[i,a,b,c,d]，表示前i位，乘積為2a3b5c7d的方案數(shù)。因?yàn)?無(wú)法用2a3b5c7d表示，所以用2(-1)替代。,,,,,狀態(tài)總數(shù)a最多為3n(考慮全部數(shù)字為8的情況)，b最多為2n(全部為9)，c最多為n(全部為5)，d最多為n(全部為7)。當(dāng)n=18時(shí)，狀態(tài)數(shù)目達(dá)到最大，為2*3*2*18

12、^4=1259712(使用滾動(dòng)數(shù)組)。但是本題需要使用高精度計(jì)算，這種做法并不能令人滿意。,,用2a3b5c7d這樣的狀態(tài)表示仍然含有許多冗余狀態(tài)！例如，23n32n5n7n這個(gè)狀態(tài)就不可能出現(xiàn)，因?yàn)?3n就已經(jīng)決定了n位數(shù)字全為8，所以其他質(zhì)數(shù)的個(gè)數(shù)不可能大于0,,我們可以使用hash，通過一個(gè)BFS的過程，遍歷出所有的可用狀態(tài)，并建立一一對(duì)應(yīng)的映射關(guān)系經(jīng)實(shí)踐發(fā)現(xiàn)，對(duì)于極限狀態(tài)，使用hash可以將原來(lái)的62萬(wàn)左右的狀態(tài)數(shù)減少到5

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