2009noip提高组复赛题解

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； 若s>t則r=s；

由最小公倍數亦可得到（設u、v分別為b0、b1含p的個數）： 若u=v則r<=v； 若u

如此便得到了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) 題目描述：

已知一數獨題目及每格的得分倍數，總得分為倍數乘這個格裡數的積，求出最高的得分。 解題思路：

數獨的解法就是搜索。所以本題就是對搜索的優化。 （去年我直接深搜得四十分）

因此可見，本題得一些分其實是相對容易的。當把這些分得來先。 優化一：

搜索優化一般是剪枝，但這題不太容易得出剪枝的方法。

一個不錯的優化是改變一下搜索順序。因為有些格可填的數字少，先搜這些格會使搜索樹小很多。但是，如果每一步搜索都要找一找下一個格子的話就太費時間了，效率甚至會不如樸素的搜索。因此不能這樣來做。

所以，只能預處理一下順序。我們可以假設一個理想化的情況：假設一個格子填入數字後，必然對同一行、同一列和同一大格中的空格造成影響。也就是說，不能做到精確的計算。但總能估計一個大概的「受影響程度」。

因此就可以讓每步填好的格子對其週圍的格子「影響」一次（即增加它們的「受影響度」），然後選取下一步的格子。如此重複，直至選取完所有的空格。 按照這個順序來搜，大約可得七十五分。 優化二：

搜索現在還慢在每一步的判斷上。這裡也是可以優化的。

一般的判斷是看這一格子所在的行、列和大格共二十個格子裡的數是否有與該格的數相同的。如果能預先知道該行、該列或該大格已經填入了哪些數字，就可以免掉很多時間。

仿照八皇后問題的優化算法。可以建立三個bool數組：plr[i][k]、plc[i][k]及plg[i][j][k]，分別表示第i行、第i列及從向第i個橫向第j個大格內數k有未被填過。這樣搜索衹要看該數組判斷就可以了。注意遞迴和回溯時要更新這幾個數組的狀態。

這樣的話應該就可以AC了。（最后一個數據我做到1.95秒）

另外，效法八皇后問題，這題也可以用位運算來解決，非常快。二十組數據每組都能一秒內出解。 建議時間： 40－60分鐘

簡單數據的分很易得，樸素深搜一定要先寫出來。優化不是很容易，盡量做。最好是多優化一下前面幾道題的程序，它們的優化比這道題容易一些，仍有時間的話再來考慮這道題的優化。 總結：

這套題得高分不太容易，但只要把程序都寫正確了，稍加些優化就能得大約一半的分（我去年得一百九十分）。這也是很高的分數。因此，「正確」是關鍵所在。這套題不必要冒太大險的。

程序範例： spy.cpp

#include #include #include using namespace std; ifstream fin(\ofstream fout(\string s1,s2,s3; char d1[26],d2[26]; int main(){ fin>>s1>>s2>>s3;

for(int i=0;i

fout<<\ return 0; }

}else if(d1[s1[i]-'A']!=s2[i]){ fout<<\

本文来源：https://www.bwwdw.com/article/3f62.html