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

1、淺談信息學(xué)中狀態(tài)的合理設(shè)計與應(yīng)用目錄淺談信息學(xué)中狀態(tài)的合理設(shè)計與應(yīng)用1摘要2關(guān)鍵字2正文2一、引言2二、狀態(tài)設(shè)計與應(yīng)用的相關(guān)應(yīng)用及例題分析31、合理分析狀態(tài)3例一、square root3問題描述:3問題分析:3初步優(yōu)化:3深入分析:3小結(jié):32、合理改進狀態(tài)3例二、banal tickets3題目描述:3問題分析:3初步分析:3進一步分析：3小結(jié)：33、合理設(shè)計狀態(tài)3例三、shoot your gun3問題描述:3題目分析:3進一步分析：3深入思考：3小結(jié)：3三、總結(jié)3附錄3淺談信息學(xué)中狀態(tài)的合理設(shè)計與應(yīng)用摘要狀態(tài)分析與設(shè)計是信息學(xué)中一個重要的部分，在動態(tài)規(guī)劃、搜索、枚舉等眾多算法中均有很多

2、應(yīng)用。對狀態(tài)本身的分析與研究也是十分重要的，而本文就針對這個方面進行了探討研究。本文通過三個例題闡述了對于狀態(tài)的合理設(shè)計在解題中所發(fā)揮的重要作用。關(guān)鍵字狀態(tài)、分析、優(yōu)化、改進正文一、 引言在日常生活中，工作時間與工作數(shù)量、單位效率的關(guān)系可以用下面的這個式子來表達：工作時間=工作數(shù)量*單位效率（上式中的單位效率是指完成一個工作所需花費的時間）在信息學(xué)中，程序的運行時間是由兩個因素決定的：程序中所處理的狀態(tài)總數(shù)和處理每個狀態(tài)所花費的時間，因此程序運行的總時間可以用下面的式子來表示：程序運行時間=狀態(tài)總數(shù)*單位效率眾所周知，式中的工作數(shù)量是無法減少的，因此大多數(shù)人選擇了減少對每一個工作所花費的時間，

3、即提高單位效率，從而減少工作總時間，達到優(yōu)化的目的。從表面上看，式與式并沒有什么本質(zhì)區(qū)別，然而在信息學(xué)中，式中的狀態(tài)總數(shù)不完全等同于式中的工作數(shù)量，因為不同的狀態(tài)表示可能產(chǎn)生不同的狀態(tài)量。合理的狀態(tài)設(shè)計有時能有效地減少冗余，從而通過減少狀態(tài)總數(shù)而達到優(yōu)化的目的。此外，好的的狀態(tài)表示還能夠幫助編程人員理清思路，為我們的解題帶來嶄新的思維方式，降低了解題難度。而對單位效率進行優(yōu)化有時則無法達到這樣的效果。二、 狀態(tài)分析與設(shè)計的相關(guān)應(yīng)用本文將重點介紹三道例題：square root、banal tickets、shoot your gun，從三個方面描述了如何根據(jù)問題的核心要求分析出問題的本質(zhì)，并合

4、理改進狀態(tài)的設(shè)計與表示方法，由此帶來解題新思路。其中，例題一Square Root，通過合理地分析，減少狀態(tài)總數(shù)，用樸素算法解決問題。例題二Banal Tickets，改進狀態(tài)表示方法，通過對狀態(tài)進行優(yōu)化，取得良好的效果。例題三Shoot Your Gun，在常規(guī)狀態(tài)表示法無法奏效時，重新設(shè)計了狀態(tài)表示，極大的減少了狀態(tài)總數(shù)。并由此得出了更為簡潔的算法，成功的降低了編程復(fù)雜度及時間復(fù)雜度。1、合理分析狀態(tài)人們在解決問題時，往往要先分析算法的復(fù)雜度是否能夠滿足題目的空間及時間的限制，之后才進行編程。如果在分析復(fù)雜度時出現(xiàn)錯誤，過高或過低地估計了算法的復(fù)雜度，都會直接影響問題的解決。復(fù)雜度估計過低

