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

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

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

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

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

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

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

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

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

9、說明的程序基本上是能說得過去的。數(shù)據(jù)的分析：先說一下下面要提到的四個(gè)程序，它們就是根據(jù)初步算法，優(yōu)化 1，優(yōu)化 1、2，優(yōu)化 1、 2、3 編出的程序。這些程序中，前兩個(gè)比較適合“多對(duì)一”的教學(xué)，后兩個(gè)程序發(fā)揮比較穩(wěn)定，可以較好地解出大多數(shù)數(shù)據(jù)。由程序的運(yùn)行結(jié)果對(duì)比可以看出，第 1、2、3、6、10 個(gè)測試點(diǎn)基本上是送分的測試點(diǎn)。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 個(gè)測試點(diǎn)，一個(gè)很弱的程序都能得出比更優(yōu)秀的解。也就是說，在賽場上，只要花少量精力，拿到 50 分是比較容易的（不過在沒見到怕誰也不會(huì)只做簡單的程序）。的時(shí)候，恐第 1、2 個(gè)測試點(diǎn)自然不必說了，動(dòng)物數(shù)量很少，技能也只有區(qū)區(qū)的 2 兩種。這兩個(gè)測試點(diǎn)搜索應(yīng)該也能拿到分。第 3 個(gè)測試點(diǎn)，也是比較簡單的，只要把 Dijkstra 求 Tas的算法寫正確，就能得出和相

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

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