?這是第二次模擬測(cè)試的解題報(bào)告
本次題目出自O(shè)IBH模擬賽

題目如下：
===================================================================================================================
飲食問(wèn)題
（eatpuz.pas/c/cpp/in/out）
時(shí)限:1 sec | 內(nèi)存: 64 MB

背景
???? 平平正在減肥，所以要控制他的飲食。并且要求她及時(shí)去公園里面散步。
題目描述
平平正在減肥，所以她規(guī)定每天不能吃超過(guò) C (10 <= C <= 35,000)卡路里的食物。農(nóng)民 John 在戲弄她，在她面前放了B (1 <= B <= 21) 捅食物。每桶內(nèi)都有某個(gè)單位卡路里(范圍：1..35,000)的食物(不一定相同)。平平?jīng)]有自控能力，一旦她開(kāi)始吃一個(gè)桶中的食物，她就一定把這桶食物全部吃完。
平平對(duì)于組合數(shù)學(xué)不大在行。請(qǐng)確定一個(gè)最優(yōu)組合，使得可以得到最多的卡路里，并且總量不超過(guò)C。
例如，總量上限是40卡路里， 6 桶食物分別含有7, 13, 17, 19, 29, 和 31卡路里的食物。平平可以吃7 + 31 = 38卡路里，但是可以獲取得更多： 7 + 13 + 19 = 39卡路里。沒(méi)有更好的組合了。

輸入
共兩行。
第一行，兩個(gè)用空格分開(kāi)的整數(shù)： C 和 B
第二行，B個(gè)用空格分開(kāi)的整數(shù)，分別表示每桶中食物所含的卡路里。

輸出
共一行，一個(gè)整數(shù)，表示平平能獲得的最大卡路里，使她不違反減肥的規(guī)則。

輸入樣例
40 6
7 13 17 19 29 31

[樣例輸出]
39

三個(gè)袋子
（bags.pas/c/cpp/in/out）
時(shí)限:1 sec | 內(nèi)存: 64 MB
背景
??? 平平在公園里游玩時(shí)撿到了很多小球，而且每個(gè)球都不一樣。平平找遍了全身只發(fā)現(xiàn)了3個(gè)一模一樣的袋子。他打算把這些小球都裝進(jìn)袋子里（袋子可以為空）。他想知道他總共有多少種放法。

題目描述
??? 將N個(gè)不同的球放到3個(gè)相同的袋子里，求放球的方案總數(shù)M。
??? 結(jié)果可能很大，我們僅要求輸出M mod K的結(jié)果。
??? 現(xiàn)在，平平已經(jīng)統(tǒng)計(jì)出了N<=10的所有情況。見(jiàn)下表：
N?1?2?3?4?5?6?7?8?9?10
M?1?2?5?14?41?122?365?1094?3281?9842

輸入
兩個(gè)整數(shù)N,K，N表示球的個(gè)數(shù)。

輸出
輸出僅包括一行，一個(gè)整數(shù)M mod K 。

輸入樣例 ( bags.in )
11 10000

輸出樣例( bags.out )
9525

數(shù)據(jù)規(guī)模
對(duì)于 40%數(shù)據(jù),10<=N<=10,000
對(duì)于100%數(shù)據(jù),10<=N<=1,000,000,000
對(duì)于 100%數(shù)據(jù)，K<=100,000

智捅馬蜂窩
（clever.pas/c/cpp/in/out）
時(shí)限:1 sec | 內(nèi)存: 64 MB
背景
??? 為了統(tǒng)計(jì)小球的方案數(shù)，平平已經(jīng)累壞了。于是，他摘掉了他那800度的眼鏡，躺在樹(shù)下休息。
??? 后來(lái)，平平發(fā)現(xiàn)樹(shù)上有一個(gè)特別不一樣的水果，又累又餓的平平打算去把它摘下來(lái)。
題目描述
??? 現(xiàn)在，將大樹(shù)以一個(gè)N個(gè)節(jié)點(diǎn)的無(wú)向圖的形式給出，每個(gè)節(jié)點(diǎn)用坐標(biāo)（Xi，Yi）來(lái)表示表示，平平要從第一個(gè)點(diǎn)爬到第N個(gè)點(diǎn)，除了從一個(gè)節(jié)點(diǎn)爬向另一個(gè)相鄰的節(jié)點(diǎn)以外，他還有一種移動(dòng)方法，就是從一個(gè)節(jié)點(diǎn)跳下，到達(dá)正下方的某個(gè)節(jié)點(diǎn)（之間可隔著若干個(gè)點(diǎn)和邊），即當(dāng)Xj=Xi and Yi<Yj 時(shí)，平平就可以從j節(jié)點(diǎn)下落到i節(jié)點(diǎn)，他下落所用時(shí)間滿(mǎn)足自由落體公式，t=sqrt((Yj-Yi)*2/g) （注意：g取10）。如果出現(xiàn)兩線相交的情況，我們不認(rèn)為它們是相通的。