5、，往往使得編程人員盲目下手，就算最后恍然大悟，發(fā)現(xiàn)算法不可行，也已經(jīng)浪費了不少編程時間。如果不能及時找到有效的改進，往往就只能選擇放棄該算法而另起爐灶。這樣的錯誤在嚴格限定時間編程的信息學(xué)賽場上導(dǎo)致的后果是很嚴重的，甚至?xí)苯佑绊戇x手的心理及比賽的結(jié)果；反之，如果復(fù)雜度估計過高，可能會使選手放棄本來可行的解法而另尋出路。由于這樣一點分析上的失誤而與正確的算法失之交臂，難道不是很可惜嗎？下面的例子就是講述如何通過分析狀態(tài)總數(shù)做相應(yīng)優(yōu)化，消除其中的冗余，并正確判斷與運用算法，減少程序運行總時間，提高效率，使問題得以解決。例一、 square root 題目來源問題描述:若整數(shù)x滿足 x2 a (m

6、od n)，則稱x是以為模時的平方根，記為滿足以上條件的x的集合。題目包含個詢問，每次詢問給出和，其中為質(zhì)數(shù)，且與互質(zhì)，要求出所有在(0,n-1)區(qū)間內(nèi)的。問題分析:這題是一道模平方根( Modular Square Roots )的問題，有專門的數(shù)學(xué)方法來解決此類問題，如有興趣，可以參考相關(guān)資料。但是，解決模平方根的問題需要學(xué)習(xí)和掌握較高深的數(shù)學(xué)知識，若想在競賽時推導(dǎo)數(shù)學(xué)公式，需要花費不少的時間。假如在推公式時遇到了阻礙，我們就會考慮用其他替代方法來解決這樣的問題。首先考慮最普通的方法枚舉。枚舉的基本思路是窮舉x，計算，如果等于，那么就稱這個。對于一個詢問，枚舉的復(fù)雜度為，則整體復(fù)雜度為，在

7、極限數(shù)據(jù)時，總枚舉量可高達30多億，顯然無法在要求的時限內(nèi)出解。經(jīng)過上述分析，枚舉法似乎很難滿足題目要求。但枚舉法是否就真的不可行呢？我們需要對狀態(tài)進行合理的分析。初步優(yōu)化:枚舉法雖然無法直接解決這個問題，但是我們注意到這樣一個信息：每次對一個詢問使用枚舉法處理，實際上可以得到所有的詢問的答案，。對一個詢問花費了的時間去枚舉，卻只利用了這中間的一小部分，浪費嚴重。那么，應(yīng)該如何合理利用這些“冗余”操作呢？再次回顧題目，可以看到k（即詢問數(shù)）最多有100000個，但是的取值只有32767個。顯然，根據(jù)簡單的鴿籠原理可得知，這些詢問中最多出現(xiàn)32767個不同的。而對于相同的，可以對第1個詢問進行枚

8、舉，之后的詢問就可以得出結(jié)果。而只需要一個排序，就可以對所有詢問進行分類。這樣就成功地對原算法進行了優(yōu)化。但是即使如此，最多還是要處理32767個不同的詢問，時間復(fù)雜度為，仍然無法在時限內(nèi)出解。因此，我們還不能停下優(yōu)化的腳步。深入分析:仔細分析枚舉的算法，我們發(fā)現(xiàn)在枚舉時并沒有對題目條件進行合理的利用。題目條件中給出了這樣的信息：為質(zhì)數(shù)，且與互質(zhì)。題目給出這樣條件就肯定有利用的價值，那么該如何利用這個條件呢？注意到為質(zhì)數(shù)這個重要的信息，根據(jù)平時總結(jié)的經(jīng)驗，以內(nèi)的質(zhì)數(shù)個數(shù)總會比小很多，能否把這個作為突破口呢？在使用篩法把32767中的質(zhì)數(shù)都列出來后，發(fā)現(xiàn)質(zhì)數(shù)的個數(shù)僅為3500個左右，比32767

