第一百二十二章 全國青少年信息學奧林匹克競賽

　　信息學聯賽是五大學科里面最為特殊的一項。

　　最最重要的原因。

　　是因為學校壓根就沒有開設計算機這門課程。

　　雖然說潛北中學里也有著自己的“機房”，但是除了有時候需要學生上網填寫信息之外，幾乎從來都不對學生們開放。

　　不僅如此，其他幾個學科的競賽的名稱都是“全國高中xx聯賽”，“全國中學生xx競賽”。

　　信息學的全稱卻是“全國青少年信息學奧林匹克競賽”。

　　可能是因為信息學更加的小眾，其中又分為NOI和NOIP，前者為正式競賽，后者為普及組和拔高組。

　　賽程里，又有一堆看起來就十分的麻煩東西。

　　如果不是因為強迫癥，想要湊齊一個五大學科全能金牌，蘇牧是真的懶得去看這些莫名其妙的規章制度。

　　不過好在信息學這些東西要等今年下半年才會正式籌備，到時候再跟學校專門負責的老師聯系一波應該沒什么大問題。

　　暑假的話，稍微做做題，刷到三四級的地步應該就已經夠用了。

　　除了五大學科競賽之外。

　　蘇牧還打算試試全國中學生英語能力競賽和每年一度的新概念作文大賽。

　　這些也都是年底才會正式出通知。

　　對于蘇牧來說只能算是日程表的末端。

還有一個比較重要的點就是世界影響力　　影響力方面蘇牧現在還處于一星，并沒有具體的數值只有一個小小的進度條。

　　看著進度條的樣子，蘇牧現在的一星也僅僅完成了不到10的樣子。

　　關于這個方面蘇牧打算先從小說方面還有視頻方面入手，成為一名作家或者成為一個up主。

　　不僅可以獲得一定的影響力，而且說不定還能獲得一定的酬勞。

　　尤其是Dilidili這幾年推出的激勵計劃，可是養活了相當一大批為愛發電的up主。

　　而且，雖然影響力這邊現在每個月只能提供一個技能點。

　　但是升到后期絕對是一個長期獲取技能點的途徑。

　　零零散散的記錄著著些東西。

　　回過神來。

　　蘇牧愕然的發現自己的事情好像真的挺多的。

　　雖然壓力不是很大，都是些送技能點的競賽。

　　但是積累起來還是得花時間去磨煉。

　　“還是先得把身體素質多點個兩級。”

　　蘇牧默默的想到。

　　“叮！您進入了五級圖書館，學習所獲得的所有積分增幅100”

　　“叮！您查看了信息學題目，信息學積分1，當前積分1/100，等級：一級。”

　　因為浙東外語外貿大學里有些學生暑期需要在學校里復習考研，所以圖書館會在暑期里的周一到周五的白天開放到晚上八點，周六周末閉館。

　　因為沒有其他事情的束縛，蘇牧現在的行動力變得很高。

　　回到家后的第一個工作日，便開始了自己的圖書館之旅，他現在做的事情是要把信息學這個學科重頭開始學起。

　　但是，才剛剛上手，他就覺得有些不適應。

　　因為信息學實在是太雜了。

　　初賽考察通用和實用的計算機普及科學知識，以筆試為主。

　　復賽為程序設計，須在計算機上調試完成。

　　而不論是計算機普及科學知識還是程序設計，蘇牧都得從頭開始學起。

　　他現在手上的兩本書是在淘寶上購買的《信息學奧賽一本通·提高篇》和《信息學奧賽之數學一本通C版》

　　“近些年來的信息學競賽試題，經常出現求一個問題的可行解或者最優解的題目，這類問題統稱為最優化問題，貪心算法是求解這一類問題的常用方法。”

　　蘇牧首先打開的是這本《信息學奧賽一本通·提高篇》

　　“最優化問題。”他摸了摸下巴，腦海中閃過了幾種數學里關于最優化的解決方案。

　　信息學很多東西本身就是與數學相通的，這讓他的心境稍微穩了積分。

　　但是，當他看到例題的時候，腦海中瞬間就出現了幾個問號。

　　題目1：在N行M列的正整數矩陣中，要求從每行中選取一個數，使得選出的N個數的和最大。

　　解析：本題可以用貪心算法求解，選N次，每一次選出相應行中的最大值即可。

　　蘇牧：“”

　　這種題目還需要解析？？

　　這不是理所當然的嗎？

　　她看向了第二個題目。

　　題目2：在一個NM的方格陣中，每一個格子賦予一個數（即權值），規定每次移動時只能向上或者向右，現試找一條路勁，使其從左下角至右上角所經過的權值之和最大。

　　解析：在這種情況下.....

　　一步一步看下來。

　　蘇牧倒也沒覺得有什么難的，只不過是一些取極值的問題。

　　但是，當他翻到后面的經典習題和解析的時候，整個人都不好了。

　　經典習題在8×8方格的棋盤上，從任意指定方格出發，為馬尋找一條走遍棋盤每一格并且只經過一次的一條路徑。

　　解析：首先這是一個搜索問題，運用深度優先搜索進行求解，算法如下：

　　⒈輸入初始位置坐標x，y；

⒉步驟　　如果c>

　　64輸出一個解，返回上一步驟c

計算(x，y）的八個方位的子結點，選出那些可行的子結點　　循環遍歷所有可行子結點，步驟c重復2

　　顯然⑵是一個遞歸調用的過程，大致如下（C程序解析）：

output_solution();//輸出一個解txhn[i].x;//hn[]保存八個方位子結點dfs(tx，ty，count1);//遞歸調用　　這樣做是完全可行的，因為它輸入的是全部解。

　　但是馬遍歷當8×8時解是非常之多，用天文數字形容也不為過，這樣一來我們的求解的過程就非常慢，并且出一個解的時間也會也非常慢。

　　當我們在每個結點對其子結點進行選取的時候，優先選擇‘出口’最小的進行搜索，‘出口’的意思是在這些子結點中它們的可行子結點的個數，也就是‘孫子’結點越少的越優先跳。

如果優先選擇出口多的子結點，那出口少的子結點就會越來越多，很可能出現‘死’結點　　這樣對下面的搜索純粹是徒勞，這樣就會浪費很多無用的時間。

　　反過來如果每次都優先選擇出口少的結點跳，那出口少的結點就會越來越少，這樣跳成功的機會就更大一些。

　　蘇牧：“。。。。”

　　他的腦海中再次緩緩的出現了一堆問號。

　　完全沒想到居然會有這么大的跨越。

　　看著僅僅只有一個小題，卻是密密麻麻的解析，蘇牧突然明白了為什么數學奧賽參加的人那么多，信息學奧賽參加的人卻那么少。

　　這東西，確定是適合青少年做的？？

　　不會禿頂嗎？？

PS2:弱弱的求幾張