star解題報告問題初看起來唯一的感覺就是麻煩、無從下手

1、Star解題：問題分析：問題初看起來，唯一的感覺就是麻煩、無從下手。首先是引入了“教學能力”與“頑皮程度”的概念，初始的時候懂得較多技能的動物不一定能成為。其次，學習技能的時候可能需要老師自己先去學技能，就是說可能出現(xiàn)“為了讓動物 s學會技能，先讓動物 tr，然后 t 和 r 一起教 s”情況。所以，面對這種問題，只能嘗試從自己想到的最簡單的方法做起，逐步優(yōu)化算法，以期獲得較好的效果。初步方法：顯然一個“全能”的技能是一項一項或幾項幾項學出來的，所以不難得出一個方法先求出每個動物學習每項技能所需要的時間，然后將每個動物學習技能令序列“拼”出來，最后選出時間最短的作為。1 求出每個動物學習每項技

2、能所需要的時間?？偟膩碚f是使用 Dijkstra，設 Tas表示動物 a 學習技能 s 所需要的時間。初始的時候，如果動物 a 本來就會技能 s，則 Tas = 0，否則 Tas = 。然后使用以下方法求出所有能求出的 Tas：do 開一個臨時數(shù)組das; for (i=0;in;i+)for (j=0;jm;j+) if (Tij =)用貪心法選出Taj的動物作為老師教動物 i 學會技能j，并將學習時間存入 dij；選出mindas的存入 T； while (本次循環(huán)內(nèi)計算出了一個教學活動)；那么，怎么求出 dij呢？這里使用的是貪心法，具體的過程就是：將所有與動物i 認識的動物按照Taj從

3、小到大的順序排序； for (k=0;kn;i+) 選出Taj第 k 小的動物 t；if (令動物t 做老師節(jié)省的時間 Tsj) 令動物t 做老師；這樣，就可以計算出 Tas。2 根據(jù) T 拼出命令序列這里使用一個最簡單的方法直接計算 Totala = Tas，選出 Total 值最小的一個動物作為。這樣，就得到了初步的方法，這樣的程序只能在第 1、2、3、6、10 個測試點得滿分。不過，沒有關系，的算法還有許多油水可榨哩！算法的優(yōu)化 1：回顧算法的實現(xiàn)，觀察程序的輸出比如說，A B C D E 同時會技能 1、2，可以發(fā)現(xiàn)命令序列中存在許多明顯無用令。先讓動物 A B C D E 教動物 F

4、 技能 1，然后又重新找動物教動物 F 技能 2，這樣就造成了浪費在第 1 個教學活動中動物 F 已經(jīng)學會了技能 2。所以，得到了一個優(yōu)化在拼命令序列的時候，用一個數(shù)組來動物已經(jīng)會的技能，就不會出現(xiàn)一個動物去學習早已學會的技能的情況了?，F(xiàn)在，程序的效能又有了。但是，4、5、7、8、9 幾個點的效果仍然很差，要嘗試進行進一步優(yōu)化。需算法的優(yōu)化 2：其實到現(xiàn)在一直都沒有使用考慮條件在教學的時候，可能同時教授多項技能。這個應該怎么使用呢？比如，又可能發(fā)現(xiàn)自己的程序會產(chǎn)生這樣令：5 1 2 3 4 9 56 1 3 4 7 8 9 5根據(jù)算法的第 1 個優(yōu)化，知道這兩條命令并不是教授動物 5 同一項技

5、能，那么假設教授的兩項技能分別為 a、b。兩條命令的老師中都有動物 1、2、3、4，所以不難得出，在執(zhí)行第 2 條命令時，動物 1、2、3、4 肯定是既會技能 a，又會技能 b 的。這時，就可以將兩條命令合并成：4 1 2 3 4 5命令的合并是非常有用的，前提是：1 合并后命令耗費的時間必須小于兩條命令的時間總和。 這一點是顯然的，如果不這樣命令的合并就沒有意義了。2 兩條命令的合并方式必須是前面為什么呢？假如出現(xiàn)以下的情況： 2 1 2 8（學習技能 a）2 1 2 8（學習技能 b）令合并到后面令中。動物 1、2 肯定是在兩條命令的中間學習了技能 b（否則根據(jù)優(yōu)化 1 的規(guī)則，第 2 條

6、命令就不會出現(xiàn)了）。此時如果將后面一條命令合并到前面去，動物 8 就無法學習技能 b，這樣就會產(chǎn)生 Illegal Solution 了。合并兩條命令是比較簡單的，相當于求兩個有序數(shù)列的公共子序列，時間復雜度大約為O(n)。兩條命令合并以后得到的新命令也可以和其可。令合并，只要符合剛才所講的前提即經(jīng)過第 2 個優(yōu)化，的又得到了優(yōu)化，第 1、2、3、4、6、7、8、10 個測試點都能得到滿分，其中第 2、4、6、7、10 個測試點超過。但是，第 5、9 個測試點仍然不能得到滿分。特別是第 5 個點，距離較遠。算法的優(yōu)化 3：仔細分析可以得出，優(yōu)化 2 實際上是存在1 2 31 3 41 4 5

7、1 2 3的。例如，對于以下這個命令序列：根據(jù)優(yōu)化 2，程序?qū)训?1 條命令合并到最后一條命令。對于這兩個命令，這樣做并沒有錯，但是第 1 條命令實際上是為第 2 條命令做準備，而第 2 條命令很有可能并沒有被合并，所以就產(chǎn)生了 Illegal Solution。至于為什么包含錯誤的程序還能安然無恙地通過所有測試點，估計是因為測試數(shù)據(jù)正好“適合”這種程序吧！另一方面，合并命令以后，一些原來的教學活動可能不再需要。而并沒有針對這個情況進行優(yōu)化，導致原來令序列里混入冗余令。對于這些情況，可以得出一個優(yōu)化方法：在合并命令以后，對所有命令進行統(tǒng)計，統(tǒng)計每個動物必須學哪些技能。如果統(tǒng)計以后發(fā)現(xiàn)安排的