9、小了近10倍！如此分析后發(fā)現(xiàn)，原算法的狀態(tài)數(shù)其實沒有，而僅為，其中表示n以內(nèi)的質(zhì)數(shù)個數(shù)，這樣就可以大膽地采用枚舉算法來解決此題，時間復(fù)雜度約為，已經(jīng)可以很好的滿足了題目的時間限制。如果采取桶排，可以將時間復(fù)雜度降為，但是由于排序不是這題時間的瓶頸，所以不影響總的時間復(fù)雜度。小結(jié):要想順利解決數(shù)學(xué)題，一般需要很深的數(shù)學(xué)造詣，而對于大部分選手，這是十分困難的。但是信息學(xué)競賽不同于數(shù)學(xué)競賽，信息學(xué)競賽中的許多數(shù)學(xué)問題并不是只有通過使用數(shù)學(xué)方法才能解決的，總會有一些替代算法。這些算法一般不能滿足題目的限制條件。但這些做法并不總是一無是處的，只要我們細心發(fā)掘，也許成功就在不遠處。本題的做法雖然不一定能適

10、用于所有數(shù)學(xué)問題，但是卻代表了狀態(tài)設(shè)計的思想。在這題中，面對巨大的數(shù)據(jù)量，正當不知所措的時候，通過合理地分析了數(shù)據(jù)中狀態(tài)的量，肯定了算法的效率。如果沒有及時對狀態(tài)進行分析，恐怕會陷入“優(yōu)化”的“深淵”而無法自拔。此題的解法雖然簡單，但是卻給予我們很大的啟發(fā)。2、合理改進狀態(tài)表示動態(tài)規(guī)劃是信息學(xué)中的重要算法之一，以其靈活多變的思維方式及狀態(tài)表示，成為許多初學(xué)者難以逾越的一道難關(guān)。甚至對于一些已經(jīng)在信息學(xué)競賽中取得優(yōu)異成績的人，動態(tài)規(guī)劃有時仍然顯得那么高不可攀。眾所周知，動態(tài)規(guī)劃的效率是由兩部分決定的狀態(tài)數(shù)目及狀態(tài)轉(zhuǎn)移的效率。在以往大多數(shù)動態(tài)規(guī)劃的題目中，優(yōu)化狀態(tài)轉(zhuǎn)移效率的方法層出不窮，種類繁多，

11、此前，許多優(yōu)秀的選手已經(jīng)對此進行過了許多細致的研究，例如2001年毛子青的論文動態(tài)規(guī)劃算法的優(yōu)化技巧，2007年楊哲的論文凸完全單調(diào)性的一個加強與應(yīng)用等等。在不斷發(fā)掘優(yōu)化轉(zhuǎn)移效率的新方法的同時，關(guān)于狀態(tài)總數(shù)作為決定動態(tài)規(guī)劃效率的另一重要部分，這方面的優(yōu)化卻鮮有人問津。不可否認，狀態(tài)上的優(yōu)化不像轉(zhuǎn)移優(yōu)化那樣具有普遍性，有不少題目甚至是無法對其狀態(tài)的表示進行優(yōu)化的。但在某些特定的題目中，對狀態(tài)的表示作必要的改進可以收到良好的效果。以下實例就是描述當對狀態(tài)轉(zhuǎn)移進行優(yōu)化而無法解決問題時，我們應(yīng)該如何處理：例二、 banal tickets 題目來源題目描述:給定一個長度為的數(shù)字串，數(shù)字串中有的位置數(shù)字

12、是已知的，以表示；有的位置的數(shù)字是未知的，以表示。下圖給出了一個長度為4的數(shù)字串：當且僅當一個數(shù)字串滿足以下條件時，稱這個數(shù)字串interesting，否則為banal:要求求出所有長度為n的interesting串和banal串的個數(shù)。問題分析:首先，不難發(fā)現(xiàn)，求interesting串的個數(shù)和求banal串的個數(shù)這兩個問題是等價的，兩者為互補關(guān)系。這樣，就可以通過求其中的一個命題，來直接得到另一命題的解。而求interesting串的個數(shù)明顯比求banal串的個數(shù)簡單，因此只考慮求interesting串的個數(shù)的命題。用表示前位，乘積為的方案數(shù)。不難得出這樣的一組狀態(tài)轉(zhuǎn)移方程：邊界條件：當

