集訓(xùn)隊(duì)作業(yè)難題討論活動

1、第三階段：相互學(xué)習(xí)與任務(wù)申請：學(xué)校：江蘇省常州市第一中學(xué)一、關(guān)于每道題目，寫出你的收獲和看過大家說的話后，自己另外想說的話。序號你的收獲（在敘述時(shí)記提到給你收獲的 人）實(shí)在沒收獲的可空著，這項(xiàng)主要是給自己學(xué)習(xí)看的。想說的話（可以是別人說的話表示同意，產(chǎn)生疑問或者參加）0001用 A*算法。0002所說的離散化算法，正確性可以得到保 證，時(shí)間在大多數(shù)情況下也可以承受。但是作為的題目，其他選手更優(yōu)的數(shù)論方法值得證明。感覺用數(shù)論算法是對的，但是還是覺得無法證明。0003分?jǐn)偹惴ńo了我啟示：可以根據(jù)數(shù)據(jù)類型采用不同的算法，以達(dá)到平衡的效果。不太可能出現(xiàn) O(nlgn)的算法，但是散列表的確能夠有很好的

2、實(shí)際效 果。0004O(n4)的算法是正確的。這說明這題可以用動態(tài)規(guī)劃解決。仍然沒有找到能證明正確性的O(n3)的算法。0005德給出了正確方法。最長路徑。0006，昆和給出了證明。貪心。0007很多人都給出了正確方法。二分。0008大家都說是搜索，我也只想到搜索，而且我覺得搜索的時(shí)間還是很快的。邵烜程懷疑可以找到直接的方法？我也曾經(jīng)想過，但是沒想法搜索。0009侯啟明的方法很 ，而且我覺得也是對的，畢竟這個(gè)動態(tài)規(guī)劃的證明還是很完全的。 德的方法雖然沒有證明，但我覺得組成的數(shù)只含 2 和3 是顯然正確的。動態(tài)規(guī)劃或是貪心。0010我原以為這是一個(gè)找Hamilton 回路的NP 問題，看了大家的

3、解答才 然大悟。 德對O(n3)的算法給出了證明。0011這道題很多人都給出了自己的解法，我覺得佳說得幾點(diǎn)都很全面了。我也想到過要利用字符的性質(zhì)但僅想到第二種方法。0012最初提交的解法是正確的。而且復(fù)雜度較低。這就是一道求一個(gè)點(diǎn)是否在 3 維凸包 ，可以用計(jì)算幾何方法解決。0013原來是者把題意理解錯(cuò)了，fa?？磥眸Q的英語水平還有待加強(qiáng)啊字符串匹配。0014分層計(jì)算吧，對于每一層（都是二IOI2003 中國國家集訓(xùn)隊(duì)難題活動維的情況）可以用數(shù)論的方法算出來。0015看過書后就解決了。Polya 原理。0016很多人都提出是最佳匹配。最佳匹配。但是并沒有人給出了證明，而且有些方法似乎是錯(cuò)的。0

4、017的構(gòu)造法很受啟發(fā)！高手就是高手啊構(gòu)造。0018除了貪心之外，還有選手提到了一些別的方法，比如不等式，動態(tài)規(guī)劃等。但是如果可以，貪心顯然是最好的方法。貪心，希望有人能夠給出證明。我不會，呵呵。0019余方程。0020O(n2)的算法很多人都想到了，但O(nlgn)的算法卻用二叉樹的結(jié)構(gòu)進(jìn)行了優(yōu)化。而德、昆和更是提出了 O(n)的方法。使我受到了很大的啟發(fā)。O(n)的算法是最優(yōu)的了，而且證明了正確性。0021很復(fù)雜的算法，一般情況下很難想到（連聽懂都有），不過寫下來以后就看懂了。0022搜索的順序和剪枝影響著搜索的實(shí)際效果。深受啟發(fā)。德的算法應(yīng)該還是指數(shù)階的，不過它的實(shí)際效果較好。0023在

5、動手之前果然沒有想到很多細(xì)節(jié)問題。編了一個(gè)很長的程序，但是根本不對，調(diào)試中0024和侯啟明的。0025學(xué)習(xí)中。0026太難了。0027提出了一個(gè)利用Hamming 性質(zhì)轉(zhuǎn)化模型的方法，而不是僅僅局限于最小生成樹上。很有啟發(fā)。0028寬搜。0029既然對這種題目都不感，我也不可能有能力推出什么公式了。還是只會遞推。0030又是推公式這道題和上題類似，都屬于找到遞推公式但無法轉(zhuǎn)化成通項(xiàng)共識。0031既然對這種題目都不感，我也沒有什么。網(wǎng)絡(luò)流。0032我不能理解。難道沒有多項(xiàng)式算法嗎？0033看了寫的內(nèi)容，才想到要判斷一些特殊情況僅僅解方程是不夠的。解方程。0034搜索的速度還是很快的。0035的證