8、“”并沒有學完所有技能，則判定這樣令序列不合法，從而避免了命令合并的缺陷；如果命令序列合法，就根據(jù)剛才的統(tǒng)計重新生成一遍命令序列，這樣一來，一些因為命令合并產(chǎn)生的不必要的教學活動就可以自然而然地剔除掉了。另一個就是貪心選擇尺度的多樣化：原先在求 dij的時候，貪心的選擇尺度是這兩種分別實現(xiàn)Tas，現(xiàn)在，添加另一種選擇尺度每個動物的教學能力。（需要修改的地方僅有 3 行），然后取最優(yōu)的作為。但是，遺憾的是，即使進行了第 3 個優(yōu)化，第 5、9 個測試點仍不能趕上不過已經(jīng)非常接近了。數(shù)據(jù)程序運行結(jié)果：如果以為 BestAns，程序最終能得到 93 分；以為 BestAns，程序能得到 67 分。這

9、說明的程序基本上是能說得過去的。數(shù)據(jù)的分析：先說一下下面要提到的四個程序，它們就是根據(jù)初步算法，優(yōu)化 1，優(yōu)化 1、2，優(yōu)化 1、 2、3 編出的程序。這些程序中，前兩個比較適合“多對一”的教學，后兩個程序發(fā)揮比較穩(wěn)定，可以較好地解出大多數(shù)數(shù)據(jù)。由程序的運行結(jié)果對比可以看出，第 1、2、3、6、10 個測試點基本上是送分的測試點。No.初步的算法優(yōu)化 1優(yōu)化 1、2優(yōu)化 1、2、310.329702970.329702970.329702970.329702970.3297029721.602677171.602677171.602677171.602677171.8833477630.186

10、440680.186440680.186440680.186440680.1864406840.707575760.707575760.533333330.569444440.61111111520.624171959.291277456.659698505.402473715.3759151460.088297320.088297320.087224430.087224430.4049723717.281843239.196428578.029761909.906684988359.28296372193.65992717178.04004810178.04004810178.0400481

11、0910.7103136510.710313657.930710647.890044597.60776003100.354769650.354769650.354769650.354769650.37905845特別是第 2、6、10 個測試點，一個很弱的程序都能得出比更優(yōu)秀的解。也就是說，在賽場上，只要花少量精力，拿到 50 分是比較容易的（不過在沒見到怕誰也不會只做簡單的程序）。的時候，恐第 1、2 個測試點自然不必說了，動物數(shù)量很少，技能也只有區(qū)區(qū)的 2 兩種。這兩個測試點搜索應該也能拿到分。第 3 個測試點，也是比較簡單的，只要把 Dijkstra 求 Tas的算法寫正確，就能得出和相

12、同的結(jié)果。但是，在這里貪心選擇的尺度是一個問題，如果以 Tas為尺度就能得到全分，但是如果以動物的教學能力為尺度就只能得到 0.28，分數(shù)是很低的。第 4 個測試點，比較突出的地方就在于技能的數(shù)量很多，因此，簡單地“拼”出命令序列已經(jīng)不再能較好地解決問題。前兩個程序都只能得到 0.70757576，究其原因，是由于中的冗余太多總共 5 條命令，每兩條命令的交集都不小。而加入了合并命令的優(yōu)化以后，5 條命令被合并成了 2 條，也變得優(yōu)秀了一些0.53333333。第 5 個測試點，是動物數(shù)量達到 100 的第一個測試點。這是一個比較麻煩的測試點，4個程序，安排的“”有三種21、50、67，但是都

13、未能趕上。前 3 個程序，產(chǎn)生令數(shù)量都過多56、22、15（是 12 條命令）；第 4 個程序產(chǎn)生了一個只有 9 條命令的序列，不過“”沒有選好，所以還是干不上。最有趣的是答案，第 1 條命令竟然讓學生什么技能都學不到，白白浪費時間！第 6 個測試點比較有特點，每個動物初始的時候就會使用的技能較多，動物的關系網(wǎng)也比較密。這些特點造成了也很有特點，第 5、7、8、9 個點大都是一對一的“開小灶”式的教學，而第 6 個點則全是“群體教學”。也正是由于這個特點，第 1、2 個程序也能很輕松地取得比好得多的結(jié)果。第 7 個測試點，動物的關系網(wǎng)很稀疏，因此教學活動傾向于“一對一”的方式。這時前兩個程序是很吃虧的，因為他們產(chǎn)生了大量形式完全相同令，浪費了許多時間。例如第1 個程序就產(chǎn)生了 36 條命令，但是加入命令合并的第 4 個程序只產(chǎn)生了 8 條命令。第 8 個測試點與第 6 個測試點恰恰相反，許多動物剛開始簡直就是“”，動物的關系網(wǎng)也很稀疏100 個動物才有 99 對互相認識。這種數(shù)據(jù)同樣也產(chǎn)生了非常有個性的答案，其它數(shù)據(jù)的教學時間沒有小于 10 的，但是這個數(shù)據(jù)的教學時間超過了 150！第 1 個程序用的是最弱的方法，產(chǎn)生了許多無用令，突出表現(xiàn)是：動物 A 在教 B 技能S 的時候，也將技能