信息學競賽輔導中“擠”的藝術

　　在信息學競賽輔導中，培養學生抓住題目本質、把題目做完全（得滿分）的能力是非常重要的。在高層次的競賽中，大部分已經達到一定層次的學生的水平實際上非常接近。比如在廣東省信息學奧賽總決賽中，對于每天的四個題目，高層次的學生（這類學生全省有30人左右）一般都能做其中三題。請注意，我這里用的是“能做”二字，一些題目很多學生能做，但卻不能得到該題的滿分，這里就是涉及到能否把能做的題目做完全的問題。而一旦誰能把能做的這幾題做完全，有兩題或兩題以上都得到滿分（或高分），誰就將脫穎而出，進入省前五名是順理成章的事。

　　例如有這樣一題競賽題：求N個字母的字符串組合：

　　如：用A、B、C三個字母組成長度為3的字符串，但每個字母都不允許重復使用，并且每個字母都不能擺在自己序號的位置上，則符合條件的只有兩個字符串：BCA、CAB。對于鍵盤輸入的n（n<=17），則意味著給出了A1、A2、……、An個不同的字母，用它們組成長度為N的字符串，但每個字母不允許重復使用，并且每個字母都不能擺在自己序號的位置上。問有多少個符合條件的字符串S。

　　幾乎所有學生一拿到就立刻用遞歸算法下手，對于輸入的n，把滿足條件的n個字符的字符串全部找出來，最后輸出總數，不用多少時間就得到程序，一運行，結果也對，于是絕大部分學生都認為大功告成了。熟不知測試數據中有n=17的情況，而限時竟然只有短短的5秒！絕大部分同學都因大數據超時而只得到該題的很少的幾分。顯然，對于這樣一題人人會做的題目，最終卻只有少數幾人能做得完全，能得滿分。事實上，此題有一公式，對于n=17的情況也不用1秒就能得出結果，找到這一公式才能把這題做得完全，雖然使用的仍是遞歸算法，但速度卻要快出無數倍，因為對于輸入的n，直接計算字符串的總數而無需得到每一個字符串，耗時自然大大減少了。給出公式如下：

　　0 　　　　　(x=1)

　　f(x)= x*f(x-1)+1 (x>2,x mod 2=0)

　　x*f(x-1)-1 (x>2,x mod 2=1)

　　程序自然不必多說了。

　　所以，一個題目會做卻并不等于你能把這題做全，能把這題的分得全，這就是真高手與半高手的區別。那么，怎樣才能在平常的訓練中培養學生的這種把題目做全的能力呢？下面筆者想以第四屆全國青少年信息學（計算機）奧林匹克分區聯賽復賽高中組第二題為例，談談筆者在奧賽訓練中采用的“擠”的訓練方法。

　　題目如下：

　　設有N個正整數(N<=20)，將它們聯成一排，組成一個最大的多位整數。

　　例如：N=3時，3個整數13、312、343聯成的最大整數為：34331213；

　　又如：N=4時，4個整數7，13，4，246聯成的最大整數為：7424613；

　　輸入： N

　　N個數

　　……

　　輸出：聯成的多位數。

　　測試數據如下：

　　序號

　　輸入

　　輸出

　　分值

　　1

　　3

　　121 21 3

　　321121

　　5

　　2

　　4

　　13 24 75 42

　　75422413

　　10