6、明方法的確很巧妙。還有很多選手提出了在二分是要注意分類。不過我已經(jīng)注意到這一點(diǎn)。二分。0036這題以前做過了，是 POI 的題目吧，原來是上屆集訓(xùn)隊(duì)的訓(xùn)練題。的解法看懂了。0037貪心。0038侯啟明的方法和冬令營上講的方法都很優(yōu)秀。字符串匹配。0039非常想知道O(n2)的算法，好像沒有誰給出了這個(gè)算法。能不能請或給出一個(gè)算法？0040Febonacci 數(shù)，多么又創(chuàng)意啊。而且證明也很完美，感謝等選手。構(gòu)造。0041貪心。0042搜索剪枝。0043原先只想到寬搜，但不知用二叉堆優(yōu)化感謝提供解法或提供的選手。寬搜+堆0044沒？因?yàn)樘y了??！NP?0045反演？沒聽。大多數(shù)選手和的一樣，都是搜

7、索+最小表示判重。用組合數(shù)學(xué)公式仿佛是一種較好的方法。搜索+最小表示判重0046果然 zju 上過的人都是用的搜索。不過的想法給了我一些啟示。00470048搜索。0049沒有比的更進(jìn)一步的算法，失望即使是寬搜，正確性也有待。解方程？寬搜？0050IMO太強(qiáng)了。即使是連通圖的情況，我也沒有想到。連通圖的情況證明的確很巧妙。也許出題人的原意就是連通圖的情況吧。連通圖：DFS；非連通圖：DFS+調(diào)整？0051大家的想法都差不多。有附加條件后也許不能求得最優(yōu)解，但是可以用貪心求得一些較優(yōu)解。0052兩個(gè)方向：寬搜的方法和數(shù)論的方法。這道題省里面訓(xùn)練的時(shí)候做 過。寬搜的方法只要在一個(gè)- 100,100

8、*-100,100的矩形范圍內(nèi)就能對樣例的所有點(diǎn)，但是事實(shí)證明這是不夠的，有一些情況不能滿 足。但是懷疑仍有一個(gè)更大的范圍能從理論上證明是正確的。另外如果用數(shù)論方法，難就難在如何余方程組。 提出 法也能對所有的測試數(shù)據(jù)，無法證明其正確性。0053昆的方法（標(biāo)準(zhǔn)）我看懂了。德說的貪心方法我還不理解。貪心。0054想得很仔細(xì)，盡管也是用最基本的方法，但是卻提出了許多值得思考的細(xì)節(jié)。博弈問題。用類似五子棋的方法。0055看過書后就知道了。數(shù)論。0056研究標(biāo)程中0057據(jù)說貪心有反例。我聽到很多人說有反例，我也覺得貪心法不能全對，但為什么沒人把反例寫出來呢，郁悶。0058解模線性方程組。0059。這

9、道題目四個(gè)之前就在 zju 上看到了，而且過，的解法就是寫的。這種方法的效率是能夠在較短的時(shí)間內(nèi)（相對于其他 ac 的程序）出解，但是認(rèn)為這不是一個(gè)最好的方法，所以才拿出來當(dāng)作難題 的。沒有必要這么奇怪吧。0060盡管搜索的復(fù)雜度看上去是很大的，但是由于很多情況都能剪枝，所以總的來說還是不滿的。搜索。0061據(jù)說搜索能對數(shù)據(jù)。還是不會。0062提出了調(diào)整算法。調(diào)整法。0063度限度生成樹。但含是不會求解。00640065006600670068德說的貪心的對的。但第二問根本沒人回答。0069除了很多人都那些優(yōu)化方法，就沒有別的了。像是組合數(shù)學(xué)題，但是又只能用搜索解決。0070O(n2)的動態(tài)規(guī)

10、劃。很久前就看到過了。0071的方法很。O(n2)。感謝。0072不會做。0073盡管是很簡單的題目，但還是又很多方法。德說的應(yīng)該是很全面了。特別是觀察法，是一種新的思路。00740075我也很喜歡這道題目，呵呵。很多選手都提出了好的方法。0076的理解好像有問題吧！這道題的確是說，每次把所有的a 都換成 s1 啊。寬搜。0077關(guān)于平面圖的論證和關(guān)于復(fù)雜度的分析都很。平面圖。007800790080很經(jīng)典的題目。00810082網(wǎng)絡(luò)流。0083和都說得很好。0084很好的計(jì)算幾何的題目。0085008600870088德的發(fā)現(xiàn)的確很有道理。0089二、隊(duì)員互評最喜歡的三位隊(duì)員：覺得做得不錯(cuò)的