輸入
兩個(gè)整數(shù)N,V，N表示節(jié)點(diǎn)個(gè)數(shù)，V表示平平爬樹(shù)的速度。
接下來(lái)N行，每行包含3個(gè)整數(shù)X,Y,F，X,Y是這個(gè)點(diǎn)的坐標(biāo)，F(xiàn)是他的父節(jié)點(diǎn)（F一定小于這個(gè)點(diǎn)的標(biāo)號(hào)，第一行的F為0）。
注意：兩節(jié)點(diǎn)間距離按歐幾里德距離計(jì)算 dis = sqrt( ( x1 – x2 ) 2+ ( y1 – y2 )2 )

輸出
輸出僅包括一行，從1到N所用的最少所需時(shí)間T，保留兩位小數(shù)。

輸入樣例 ( clever.in )
9 1
5 0 0
5 5 1
6 5 2
7 6 2
6 9 2
3 6 2
4 5 2
3 2 7
7 2 3

輸出樣例 ( clever.out )
8.13

數(shù)據(jù)規(guī)模
對(duì)于100%數(shù)據(jù),1<=N<=100,1<=V<=10,0<=X,Y<=100.
建議使用extended(pas)或double（c and c++）計(jì)算，我們對(duì)于精度造成的誤差將不予重測(cè)。

過(guò)河
（river.pas/c/cpp/in/out）
時(shí)限:1 sec | 內(nèi)存: 64 MB
背景
??? 經(jīng)過(guò)一番努力，平平終于摘到了水果，拿近一看才發(fā)現(xiàn)是馬蜂窩。
??? 平平從樹(shù)上掉了下來(lái)，沒(méi)命的跑啊跑啊……
??? 后來(lái)，他發(fā)現(xiàn)前方有一條河。現(xiàn)在他用電話(huà)求助于你，希望你在他跑到之前鋪好過(guò)河的路，讓他順利過(guò)河。

題目描述
??? 已知河的長(zhǎng)度為L(zhǎng)，現(xiàn)在我們有M個(gè)石子，我們可以把一個(gè)石子鋪在河上的一個(gè)點(diǎn)，讓平平踩著這些石頭過(guò)河。河上已經(jīng)有N個(gè)石子，而且已知平平每步跨出的距離為S到T之間的整數(shù)（ S <= T ），起點(diǎn)是0點(diǎn)，河為1到L，只要平平最后能跳過(guò)L（必須大于L）就算平平順利過(guò)河。
??? 如果平平能夠過(guò)河，請(qǐng)輸出最少步數(shù)，否則輸出最遠(yuǎn)到達(dá)的距離，以便我們及時(shí)去救起平平。

輸入
第一行有五個(gè)整數(shù)L,N,M,S,T ，L是河的寬度，N表示河里原來(lái)就有N個(gè)石頭，M表示我們手上擁有的石頭，S,T表示平平的一步最小的跨度和最大跨度。接下來(lái)N行有一個(gè)值表示在河里的石頭的位置（從小到大給出）。

輸出
輸出僅包括一行，如果能夠過(guò)河，輸出最少步數(shù)，否則輸出平平能夠到達(dá)的最遠(yuǎn)距離。

輸入樣例 ( river.in )
樣例1：
8 2 2 2 3
2
3

樣例2：
10 1 1 1 2
2

輸出樣例 ( river.out )
樣例1：
3

樣例2：
4

數(shù)據(jù)規(guī)模
對(duì)于40%數(shù)據(jù),1<=M<=L<=1000 , 1<=S<=T<=10 ;
對(duì)于100%數(shù)據(jù),1<=M<=L<=100000;
對(duì)于100%數(shù)據(jù),1<=S<=T<=100,1<=N<=100.

后記
??? 可憐的平平還是沒(méi)有逃過(guò)被馬蜂蟄的命運(yùn)。大老板以最快的速度把平平送到了醫(yī)院。
平平的故事就此告一段落。現(xiàn)在平平小朋友正躺在家里好好休息，準(zhǔn)備沖刺2007年的NOIP……
================================================================================================================

解題報(bào)告：

第一題：
??????????? 簡(jiǎn)單的01背包，就算使用回溯法枚舉所有可能情況也能過(guò)（經(jīng)測(cè)試），數(shù)據(jù)很弱。。。。。。。
????????????本人用DP方法，求出了所有可能得到的卡路里值
????????????附上程序：

?
第二題：
????????????無(wú)奈的數(shù)學(xué)題，快速冪，或者干脆用矩陣乘法加速，看著辦吧

第三題：
????????????簡(jiǎn)單的單元最短路，注意如果可能掉下來(lái)而不用爬的方法，更新兩點(diǎn)間的通路時(shí)間，其他沒(méi)什么了。
??????????? Dijkstra算法，代碼：?

第四題：
????????????讓人崩潰的DP題目，不過(guò)由于數(shù)據(jù)比較弱，搜索應(yīng)該也是可以過(guò)的（不過(guò)本人不會(huì)）。

