2009noip提高组复赛题解要点分析.doc

NOIP2009提高組複賽試題解題報告 NOIP2009提高組複賽試題解題報告 一、潛伏者(spy) 問題描述： 　　給出密文及對應明文，求字母的對應關係並破譯密文。 解題思路： 　　水題。只需把字符串掃描一遍，邊掃邊增加對應關係。並判斷既有之對應關係是否正確。最後判斷是否每一個字母都有其對應字母。 　　需要注意不僅要判斷是否每一個密文字母都存在惟一對應的明文字母，還要判斷是否每一個明文字母都存在惟一對應的密文字母。（去年我沒判斷這個，所以測試點三WA了，九十分） 　　最後若失敗輸出“Failed”，否則按照對應字母輸出即可。 建議時間： 　　15－25分鐘 　　題很簡單，就是要考慮全面一些，第一題的分不能錯過。盡量多調試一下。 二、Hankson的趣味題 題目描述： 　　已知x和a0的最大公約數是a1，x和b0的最小公倍數是b1。求x的解的個數。 解題思路： 算法一： 　　最簡單的方式是枚舉，x從a1取到b1，然後判斷x是否為解。 　　這種方法能得到一少半分數，因為數很大。 優化： 　　由於ｘ必是a1的倍數，亦必是b1的約數，所以枚舉時可以枚舉a1的倍數，判斷是否為b1的約數，然後再輾轉相除驗證解。另外b1/2至(b1-1)之間沒必要枚舉，可去除這段區間。 　　（我去年這樣得到了五十分） 算法二： 　　考慮素因數的性質：若gcd(x,a0)=a1，x、a0和a1含有某一素因數p的個數分別為r、s和t，則必有t=min(r,s)。故x含有p的個數滿足： 　　　　若s=t則r=s； 　　　　若st則r=s； 　　由最小公倍數亦可得到（設u、v分別為b0、b1含p的個數）： 　　　　若u=v則r=v； 　　　　若uv則r=v； 　　如此便得到了r的取值範圍，進而得到r可取值的個數。 　　這樣的話，就可以將a0和b1分解質因數，並對每個質因數都計算一次r的解數。依乘法原理，將它們相乘即可得到答案。 　　這種方法可得到80分左右。 　　為了減少分解時的冗餘判斷，加快分解的速度，可以預處理出五萬以內的素數表（約五千多個）。這樣就可以拿到滿分。 建議時間： 　　35－45分鐘 　　這道題考察到數論知識，對數學和編程都是一大考驗。先寫個暴力再說，可以先做做後面的題。不要浪費太多時間，如果對高級算法把握不大就寫簡單算法騙分吧。得分最重要。 三、最優貿易(trade) 題目描述： 　　給定一個有向圖，每個點都有一個價格。要求找一條從1到n 的路，路上有至多一次買進和賣出，使得所獲利潤最大。 解題思路： 　　（我去年不會這道題，輸出0騙了十分） 　　可以有哪些信誉好的足球投注网站路徑，找最低的買價和最高賣價（先買後賣）。效率不高。 　　考慮到買和賣具有階段性，可以用動態規劃。 　　設f(i)為從1到i的路徑中的最低買價，g(i)為從i到n的路徑中的最高賣價。只要求出f、g，那麼最大的(f(i)-g(i))或0就是答案。 　　那麼如何求f和g呢？ 　　明顯在存在有向邊i-j時有f(i)=min(f(i),f(j),price[j])，g(i)則反過來，因此可以通過鬆弛操作來實現。分別以正、反兩個方向做一次SPFA（相當於優化了的寬搜，不是標準的最短路，故本題不可用dijkstra+heap），找到最大的(f(i)-g(i))即可。 　　另外標準的解法是將強連通分量縮為一點。再利用拓撲排序逐層求f、g，代碼量稍大。 建議時間： 　　40－50分鐘 　　最好先寫個簡單程式。求f、g的方法是本題關鍵。由於後面的數獨比較容易騙分，所以可以先把第四題騙了分，再來仔細做這個題。 四、靶形數獨(sudoku) 題目描述： 　　已知一數獨題目及每格的得分倍數，總得分為倍數乘這個格裡數的積，求出最高的得分。 解題思路： 　　數獨的解法就是有哪些信誉好的足球投注网站。所以本題就是對有哪些信誉好的足球投注网站的優化。 　　（去年我直接深搜得四十分） 　　因此可見，本題得一些分其實是相對容易的。當把這些分得來先。 優化一： 　　有哪些信誉好的足球投注网站優化一般是剪枝，但這題不太容易得出剪枝的方法。 　　一個不錯的優化是改變一下有哪些信誉好的足球投注网站順序。因為有些格可填的數字少，先搜這些格會使有哪些信誉好的足球投注网站樹小很多。但是，如果每一步有哪些信誉好的足球投注网站都要找一找下一個格子的話就太費時間了，效率甚至會不如樸素的有哪些信誉好的足球投注网站。因此不能這樣來做。 　　所以，只能預處理一下順序。我們可以假設一個理想化的情況：假設一個格子填入數字後，必然對同一行、同一列和同一大格中的空格造成影響。也就是說，不能做到精確的計算。但總能估計一個大概的「受影響程度」。 　　因此就可以讓每步填好的格子對其週圍的格子「影響」一次（即增加它們的「受影響度」），然後選取下一步的格子。如此重複，直至選取完所有的空格。 　　按照這個順序來搜，大約可得七十五分。 優化二： 　　有哪些信誉好的足球投注网站現在還慢在每一步的判斷上。這裡也是可以優化的。 　　一般的判斷是看這一