11、五位隊(duì)員（不得與前三位重復(fù)）：*注：上述部分先后。對于某些題目，特別想感謝以下的同學(xué)（可空缺，也可多寫）：三、心得體會（至少 1000 字，可多寫）經(jīng)過了近半年時(shí)間的集訓(xùn)隊(duì)活動，階段基本上結(jié)束了?？偟膩碚f，這次的活動到目前為止是成功的。隊(duì)員們也一定從中學(xué)到了很多東西。這次活動的主導(dǎo)是由于近年來國際競賽難度增加，所以讓集訓(xùn)隊(duì)員一些難題目隊(duì)員理由0098雖然不是集訓(xùn)隊(duì)選手，但是從他的分析中，我看到了湖南和江蘇的差距。隊(duì)員總體理由講得特別好的題目（及認(rèn)為其講得好的理由）侯啟明他太牛了，不能不提。0009，0010，0038很認(rèn)真，很厲害。0035，0077，0083復(fù)旦的老師和學(xué)生都稱贊他，一定有他

12、們的理由。主要是對平面圖的分析，給了我很深的印象，0077等?？杖睂幦蔽銥E很多問題也許沒有完美的 ，但是他同樣分析得很好。0027，0038隊(duì)員總體理由講得特別好的題目（及認(rèn)為其講得好的理由）特別認(rèn)真，很多題目都給出了詳細(xì)的解答。0046，0083，0020，0046，0083很多題目的解答體現(xiàn)了高手風(fēng)范。0004，0017，0020，0040，0062，0071，0099德提交了很多題目，解決了的題目。0005，0009，0010，0020，0053，0068，0073，0088，還有很多009000910092009300940095009600970098的方法我聽懂了。但是他對復(fù)雜性的

13、分析沒講清楚（也許是我沒聽清楚），我覺得他的方法的確是線性的。0099很好的博弈問題。平局增加了問題的難度。鳴和 在冬令營上的發(fā)言都很好。特別是的方法，實(shí)際效果是很好的。0100題，共同提高，從中也能夠看出那些真正的解決難題的選手。因此，這次選擇的 100 道 題，很多都是有質(zhì)量，有難度的。特別是提供的若干題目，是我領(lǐng)略到了真正的難題，也使我看到了差距（至今還有很多題目不之所云）。集訓(xùn)隊(duì)中有一些選手體現(xiàn)了很高的水平。和去年的 POI 解題 比起來，今年的活動有很多新的特點(diǎn)。首先，給了 很長的時(shí)間進(jìn)行 ，而且在冬令營上特地提供時(shí)間供集訓(xùn)隊(duì)員和很多非集訓(xùn)隊(duì)員進(jìn)行 。這大大開闊了 的視野，使 看到了

14、別的選手的方法和自己的區(qū)別。有些題目我沒有想出來的，別的選手卻提出了很好的解法；還有些題目雖然大家都可以做，但是做法各不相同，也給了我許多思考的空間。由此看來， 應(yīng)當(dāng)算是這次活動的一個(gè)進(jìn)步。另外，這次難題征集時(shí)沒有限定題目的范圍。因此有很多的來源，甚至是某些隊(duì)員的 。有些題目是我沒有見到過的，很多題目甚至沒有標(biāo)準(zhǔn)解答。這些題目都給人耳目一新的感覺。從這次活動的效果來看，確有了一定的收獲。首先是方法上，例如，0040，一道很好的構(gòu)造題，我只會簡單的貪心，但是很多選手卻能把它和 Febonacci 數(shù)列聯(lián)系到一起，這體現(xiàn)了很多選手的想象力和基本功；再比如說 0017，的構(gòu)造方法，的確十分巧妙，用模運(yùn)算建立了一一對應(yīng)的關(guān)系。其次，我也了解了很多新的算法，例如，我0047Net 那題，用到的是弦圖的判定；還有很多題目中的新的名詞（大多數(shù)都是）。雖然這 些知識我還不都理解，但是我覺得對它們有一定的了解還是很好的。在這次活動問題中，有一部分是選手的，或是很容易就看出沒有標(biāo)準(zhǔn)解法的。這些題也代表著競賽的一個(gè)新的方向：開放性試題。盡管很難，還是有很多選手提出了自己的想法或是不成意見，在中逐漸形