13、時：當時：設(shè)表示對前半部分進行動態(tài)規(guī)劃所得出的結(jié)果，表示對后半部分進行動態(tài)規(guī)劃所得出的結(jié)果，則interesting串的個數(shù)為：其中，為最大的狀態(tài)數(shù)。似乎，此題已經(jīng)被很好地解決了?？墒亲屑毞治鱿聽顟B(tài)總數(shù)，不難發(fā)現(xiàn)，當每位都取時，總乘積最大，竟然達到了。這么大的狀態(tài)數(shù)根本存不下，更不要提在規(guī)定時間內(nèi)出解！需要進行優(yōu)化！初步分析:首先需要明確的是，這題中狀態(tài)在轉(zhuǎn)移時最多進行10次計算，因而，對轉(zhuǎn)移進行優(yōu)化并不能有效提高時間效率，我們迫切需要解決的是如何合理地改進狀態(tài)表示來減少狀態(tài)總量。明確了這點后，就要花心思對狀態(tài)表示進行優(yōu)化。稍加分析不難發(fā)現(xiàn)，一類數(shù)例如：這些數(shù)均不可能出現(xiàn)在狀態(tài)中，但是這些數(shù)有

14、什么共同點呢？質(zhì)數(shù)？不完全是。光是看這些數(shù)可能不能很明顯的發(fā)現(xiàn)一些規(guī)律，我們不如把可能出現(xiàn)在狀態(tài)中的數(shù)字列舉出來：以上這些數(shù)字有什么共同之處呢？除了以外，其他數(shù)字都能寫成的形式。仔細回想題目，狀態(tài)只可能是這10個數(shù)的乘積，而這幾個數(shù)只包含這4個質(zhì)因子！因此可以將狀態(tài)改為，表示前i位，乘積為的方案數(shù)，轉(zhuǎn)移方程只需稍加改動：邊界條件：當時：當時，當時，當時：因為無法用表示，所以用替代。其中，是一個四元組，表示將分解為時對應(yīng)的系數(shù)。采用這樣的方法，就明顯地減少了冗余狀態(tài)，優(yōu)化了狀態(tài)表示。接下來再分析狀態(tài)總數(shù)：最多為(考慮全部數(shù)字為8的情況)，最多為(全部為9)，最多為(全部為5)，最多為(全部為7)

15、。所以當時，狀態(tài)數(shù)目達到最大，為(使用滾動數(shù)組)，轉(zhuǎn)移為，總的最壞時間復(fù)雜度為，總的最大運算量為，不管時間還是空間都十分理想。但是這樣做真的就能AC此題了嗎？最多為18，總的字符串長度為36，因此總的數(shù)字個數(shù)為，需要使用高精度！假如選擇壓4位(10000進制)，那么高精度最大位數(shù)為9，則運算時間和所需空間均為原來的9倍，這樣時間勉強能承受，但是這題的空間限制為32MB，稍加計算即可知道不能滿足題目要求。而選擇大于5位的壓縮方法，則必須使用int64強制轉(zhuǎn)換運算類型(因為最后計算結(jié)果時需要用到高精度乘法)。由于int64的空間為longint的2倍，只有在壓縮9位的情況下才能使空間略微減少，仍然

