江寒按了一下電腦電源按鈕，很快顯示器上出現了NOI Linux的啓動界面。

這就必須“贊”一下了，往年都是用虛擬機進入Linux的，今年改成原生系統了。

這樣一來，系統的啓動和運行速度，起碼要提高一倍以上。

實際上，有些省份目前還是Windows和虛擬機Linux並行，選手自行選擇趁手的操作系統。

合江省這次竟然走在了全國前列，率先淘汰了大衆熟悉的Windows……

足足等了三十多秒，終於進入了Linux桌面。

江寒先把桌面分辨率等環境參數，調整成了最順手的設置。

然後按下【Alt+Ctrl+T】，調出終端，用“ls”命令查看了一下。

賽組委果然沒有預先建立比賽文件夾，這樣就只能自己動手了。

江寒按照監考教師下發的參賽說明，使用“mkdir”命令建立了一個文件夾，命名爲【Jianghan】。

接下來，他又在終端中輸入【vim test.cpp】，啓動了代碼編輯器vim的IDE界面，然後按“I”鍵進入插入模式。

這樣就可以鍵入代碼了。

這次比賽仍然可以在c、c++、pascal三種程序設計語言中任選一款。

三種語言各有特點，c語言執行效率最高，pascal語法簡單，但稍嫌刻板，好處是不容易犯低級錯誤，c++則更加適合複雜程序的設計。

江寒毫不猶豫地選擇了最爲熟悉的c++。

首先完成一個測試代碼。

功能很簡單，就是在標準的“hello world”基礎上，增加了一個從1加到100的循環程序，然後將結果輸出到屏幕上。

江寒編輯完代碼，稍微檢查了一遍，排除了可能存在的語法錯誤，然後按“ESC”鍵，退出插入模式，再輸入“WQ”存盤退出。

接下來，回到終端中，輸入命令行指令：【g++ test.cpp -o test】，回車。

這樣，g++編譯器就開始工作，將test.cpp編譯成了可執行文件test。

編譯過程中，如果有錯誤，就會提示出來。

但江寒這個測試程序十分簡單，並沒有犯任何小錯誤，一次就通過了編譯。

接下來，就可以輸入【./test】，來執行生成的可執行文件了。

稍微觀察了一下，確認程序可以正常運行。

這樣系統的檢測和調整就初步完成。

接下來，進行一些進階的設置。

江寒用【vim ～/. vimrc】命令，再次打開vim界面，並加載了配置文件vimrc。

然後修改了一下其中的幾個參數，將vim編輯器的操作模式，調整成了最順手的狀態。

接下來，在自己的比賽文件夾中，創建兩個文本文件：test.in 和test.out。

再修改測試代碼，爲其增加文件輸入輸出功能，並添加對頭文件的引用，使其能操作test.in 和test.out。

再次調試正確後，就得到了一份c++模板代碼。

一會兒比賽正式開始，只需要在模板的基礎上，進行一些修改和填補就可以了。

這些都搞定之後，還剩下大約15分鐘時間，比賽才能正式開始。

江寒在vim中隨便輸入了幾個小程序段，快速排序、堆排序、二分查找……進行賽前熱手，以提升手感。

8點20分，監考人員通知大家登陸ftp服務器，用公用賬號和密碼下載試題壓縮包。

江寒只用了30秒，就把試題壓縮包下載到了自己的桌面上，並解壓到了一個文件夾中。

隨後依次點開3道試題的說明文檔，認真查看了起來。

只用了10分鐘，他就將3道題都看完一遍，並理清了解題思路。

然後按照題目難度，排了個序。

巧的是，三道題的編號和難度係數一一對應。

當然這是對於他來說，換個人看，很可能覺得第2題纔是最難的……

江寒在【Jianghan】文件夾裏，創建了三個子文件夾，按照要求，分別命名爲【vigenere】、【game】和【drive】，一會兒爲各個題目編寫的代碼，就分別存放於對應的文件夾中。

江寒先看第一題：Vigenère密碼。

這是一個密碼學問題，加密規則很簡單。

