CCF青少年計算機程式設計評級标準（五）

五級标準

1.1  定義

        掌握簡單資料結構知識，并結合已學算法和數學知識編寫程式，解決問題。

1.2  知識要求

        1.      指針類型。

        2.      一般線性表，隊列，堆棧，二叉樹的存儲和周遊。

        3.      排列與組合，高精度數值處理。

        4.      二分算法，快速排序，深度優先搜尋，寬度優先搜尋，簡單動态規劃。

        5.      圓排列，可重集排列，鴿籠原理，素因數分解，幂函數，指數函數，對數函數，三角函數，模運算，不等式基礎知識。

1.3  能力要求

        1.      能運用常用算法和簡單資料結構解決實際問題。

        2.      能從算法本質出發，分析相關算法之間的本質聯系。

        3.      具備初步的數學模組化能力。

1.4  評價方法

        1.      與NOIP普及組複賽相銜接。采用上機程式設計考核方式，共4個試題，考核時間：3小時。

        2.      在NOIP普及組複賽中成績列全國前40%。

1.5  題例

試題名：擺花

檔案名：flower

試題描述：

         小明的花店新開張，為了吸引顧客，他想在花店的門口擺上一排花，共m盆。通過調查顧客的喜好，小明列出了顧客最喜歡的n種花，從1到n标号。為了在門口展出更多種花，規定第i種花不能超過ai盆，擺花時同一種花放在一起，且不同種類的花需按标号從小到大的順序依次擺列。

         試程式設計計算，一共有多少種不同的擺花方案。

輸入資料：

         輸入檔案flower.in，共2行。

         第一行包含兩個正整數n和m，中間用一個空格隔開。

         第二行有n個整數，每兩個整數之間用一個空格隔開，依次表示a1、a2、…….an。

輸出資料：

         輸出檔案名為flower.out。

輸出隻有一行，一個整數，表示有多少種方案。注意：因為方案數可能很多，請輸出方案數對1000007取模的結果。

輸入輸出樣例：

         flower.in                              flower.out

         2 4                                         2

         3 2

         樣例說明：有2種擺花的方案，分别是（1,1,1,2），（1,1,2,2）。括号裡的1和2表示兩種花，比如第一個方案是前三個位置擺第一種花，第四個位置擺第二種花。

資料範圍：

         對于20%資料，有0<n<=8，0<m<=8，0<ai<=8；

         對于50%資料，有0<n<=20，0<m<=20，0<ai<=20；

         對于100%資料，有0<n<=100，0<m<=100，0<ai<=100。

參考題解：

         本題可采用簡單動态規劃。設f[i,j]表示前i種花放在前j個花盆裡的最大方案數，那麼：

         f[i,j]=sum(f[i-1,j-x])  (0<=x<=min(a[i],j))

         狀态轉移方程的含義為：前j個花盆裡，第i種花最少放0個，最多放min{a[i],j}個。

         其中min{a[i],j}表示第i種花的數目和花盆的數目中較少的那一個。

         邊界條件：f[1,j]=1 (i<=a[1])。