????????????首先我們應(yīng)該明確題目中的幾個(gè)重要部分（或者說(shuō)是細(xì)節(jié)步驟，要不然就是過(guò)河時(shí)的一般規(guī)律）：
????????????1、如果可能到達(dá)河岸對(duì)面，那么，手中的石頭全部使用完肯定對(duì)應(yīng)至少一個(gè)最優(yōu)解（為什么？自己想，簡(jiǎn)單的很）；
????????????2、對(duì)于兩個(gè)石頭之間，是否存在可能到達(dá)方式的判斷條件：len/s*t>=len（len為兩石頭間的距離，下同）? (具體證明，可以形象的畫(huà)一畫(huà)）；
????????????3、如果兩個(gè)點(diǎn)（或者說(shuō)石頭），如果之間有可能的方法到達(dá)（即滿(mǎn)足2中的判斷條件），那么，從一個(gè)石頭到達(dá)另一個(gè)石頭所需要踩過(guò)的其他石頭（即非這兩個(gè)石頭）的數(shù)目為 (len-1)/t,并且可以保證一定有這樣子的一種到達(dá)方法。

????????????接下來(lái)，就應(yīng)該介紹動(dòng)態(tài)轉(zhuǎn)移方程，以及相關(guān)的預(yù)處理了。
????????????對(duì)于數(shù)據(jù)，我們首先要進(jìn)行一些必要的預(yù)處理：
????????????1、對(duì)于讀入的每個(gè)石頭的位置，通過(guò)對(duì)于上述條件的判斷，如果從0點(diǎn)不可到達(dá)，則可以將次石頭略去不考慮；
????????????2、因?yàn)轭}目要求一定要過(guò)河（就是行動(dòng)的總距離要大于L才行），所以就在 L+1~L+S 這S個(gè)位置上人為的構(gòu)造出S個(gè)石頭，并認(rèn)為這些石頭是本身存在與河面上的。
????????????3、對(duì)于上面提到的每一個(gè)石頭，應(yīng)該對(duì)其預(yù)處理出一個(gè)值（我將其保存在B數(shù)組中），代表從0點(diǎn)到達(dá)這個(gè)石頭中間要踩過(guò)多少個(gè)石頭（這里踩過(guò)的石頭可以是已有的，可以是從手中放下的，石頭數(shù)允許是不合法的。注意：這個(gè)數(shù)組只是表示這一種可能情況，不表示一定滿(mǎn)足輸入數(shù)據(jù)）；
????????????4、動(dòng)態(tài)規(guī)劃的初始狀態(tài) F[i][0]=b[i]+1。

????????????接下來(lái)，介紹動(dòng)態(tài)規(guī)劃中狀態(tài)的表示方法：
????????????F[i][j]表示從0點(diǎn)到第i個(gè)石頭，中間如果踩過(guò)j個(gè)石頭，所需要的最少步數(shù)。（注意：此處是踩過(guò)，如果只是經(jīng)過(guò)某個(gè)石頭而不必踩過(guò)，則這個(gè)石頭就不包含在這j個(gè)石頭中）。

????????????動(dòng)態(tài)轉(zhuǎn)移方程：
????????????F[j][k+ifneed(i)]=min{F[i][k]+w[i][j]+1} (0<=k<i),其中w[i][j]表示從第i個(gè)石頭到第j個(gè)石頭中間要踩過(guò)的石頭數(shù)，ifneed表示一種判斷條件，就是用來(lái)判斷如果到達(dá)第j個(gè)石頭,是否一定要踩到第i個(gè)石頭上面,如果必要,則返回1,否則返回0。具體的判斷方法實(shí)現(xiàn)如下：


????????????最后就是對(duì)結(jié)果的判斷了。

????????????第一項(xiàng)，應(yīng)該是判斷是否存在能夠過(guò)河的方法。由于可以明顯的看出，在上述動(dòng)態(tài)規(guī)劃的過(guò)程中，由于判斷了中轉(zhuǎn)石頭是否必要踩過(guò)，已經(jīng)形成了一定的貪心規(guī)則。所以，在輸出時(shí)，就應(yīng)該對(duì)最后s個(gè)石頭（就是自己加進(jìn)去的石頭判斷），如果b[i]滿(mǎn)足條件，就取其中最小的；如果b[i]>m，就取F[i][b[i]-m]里最小的。（原因應(yīng)該很簡(jiǎn)單，因?yàn)樯厦嬖谵D(zhuǎn)移和預(yù)處理時(shí)已經(jīng)保證了得到最優(yōu)）
????????????第二項(xiàng)，就是在第一項(xiàng)沒(méi)有找到過(guò)河步數(shù)是，求出最遠(yuǎn)走到哪里了。這里就更為簡(jiǎn)單了：1、最近可以走m*t的距離；2、如果F[i][j]可行（就是不為0），并且滿(mǎn)足m+j>=b[i]，就判斷rock[i]+(m+j-b[i])*t 是否為可行解即可。
????????????
????????????再來(lái)分析一下時(shí)間復(fù)雜度，由于石頭數(shù)不大于100，s也不大于10，對(duì)于上述O(N^3)的算法是絕對(duì)不會(huì)超時(shí)的。這樣，這道題就完美解決了。

附上代碼：