密鑰k是一個字符串，K=K1K2K3……Kn，當明文M=M1M2M3……Mn時，加密後的密文爲C=C1C2C3……Cn，Ci=Mi⊕Ki。

⊕是一個規則表，26行，26列，每一行代表一種字母替換方式，第一行從A到Z順序排列，第i+1行是第i行循環左移1個字符得到。

⊕運算不區分大小寫，加密結果套用明文的大小寫格式。

當M的長度大於K的長度時，重複使用K。

問題：給出密鑰和密文，求原本的明文。

如果讓江寒給這道題的難度評級，大約只肯給出1星。

這麼簡單的題目，約等於白給。

解題思路十分明確，找出加密規則⊕的數學描述，然後使用⊕的逆運算，代入密鑰K和密文C，求出明文M。

如果實在不想麻煩，也可以將規則表建立成一個字符數組，然後反向查表。

可以說，只要認真訓練過的選手，這道題沒理由會丟分。

江寒迅速在草稿紙上，將流程圖畫了出來，然後編寫C++代碼。

5分鐘搞定代碼，然後在test.in中編制了10組測試數據，一一代入進行模擬計算。

輸出的結果與紙筆計算十分吻合。

此題結束。

由於linux系統區分大小寫，所以江寒在解題的過程中，除了題目中有規定的輸出文本等，程序中使用的所有變量等等，一律使用小寫字母。

接下來是第二題：國王遊戲

N個大臣排成一隊，國王站在隊伍最前方，每個人左右手上，分別寫有一個數字。

國王按照規則，賜予每個大臣一定數量的金幣。

每個大臣所能得到的金幣數，等於排在該大臣之前所有人左手數字之乘積，除以其右手的數字，結果向下取整。

問題是，如何調整大臣的順序，才能讓獲得的金幣最多的那個人，得到的金幣儘可能的少。

注意，國王始終站在隊伍最前方。

然後在輸入數據說明中，有如下提示。

對於 20%的數據，有 1≤ n≤ 10，0 < a、b < 8；

對於 40%的數據，有 1≤ n≤20，0 < a、b < 8；

對於 60%的數據，有 1≤ n≤100；且答案不超過 10^9；

對於 100%的數據，有 1 ≤ n ≤1，000，0 < a、b < 10000。

這道題的難度比第一題稍有提高，但也不算特別費勁。

此題的坑點在於，輸入的數據有可能很大，使用通常的編程方式，只能通過前40%的數據校驗，想得高分，就必須使用高精度編程。

解題思路就是窮舉法。

針對給出的大臣數N，以及給出的N+1組左右手數字a、b，計算每種可能的站位情況所對應的金幣最大值m，再求出集合M={m1，m2，m3，……mk}中的最小值。

由於N個大臣共有N！種站位，所以一旦N足夠大，計算量將是非常恐怖的。

這道題一共10個檢查點，每個檢查點10分。

比賽對於程序運行時間的限制，是每個檢查點不超過1秒。

對於運行空間的限制，是每個程序使用的內存，不得超過128兆。

無論在哪個檢查點超時或者輸出錯誤，都會扣掉該點的分值。

計算機打分的時候，一般會輸入強弱不同的10組測試數據。

遇上小點的數字，比如本題中前20%的數據，只要程序沒有邏輯錯誤，基本都能通過測試，拿到分數。

但當N稍微大一點的時候，使用暴力搜索算法，很可能會超過1s的時限。

所以，一定要找出規律，對輸入的N組a、b進行預處理。

江寒在紙面上推演了一下，很快得到了一個猜想：當大臣們按a×b的積升序排序時，得到的序列就是最優的方案。

那麼原本的暴力搜索程序，就可以改造一下了。

第一步，排序，求出最優方案時的隊列，第二步，計算該情況下的M值。

毫無疑問，這個算法的效率遠比暴力搜索更高，其運行時間取決於使用的排序算法的時間複雜度。

江寒先編制了一個最樸素的暴力搜索算法，測試了一下，驗證程序沒有邏輯錯誤後，另存了一份。

然後又按照改進後的思路，修改了一下代碼，用快速排序整理隊列，然後計算M值。

接下來就是比較好玩的東西了。

對拍。