16、超過了空間限制。進一步分析：我們的優(yōu)化已經(jīng)初見成效了，僅僅因為超了一點空間而選擇放棄實在太可惜。這樣的狀態(tài)真的沒有一點冗余了嗎？讓我們嘗試列舉50以內(nèi)的所有狀態(tài)，以期發(fā)現(xiàn)一些新的思路：1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，16，17，1819，20，21，22，23，24，25，26，27，28，29，30，31，32，33，34，35，3637，38，39，40，41，42，43，44，45，46，47，48，49，50上面的數(shù)列中，涂紅色的數(shù)字是有用的狀態(tài)，共33個。但是按照之前的狀態(tài)表示，2最多可能出現(xiàn)5個，3最多可能出現(xiàn)3個，5最多可能出現(xiàn)2個，7最多

17、可能出現(xiàn)2個，因此需要開的空間為，從這里可以看出，所用的狀態(tài)表示仍然包含大量冗余！例如，對于這個狀態(tài)就不可能出現(xiàn)，因為就已經(jīng)決定了n位數(shù)字全為8，所以其他質(zhì)數(shù)的個數(shù)不可能大于0。因此可以使用hash，只保留所有可能出現(xiàn)的狀態(tài)，就可以很好地減少了總狀態(tài)數(shù)。具體編程只需要使用一個BFS的過程，從這個狀態(tài)開始擴展，把所有有用的狀態(tài)篩選出來然后用hash建立一一對應(yīng)的映射關(guān)系即可。經(jīng)實踐發(fā)現(xiàn)，對于的極限狀態(tài)，使用hash可以將原來的69萬左右的狀態(tài)數(shù)減少到5萬以下。這樣，就能很好地解決此題了。小結(jié)：對于本題，很多人在對這題稍加分析，都會想到使用動態(tài)規(guī)劃來解決。但是當我們采用熟悉的動態(tài)規(guī)劃不能在題目要求

18、的時間和空間限制內(nèi)出解時，我們應(yīng)該怎么做呢？轉(zhuǎn)換模型？優(yōu)化轉(zhuǎn)移？這兩者都不失為很好的解題方法，但它們并非萬能靈丹，有時還是需要依靠優(yōu)化狀態(tài)總數(shù)來解決問題。如在解決這道問題時，轉(zhuǎn)換模型并不是那么容易，優(yōu)化轉(zhuǎn)移則事倍功半，最終還是要通過對狀態(tài)進行分析，改進狀態(tài)表示，發(fā)現(xiàn)并減少了冗余，才能滿足題目中空間和時間的要求。有時候，狀態(tài)中的冗余并不是很容易發(fā)覺，需要通過細心的分析，果斷的嘗試，以百折不撓的精神來解決問題。3、合理設(shè)計狀態(tài)對于許多人來說，學(xué)習(xí)信息學(xué)是從學(xué)習(xí)經(jīng)典算法開始的。了解及應(yīng)用了經(jīng)典算法之后，能幫助我們拓寬思維，舉一反三。但需要注意的是，信息學(xué)中的題目是千變?nèi)f化的，生搬硬套經(jīng)典算法有時候并

19、不能有效解決問題，這時就需要我們動腦筋思考，用創(chuàng)新的思維來改進已有的算法。學(xué)而不思則罔，思而不學(xué)則殆。我們不僅要學(xué)習(xí)某種算法本身，更要學(xué)習(xí)其中蘊涵著的思維方法。下面的例子就是講述如何在經(jīng)典算法遇到障礙時，合理地設(shè)計狀態(tài)，巧妙地解決障礙，并最終以較低的編程難度實現(xiàn)較高的程序效率。例三、 shoot your gun 題目來源 The 2007 ACM Asia Programming Contest Beijing Site, Problem G問題描述:定義rectangular polygon為一個僅包含90度或者270度內(nèi)角的簡單多邊形，并且其邊平行于坐標軸。已知，在一個大的rectang

20、ular polygon中有兩個小的rectangular polygon 和。對于每一個格點，可以往其左上，左下，右上，右下四個方向發(fā)射出一條射線(如下圖右)，射線在其軌跡路線上遇到障礙物，則遵循光路的鏡面反射規(guī)律進行反射。具體的反射規(guī)則（如下圖中）。圖下圖左描繪出了一個例子：題目要求求出從邊上的任意一個位置到達邊上的任意一個位置的路徑的最少反射次數(shù)，并且需要保證路徑在到達之前不能再次經(jīng)過。一個rectangular polygon最多包含50條邊，頂點坐標范圍在。題目分析:需要注意到，題目中G邊上的任意一點都可以發(fā)射出射線。如下圖，分別用紅線和藍線代表一條邊的兩個頂點所發(fā)出的射線，用綠線代

