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

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

福建省福州第三中學(xué)

劉弈

引言在日常生活中，工作時(shí)間與工作數(shù)量、單位效率的關(guān)系可以用下面的這個(gè)式子來表達(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)。我們對狀態(tài)的合理設(shè)計(jì)與應(yīng)用不僅能優(yōu)化的算法效率，還能夠幫助編程人員理清思路，降低思維難度。例一 SquareRoot 狀態(tài)分析合理地分析狀態(tài)數(shù)目例二 BanalTickets 狀態(tài)優(yōu)化對狀態(tài)進(jìn)行優(yōu)化例三 ShootYourGun 狀態(tài)設(shè)計(jì)重新設(shè)計(jì)狀態(tài)例三 ShootYourGun定義邊平行于坐標(biāo)軸的簡單多邊形為矩形多邊形。已知在一個(gè)大的矩形多邊形M中有兩個(gè)小的矩形多邊形G和T。G邊上的任意一點(diǎn)可以向其左上、左下、右上、右下四個(gè)方向發(fā)射出射線。射線在遇到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)行求解。這樣的狀態(tài)數(shù)是O(n2)級(jí)別的，不能很好的解決此題。分析條件題目條件：路線軌跡遵循光的傳播路線光是沿直線傳播的，只有在遇到障礙物時(shí)才會(huì)發(fā)生反射只有發(fā)生反射時(shí)，路線方向才會(huì)發(fā)生改變。也就是說，只有在邊上才可能使方向發(fā)生變化。如下圖，圖中加粗的邊為射線的軌跡。設(shè)計(jì)狀態(tài)因此我們不妨將邊上的點(diǎn)作為狀態(tài)使用spfa算法則可以滿足題目時(shí)間和空間的要求。用spfa算法解決此題效果并不好。深入思考光路是不會(huì)部分重疊的，要么完全不重疊，要么完全重疊。只需要枚舉起點(diǎn)，然后每次遇到多邊形的邊的時(shí)候模擬反射，直到到達(dá)T集合。這樣做之后，程序?qū)崿F(xiàn)起來十分簡單，運(yùn)行效率也很高。至此，我們很好地解決了此題?？偨Y(jié)對狀態(tài)優(yōu)化的方法是基于對狀態(tài)的表示和對題目條件的深入分析而設(shè)計(jì)的。在很多時(shí)候，對單位效率進(jìn)行優(yōu)化難以奏效，對狀態(tài)進(jìn)行合理地優(yōu)化與設(shè)計(jì)卻能大顯身手，取得良好的效果。對狀態(tài)進(jìn)行合理地分析及設(shè)計(jì)能幫助我們更好的理清頭緒并設(shè)計(jì)出簡潔的算法。謝謝例一 SquareRoot若整數(shù)x滿足x2≡a(modn)，則稱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，然后算出value(x)=x^2modn，如果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è)取值。我們在使用枚舉法的時(shí)候，是對x進(jìn)行枚舉，然后判斷x是否∈Root(a,n)。仔細(xì)分析，不難發(fā)現(xiàn)，在求Root(a,n)的同時(shí)，我們可以順便求出Root(m,n)（0<=m<n)因此，我們可以在對詢問進(jìn)行分類后，對于n相同的詢問，花O(N)的時(shí)間對第1個(gè)詢問進(jìn)行枚舉，這樣剩下的詢問就可以用O(1)的時(shí)間得出結(jié)果了。時(shí)間復(fù)雜度變成O(prime(n)*n+klogk)例二 BanalTickets給定一個(gè)長度為2n(n<=18)的數(shù)字串，數(shù)字串中有的位置的數(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è)命題，來直接得到另一命題的解。而求interesting串的個(gè)數(shù)明顯比求banal串的個(gè)數(shù)簡單，因此只考慮求interesting串的個(gè)數(shù)的命題。初步設(shè)計(jì)不難得出這樣的一組方程：邊界條件

當(dāng)時(shí) 當(dāng)時(shí)dp[i,j]表示前i位，乘積為j時(shí)的方案數(shù)。設(shè)dpa表示對前半部分進(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ù)字！需要優(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)?無法用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^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)，并建立一一對應(yīng)的映射關(guān)系經(jīng)實(shí)踐發(fā)現(xiàn)，對于極限狀態(tài)，使用hash可以將原來的62萬左右的狀態(tài)數(shù)減少到5萬以下，這樣我們就可以有效地剔除冗余了。圖中從A點(diǎn)向右下方向發(fā)射的射線與方格的邊交于B，C點(diǎn)向右下方向發(fā)射的射線與方格的邊交于D。更一般的非整點(diǎn)(x,y)向右下方向發(fā)射的射線與方格的邊交于點(diǎn)(