1．能量項鍊(energy.pas/c/cpp)
【問題描述】
在mars星球上，每個mars人都隨身佩帶著一串能量項鍊。在項鍊上有n顆能量珠。能量珠是一顆有頭標記與尾標記的珠子，這些標記對應著某個正整數。
並且，對於相鄰的兩顆珠子，前一顆珠子的尾標記一定等於後一顆珠子的頭標記。因為只有這樣，通過吸盤（吸盤是mars人吸收能量的一種器官）的作用，這兩顆珠子才能聚合成一顆珠子，同時釋放出可以被吸盤吸收的能量。如果前一顆能量珠的頭標記為m，尾標記為r，後一顆能量珠的頭標記為r，尾標記為n，則聚合後釋放的能量為（mars單位），新產生的珠子的頭標記為m，尾標記為n。
需要時，mars人就用吸盤夾住相鄰的兩顆珠子，通過聚合得到能量，直到項鍊上只剩下一顆珠子為止。顯然，不同的聚合順序得到的總能量是不同的，請你設計乙個聚合順序，使一串項鍊釋放出的總能量最大。
例如：設n=4，4顆珠子的頭標記與尾標記依次為(2，3) (3，5) (5，10) (10，2)。我們用記號⊕表示兩顆珠子的聚合操作，(j⊕k)表示第j，k兩顆珠子聚合後所釋放的能量。
則第4、1兩顆珠子聚合後釋放的能量為：
(4⊕1)=10*2*3=60。
這一串項鍊可以得到最優值的乙個聚合順序所釋放的總能量為
((4⊕1)⊕2)⊕3）=10*2*3+10*3*5+10*5*10=710。
【演算法說明】
這是根據矩陣連乘問題改編的，是乙個典型的動態規劃問題。原線性結構改為環狀結構，陣列擴大一倍（不使用求餘方法），比原題略難一些。
矩陣連乘問題是這樣描述的：給定n個矩陣 ，每個相鄰的矩陣都是可乘的，即前乙個矩陣的列數等於後乙個矩陣的行數。考察這n個矩陣的連乘積，由於矩陣乘法滿足結合律，所以計算矩陣的連乘可以有許多不同的計算次序。
這種計算次序可以用加括號的方式來確定。以5個矩陣為例，下面一些結合方式都是正確的：
乙個m行n列的矩陣與乙個n行r列的矩陣相乘，所需要的小乘法（普通的數乘）的次數為。對於n個矩陣連乘，不同的結合順序所需要的總的小乘法次數一般是不同的。於是，矩陣連乘問題可表述為：
對於給定了行數與列數的n個矩陣，如果它們是可乘的，求一種結合順序，使總的小乘法次數最少。
在我們的問題中，將求最小改為求最大，如果對所有可能結合的方式進行全面搜尋，可以證明，對於n個矩陣連乘，不同的結合順序大約有o(4n)種，當n較大時，顯然是行不通的。通常採用動態規劃求解。
考慮連乘中的一段：， 設計算a[i:j]，1≤i≤j≤n，所需要的最多的乘次數為m[i,j]，則原問題的最優值就是m[1,n]。
計算a[i,j]的最後一步總是兩個矩陣相乘，即，因此，可得下面的動態轉移方程：
例：設n=4, p0=35, p1=40, p2=20, p3=10, p4=15
即：a1=( )35*40, a2=( )40*20, a3=( )20*10, a4=( )10*15
(1) m12=35*40*20=28000, m23=8000, m34=3000
(2) m13=max =35000
m24=max =15000
(3) m14=max =41500
m14就是所求的結果。
函式「void init_neck()」的功能是輸入已知資料，再將陣列p擴大一倍。函式「void matrixch(int p,int n)」是矩陣連乘的核心演算法，注意如果使用int型數，3個下標值相乘時可能會溢位，要做型別轉換處理。演算法參看附件。
函式「void out_neck(int n)」輸出最優值，由於是環狀的，還要求一次最大值。此題是最容易的一道題。
2．金明的預算方案(budget.pas/c/cpp)
【問題描述】
金明今天很開心，家裡購置的新房就要領鑰匙了，新房裡有一間金明自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：「你的房間需要購買哪些物品，怎麼布置，你說了算，只要不超過n元錢就行」。
今天一早。金明就開始做預算了，他把想買的物品分為兩類：主件與附件，附件是從屬於某個主件的，下表就是一些主件與附件的例子：
如果要買歸類為附件的物品，必須先買該附件所屬的主件。每個主件可以有0個、1個或2個附件。附件不再有從屬於自己的附件。
金明想買的東西很多，肯定會超過媽媽限定的n元。於是，他把每件物品規定了乙個重要度，分為5等：用整數1—5表示，第5等最重要。
他還從網際網路上查到了每件物品的**（都是10元的整數倍）。他希望在不超過n元（可以等於n元）的前提下，使每件物品的**與重要度的乘積的總和最大。
設第j件物品的**為v[j]，重要度為w[j]，共選中了k件物品，編號依次為j1 ，j2，……，jk，，則所求的總和為：
v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。（其中*為乘號）
請你幫助金明設計乙個滿足要求的購物單。
【演算法說明】
此題是在01揹包問題的基礎上改編的，但比普及組類似的一道題要難得多。一是資料量（物品個數）加大了，由25增到60。二是設定了「附件」，使問題難度加大，因此建議使用動態規劃策略解題，而一般的遞迴回溯對較大的m會超時。
（當然還有其他一些可行的甚至更好的方法）。
01揹包問題的動態規劃演算法可在許多書中找到。總錢數（<32000）由於是10的整數倍，可以在[0，3200]中搜尋，最後輸出時再乘以10。
由於附件的引用，每個物品的一種狀態可能變為4種狀態（只用主件，主件+附件1，主件+附件2，主件+附件1+附件2）。這4種狀態是互相排斥的。因此在構建動態規劃的二維表時，相應的行最多要處理4次（用迴圈for(j=1;j<=4;j++)實現）。
在cpp程式中，函式「void init_happy()」的功能是初始化處理：讀入已知資料，並計算陣列tmp,存放每件物品對結果的貢獻值，這樣處理可減少許多重複的乘法。函式「void out_happy()」的功能是輸出結果。
函式「void oper1(int k)」是遞迴回溯的核心部分。部分變數的含義如下：value：
本次計算得到的目標值， best到目前為止，最好的目標值。allw：到目前為止已選定的物品的總價值。
nlimit：可用的錢數的最大值。
主要變數說明：
v[n][3200]=;動態規劃陣列。最優貢獻量（即**與重要度的乘積）核心陣列
a[n][4]=;已知資料，[0]：編號，[1]：**，[2]：重要度 [3]：主件
b[n][5]=;經處理後的陣列，存放**資訊
[0]：編號，[1]：單個主件，[2]：主件加附件1，[3]：主件加附件2，[4]：主件加2個附件
v2[n][5]=;經處理後的陣列，存放貢獻量資訊
nlimit：總錢數，nlimit2：總錢數/10，m:總物品數，m2:主件總數
函式「void init_budg()「的功能包括：輸入已知資料，計算陣列b[n][5],v2[n][5]及nlimit2。
函式「void out_budg() 「的功能是輸出計算結果。
函式「void oper1(int k)」的作用是：前k-1件已處理完，現考慮處理前k件。是程式的核心部分。
基本公式：設第t件物品的第j種狀態的**為b[t][j],貢獻量為v2[t][j],
則：對於i=1,2,…,b[t][j]-1,v[k][i]=v[k-1][i] （不使用第t件物品）。
對於i=b[t][j]，…,nlimit2,
v[k][i]=
max 。
3．作業排程方案(jsp.pas/c/cpp)
【問題描述】
我們現在要利用m臺機器加工n個工件，每個工件都有m道工序，每道工序都在不同的指定的機器上完成。每個工件的每道工序都有指定的加工時間。
每個工件的每個工序稱為乙個操作，我們用記號j-k表示乙個操作，其中j為1到n中的某個數字，為工件號；k為1到m中的某個數字，為工序號，例如2-4表示第2個工件第4道工序的這個操作。在本題中，我們還給定對於各操作的乙個安排順序。
例如，當n=3，m=2時，「1-1，1-2，2-1，3-1，3-2，2-2」就是乙個給定的安排順序，即先安排第1個工件的第1個工序，再安排第1個工件的第2個工序，然後再安排第2個工件的第1個工序，等等。
一方面，每個操作的安排都要滿足以下的兩個約束條件。
(1) 對同乙個工件，每道工序必須在它前面的工序完成後才能開始；
(2) 同一時刻每一台機器至多只能加工乙個工件。
另一方面，在安排後面的操作時，不能改動前面已安排的操作的工作狀態。
由於同一工件都是按工序的順序安排的，因此，只按原順序給出工件號，仍可得到同樣的安排順序，於是，在輸入資料中，我們將這個安排順序簡寫為「1 1 2 3 3 2」。
還要注意，「安排順序」只要求按照給定的順序安排每個操作。不一定是各機器上的實際操作順序。在具體實施時，有可能排在後面的某個操作比前面的某個操作先完成。
例如，取n=3,m=2，已知資料如下：
則對於安排順序「1 1 2 3 3 2」，下圖中的兩個實施方案都是正確的。但所需要的總時間分別是10與12。
當乙個操作插入到某台機器的某個空檔時（機器上最後的尚未安排操作的部分也可以看作乙個空檔），可以靠前插入，也可以靠後或居中插入。為了使問題簡單一些，我們約定：在保證約束條件（1）（2）的條件下，盡量靠前插入。
並且，我們還約定，如果有多個空檔可以插入，就在保證約束條件（1）（2）的條件下，插入到最前面的乙個空檔。於是，在這些約定下，上例中的方案一是正確的，而方案二是不正確的。
NOIP2019複賽普及
第十二屆全國青少年資訊學奧林匹克 聯賽複賽試題 noip2006普及組 競賽時間 2006年11月18日下午1 30 4 30 關於競賽中不同語言使用限制的說明 一 關於使用pascal語言與編譯結果的說明 1 對於pascal語言的程式，當使用ide和fpc編譯結果不一致時，以fpc的編譯結果為準...
Pascal衝刺NOIP2019模擬試題與解析 六
衝刺noip2009模擬試題與解析 六 普及組 題目說明 1 檔名 程式名和輸入輸出檔名 必須使用小寫 2 c c 中函式main 0的返回值型別必須是int，程式正常結束時的返回值必須是0 3 每到題目都必須建立資料夾。1 上學路線 題目描述 你所在城市的街道好像乙個棋盤，有a條南北方向的街道和b...
NOIP2019山東賽區初賽預備通知
預備通知 各市科協 教育局 處 計算機學會 聯賽有關單位 學校 全國青少年資訊學奧林匹克聯賽 簡稱noip 是經教育部批准 中國科協主管，由中國計算機學會主辦的一項全國青少年學科競賽活動，通過競賽相互交流，共同提高和從中培養 選拔資訊學優秀後備人才。到目前為止，還沒有收到中國計算計算機學會 ccf ...