21、表邊上除頂點外任意一點發(fā)出的射線。很明顯，綠線所代表的非整點發(fā)射出的軌跡與紅線與藍線明顯不同，因此是不能忽略的，否則可能導(dǎo)致最優(yōu)解的缺失。由于一條邊上有無窮多個點，枚舉似乎是不可行。但是稍加分析后可以發(fā)現(xiàn)，圖中的綠線，無論往上或往下平移，只要不碰到紅線或藍線，其路線軌跡上反射的次數(shù)都是相同的，也就是說這些非整點發(fā)出的射線對于問題的解是等價的。我們選擇邊的中點作為這些點的代表。這樣，實際上只需要處理整點和中點，狀態(tài)是有限多個的。結(jié)論：對于同一條邊上的非整點，其路線軌跡上的反射次數(shù)是相同的。證明：不妨考慮向右下發(fā)射的情況，其他方向同理可證。如圖，以方格的左下角為原點建立平面直角坐標系：圖中從A點向

22、右下方向發(fā)射的射線與方格的邊交于B，C點向右下方向發(fā)射的射線與方格的邊交于D。更一般的非整點(x,y) 向右下方向發(fā)射的射線與方格的邊交于點(y,x)。同樣的，因此，對于所有在同一條邊上的非整點(x,y)，會且只會落在該方格的另一條邊上。即非整點只能到達非整點，且落點在同一條邊上。而落點所在的邊上的點又可以同理證明其發(fā)射的射線在到達另外一個方格的邊時，仍有如上性質(zhì)。因此同一條邊上的非整點發(fā)射出的射線軌跡上落點的個數(shù)是相同的，即反射次數(shù)相同。命題得證。由于這題中的點可以朝4個方向發(fā)射射線，簡單地把每個點作為一個狀態(tài)難以區(qū)分方向，因此可以采用經(jīng)典的拆點法，把一個點拆成4個點，分別代表左上，左下，右

23、上，右下四個方向，這樣就能合理地表示狀態(tài)了。在選定了狀態(tài)后，接下來是設(shè)計轉(zhuǎn)移。設(shè)表示這個格子并且射線發(fā)射方向為的狀態(tài) (分別表示左上，左下，右上，右下角的點和上，下，左，右邊的中點)?？梢詫⑺袪顟B(tài)構(gòu)成一張圖，相鄰的格子上的點之間連邊，問題就可以轉(zhuǎn)化為求集合到集合的最短路。由于和同級別(V為頂點集，E為邊集)，所以使用spfa或堆優(yōu)化的dijkstra效果會比較好。但是考慮到頂點坐標的范圍在之間，所以狀態(tài)總數(shù)最多可達，就算使用integer類型的話，也需要的空間，完全無法承受。進一步分析：之前的狀態(tài)表示有很明顯的冗余，例如這個格子的右下角和的左上角是同一個點，但是我們卻把這個點重復(fù)表示了好幾次

24、(和也會分別把這個點表示一次)。這樣的表示方法造成了很大的浪費！在我們排除了這些本質(zhì)相同的狀態(tài)后，最大狀態(tài)數(shù)約為，空間需要依然十分巨大(為原來的)，仍然不是很理想。要想徹底的優(yōu)化，還必須在狀態(tài)表示上多下些工夫。此前的構(gòu)圖方法并沒有用到題目中給的“線路軌跡遵循光的傳播路線”這個條件，這個條件能給我們一些有用的啟示嗎？大家知道，光是沿直線傳播的，只有在遇到障礙物時才會發(fā)生反射！例如下圖：圖中加粗的邊為射線的軌跡。在這個圖中，的路徑中，中間的邊上的轉(zhuǎn)移是固定的，只有在路徑遇到多邊形的邊界時才會發(fā)生不同的轉(zhuǎn)移，而我們卻仍多此一舉，把這些點納入狀態(tài)表示范圍，產(chǎn)生了大量的冗余狀態(tài)。由于路徑的變化是發(fā)生在多

25、邊形的邊上，因此只需要處理多邊形邊上的點即可。這樣狀態(tài)數(shù)將大大減少。我們來估算一下改進后最壞情況下的時空復(fù)雜度?？梢韵胂?，當圖形如下圖所示時，邊上的點數(shù)會達到最大，大約為（每一個凸出來的部分有上下兩個面，而構(gòu)成一個凸出部分（圖中灰色部分）需要4個點）。這樣，點數(shù)大概在10萬左右，邊數(shù)與點數(shù)同階，如果使用spfa算法，所需空間僅為，大約為，大約為之前的狀態(tài)總數(shù)的。而且，spfa算法的期望時間復(fù)雜度約為，這樣的狀態(tài)表示方法已經(jīng)能夠很好滿足題目空間及時間的限制。深入思考：使用spfa算法雖然已經(jīng)可以解決此題，但是考慮到spfa算法常數(shù)因子并不小，編程較為麻煩(構(gòu)圖部分)，有沒有更簡潔一些的方法呢？我

26、們對題目中“光路”的條件并未充分利用：光路是不會部分重疊的！要么完全不重疊，要么完全重疊。因此，根本不需要用spfa之類的最短路算法，只需要枚舉起點，然后每次遇到多邊形的邊的時候模擬折射，直到到達集合。然后從中挑選一條折射次數(shù)最少的光路即可。這樣做最多將每個點的4個方向枚舉一次，因此總的最大計算量為10萬*4。偽代碼如下：1枚舉起點(x,y)和方向d，若全部起點和方向都已枚舉過則退出該過程2對于當前點(x,y)，對所有邊v按從近到遠的順序進行枚舉，找到第一條可以發(fā)生折射的邊k3當前點(x,y)和方向d關(guān)于邊k發(fā)生反射，并得出射線與邊k的交點(x,y)和方向d4if 到達T集合更新反射的次數(shù)最優(yōu)

27、解并返回1if 到達G集合返回15替換當前點(x,y)為(x,y),替換當前方向d為d,并返回2這樣做之后，程序?qū)崿F(xiàn)起來十分簡單，運行效率也很高。至此，我們很好地解決了此題。小結(jié)：這題是今年ACM預(yù)選賽北京賽區(qū)的題目，在比賽現(xiàn)場并沒有人通過此題。但是，經(jīng)過仔細分析后發(fā)現(xiàn)，程序?qū)崿F(xiàn)的方法十分簡單，并沒有什么很復(fù)雜的證明及推理過程。但是為什么在當時沒人通過呢？可能大部分人在看到這題都把題目想復(fù)雜了，而我們對題目進行了仔細的分析，合理地設(shè)計了狀態(tài)，有效的去除了冗余，并用簡單的方法解決了此題。由此可以看到，對題目的進一步思考以及對狀態(tài)進行合理設(shè)計，可發(fā)揮出重要作用。三、 總結(jié)狀態(tài)優(yōu)化的方法是基于對狀態(tài)

28、的表示和對題目條件的深入分析而設(shè)計的。優(yōu)化狀態(tài)并不是只需要單純地使用hash就可以有效地減少狀態(tài)表示的空間，減少冗余。事實上，這里還有不少的優(yōu)化技巧。在第一題中，數(shù)學(xué)方法應(yīng)該是理論上的最優(yōu)解決辦法。但我們卻另辟蹊徑，通過對狀態(tài)的分析成功地使用了樸素的枚舉算法來解決。這也說明了合理地分析和設(shè)計狀態(tài)可以讓我們用一些簡單的做法來解決更困難的問題。在第二題中，我們很容易想到dp模型，但是規(guī)模十分巨大。我們通過合理分析題目條件，改進了狀態(tài)表示，并使用hash進一步優(yōu)化了冗余，這說明了狀態(tài)表示的重要性以及選擇好的狀態(tài)對解題所發(fā)揮出的巨大作用。在第三題中，常規(guī)的思路不能滿足題目的時間及空間限制。但是分析了狀

29、態(tài)的實質(zhì)后，我們把那些用處不大的狀態(tài)給排除了，極大地減少了狀態(tài)的數(shù)目，并很好地解決了問題。在最后的時候，又利用題目條件，巧妙地使用簡單的方法來代替原來略顯繁雜的方法，使原方法錦上添花。對狀態(tài)的合理設(shè)計與應(yīng)用能幫助我們以簡化繁、優(yōu)化算法和理清思路。但是要做到合理地設(shè)計狀態(tài)，合理地應(yīng)用題目條件，就需要我們嚴謹?shù)胤治鲱}目，對題目條件進行合理地組織與應(yīng)用，還要有一點點創(chuàng)造性的思維以及不斷累積的解題經(jīng)驗。當我們成功地解決題目后，要善于歸納總結(jié)解題思想，累積解題經(jīng)驗，才能更自信地走進信息學(xué)賽場。感謝感謝福州三中魏麗真老師的指導(dǎo)；感謝集訓(xùn)隊劉汝佳教練對論文修改提出的寶貴意見及幫助；感謝清華大學(xué)楊沐同學(xué)及上海

30、交通大學(xué)王航同學(xué)在論文修改中給予的幫助；感謝孫林春前輩在論文修改中給予的幫助。參考文獻算法藝術(shù)與信息學(xué)競賽附錄例一原題：Square RootTime Limit: 1.0 secondMemory Limit: 16 MBThe number x is called a square root of a modulo n (root(a,n) if x*x = a (mod n) Write the program to find the square root of number a by given modulo n. InputOne number K in the first lin

31、e is an amount of tests (K 100000). Each next line represents separate test, which contains two numbers a and n (a, n are natural, 1 a, n 32767, n is prime, a and n are relatively prime).OutputFor each input test the program must evaluate all possible values root(a,n) in the range (0,n1) and output

32、them in increasing order in one separate line using spaces. If there is no square root for current test, the program must print in separate line: No root.Sampleinputoutput54 173 72 714 3110007 200112 15No root3 413 185382 14629Problem Author: Michael Medvedev例二原題：Banal TicketsTime Limit: 5000MSMemor

33、y Limit: 32000KTotal Submissions: 693Accepted: 59DescriptionPeter is fond of number theory. That's why he is looking for interesting bus tickets. Ticket with the number of length 2N is called interesting if the product of the first N digits of its number is equal to the product of the last N dig

34、its. Other tickets are called banal. Peter has found a used ticket in his pocket. Unfortunately the ticket was punched, so Peter cannot recognize some digits. He wonders whether this ticket was an interesting one. Moreover he wants to know how many different interesting and banal tickets could be pu

35、nched to get this one. Help Peter to find answers to his questions. InputThe first line of the input file contains an integer N(1 <= N<=18). The next line contains a string representing the ticket number. If some digit is punched out it is denoted by "?" otherwise it is denoted by it

36、self.OutputOn the first line of the output file print the number of interesting tickets. On the second line print the number of banal tickets.Sample Input2 2?3Sample Output4 96 SourceNortheastern Europe 2003, Northern Subregion例三原題:Problem GShoot Your Gun!Input: gun.inThere are two rectangular polyg

37、ons (simple polygons with interior angles of only 90 or 270 degrees) G and T, insideanother rectangular polygon M. You can place a gun anywhere on the boundary of G, then shoot a bullet in one of fourdiagonal directions, and then touch the boundary of T. You may shoot across an edge of T, but touching only a corner isalso allowed. Your bullet is not allowed to touch G again (even touching a corner of G is not allowed), before touching T.The edges