首先給出原來幾屆的免試題解析鏈接：
2013 Linux 興趣小組免試題解析
2014 Linux 興趣小組免試題解析
2015 Linux 興趣小組免試題解析
目前2016 Linux 興趣小組免試題還在線，大家有興趣可以玩一玩。2016年的免試題是由14級成員朱新全、張明瑞、周攀、楊博東、師毅五位同學出的。感謝他們。下面我們進入2016年的免試題揭秘。
這篇文章只是將出題幾位同學整理的解析整合了起來，文章最後會給出原文出處。
【第一關】
當打開免試題鏈接的時候，大家看到了這樣一個頁面：
毫無疑問點擊START，當你還想著和去年一樣圖片裡面含有一些東東的話，那麼你可能得走一些彎路了。
點擊START進去之後會看到這樣一個頁面：
然後發現這個簡單的頁面只有中間的數字可以點擊，點擊多次之後就會發現你進入死循環了,2006=>2007=>2008……2015=>2006=>2007……
遇上這樣的情況我們首先看一下網頁的源碼:
[code]<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title></title>
<style>
html{height:100%;}body{
background: url("http://xylinux-10028272.file.myqcloud.com/picture.jpg") no-repeat;
position:center;
background-size: cover;
}
#content{
height: 500px;
font-size: 50px;
}
#num{
position: relative;
top: 50%;
width: 200px;
height: 200px;
margin: -100px auto;
}
a{
text-decoration: none;
}
a:link, a:visited{
color:#06B9D1;
}
</style>
</head>
<body>
<div id="content">
<div id="num">
<form name="test" method="post">
<h1><a href="javascript:document.test.action='year';document.test.target='_self';document.test.submit();" >2008</a></h1>
<input type="hidden" name="year" value="2009"></input>
</form>
</div>
</div>
</body>
</html>然後在中間的數字部分你就會發現存在一個表單：
[code] <div id="content">
<div id="num">
<form name="test" method="post">
<h1><a href="javascript:document.test.action='year';document.test.target='_self';document.test.submit();" >2008</a></h1>
<input type="hidden" name="year" value="2009"></input>
</form>
</div>點擊多次之後，比較一下不同的網頁的關系：
[code]<div id="content">
<div id="num">
<form name="test" method="post">
<h1><a href="javascript:document.test.action='year';document.test.target='_self';document.test.submit();" >2012</a></h1>
<input type="hidden" name="year" value="2013"></input>
</form>
</div>
</div>發現下面的數字比上面的數字小1，並且頁面顯示的數字為表單中上面的數字，而下面的數字為下一個頁面的數字，然後我們看一下最後一個2015的頁面：
[code] <div id="content">
<div id="num">
<form name="test" method="post">
<h1><a href="javascript:document.test.action='year';document.test.target='_self';document.test.submit();" >2015</a></h1>
<input type="hidden" name="year" value="2006"></input>
</form>
</div>
</div>發現下面的數字為2006也就是將要跳轉到2006。那麼我們嘗試著在網頁源碼裡面修改該數字為2016，然後重新提交：
神奇的事情發生了，結果進入了第二關：
【第二關】
這個。。。有圖片，有音樂。還是直接查看網頁源代碼吧：
發現3個可以下載的東西，我們依次下載下來。發現圖片並沒有什麼奇怪的地方。只能是音樂了，發現.3gpp後綴的音樂實際上就是我們網頁上放的音樂。那這個.eop文件呢？百度下，發現這個軟件：
之後用這個軟件打開.eop文件，可以看到琴鍵的變化對應著我們的鍵盤，我們記錄下每個鍵盤的子母就可以得到第三關的網址。進入第三關。
【第三關】
第三關很直接，一進去就可以看到，一段視頻，下面是一個文本框，裡面是一串01碼，不用說，解這些01碼的玄機就來自這段視頻裡，視頻主要內容是兩個不相識的年輕人因為偶然的原因而相識，相愛的故事，但是，感動並不能解決這道題，解題的關鍵還是在與兩個年輕人交流的方式，為什麼打著手電筒就可以進行信息交流，雖然視頻裡面卻有誇張的地方，但是現實中卻實是可以的。其實，足夠細心的話，就可以發現，在一開始字幕上面，就已經將玄機展示了，那就是字幕下面的點和橫線，通過百度，就可以發現其是那就是摩爾斯電碼，至此，解題的關鍵就已經出來了，下面重點就是對付下面的0，1碼了。
通過維基百科上面查找，就可以找到完整的摩爾斯電碼的信息，由於黨國的信息封鎖政策，導致大家不能科學上網,下面就將上面的信息貼過來：
有了碼表，仔細對照以下，就會發現，碼表上面的0代表摩爾斯電碼的“.”,1代表摩爾斯電碼上面的“-”，那就結了，會有部分人想著直接用手去解，但是那就體現不出我們的專業技能了，干嘛不寫一個程序來解呢？好的，下面貼出代碼：
[code]#!/usr/bin/env python
#coding=utf-8
__author__ = 'zhoupana'
#python3.4 and above
#mosi . --> 0 - -->1
#導入系統模塊
import sys
#定義編碼字典
drit={'A':'01', 'B':'1000', 'C':'1010', 'D':'100', 'E':'0',
'F':'0010', 'G':'110', 'H':'0000', 'I':'00', 'J':'0111',
'K':'101', 'L':'0100', 'M':'11', 'N':'10', 'O':'111',
'P':'0110', 'Q':'1101', 'R':'010', 'S':'000', 'T':'1',
'U':'001', 'V':'0001', 'W':'011', 'X':'1001', 'Y':'1011',
'Z':'1100',
'1':'01111', '2':'00111', '3':'00011', '4':'00001', '5':'00000',
'6':'10000', '7':'11000', '8':'11100', '9':'11110', '0':'11111',
'.':'010101',':':'111000', ',':'110011',';':'101010','?':'001100',
'=':'10001', '!':'101011', '-':'100001','_':'001101','(':'10110',
')':'101101','$':'0001001','&':'01000','@':'011010','+':'01010',
"'":'011110','/':'10010'，
' ':' '
}
#定義解碼字典
drit_reversed={}
#反轉編碼字典得到解碼字典
for key,value in drit.items():
drit_reversed[value]=key
#加密，並寫入文件
def EncodeReadFile():
#加密文件
encode=open("1.encode",'r')
#解密文件
decode=open("1.decode",'w')
#迭代整合文件
for string in encode.readlines():
print(string,end="")
for str in string:
try:
decode.write(drit[str.upper()])
decode.write(" ")
except KeyError:
pass
decode.write("\n")
#解密，輸出到文件到你中，並顯示在屏幕上
def DecodeReadFile():
#加密文件
encode=open("2.encode",'w')
#解密文件
decode=open("1.decode",'r')
#迭代整個文件
for string in decode.readlines():
#將讀取的一行用空格分隔開
result=Split(string)
for str in result:
try:
print(drit_reversed[str.upper()],end="")
encode.write(drit_reversed[str.upper()])
except KeyError :
encode.write(drit_reversed[" "])
print(" ",end="")
encode.write("\n")
print()
def Split(String):
ret=[]
j=0
for i in range(0,len(String)):
if(String[i] == ' '):
if(i == 0):
pass
elif(i == j):
ret.append(String[j])
else:
ret.append(String[j:i])
j=i+1
return ret
if __name__ == '__main__':
#EncodeReadFile() #加密
DecodeReadFile() #解密上面代碼使用的是python3.4標准來寫的，在python2.7裡面無法運行，請注意。
將網頁上面的代碼拷貝到名為1.decode文件裡面，然後運行：
出來了一串用等於好隔開的字符串，很多人可能要問，這又是什麼？還是百度以下把。
發現下面信息：
點我已經標示出來了，可以發現，使用的是QUOTED-PRINTABLE這種編碼方式，網上這種解碼網站特別多，推薦一個：bianma.911cha.com將上上面解出的內容铐進去，然後結果就出來了：
細心的同學可能會發現，QUOTED-PRINTABLE這種編碼方式和URL編碼方式的差別就在之間分割號的不同，所以將等於號換成百分號就可以直接通過URL將結果解出來了！結果就是最上面的文本格式裡面的內容:很高興你能到達這關，下一關的入口是：一八二點二五四點二四六點一五四。
至此，本關全部結束。進入第四關。
【第四關】
進入網址我們看到的是4張撲克牌K，這是什麼意思？
要我斗地主？好了，還是乖乖的先查看源碼吧。
但是什麼也沒有發現啊。沒辦法，將四張照片都下載下來看看，可是左看右看還是一張圖片啊，該不會在圖片內容中隱藏著什麼吧？那怎樣查看圖片內容呢？ 找個十六進制編輯器吧！
這些其實都可以，大家自己選擇由於我在Linux操作系統下熟悉了hexedit，就下載了一個hexedit來分析。沒辦法，一張一張來吧。陽光總在風雨後，機遇出現在第三張圖片，看看發生了什麼神奇的事情！
什麼！！難道這是一個rar壓縮文件，於是立馬修改了圖片的後綴，果然發現了…
再查看1.txt的內容，發現好像是一個與c語言有關的程序，但是看內容不是源碼啊，修改個.exe試試？結果出現了:
天哪！貪吃蛇，好吧，像我這種手殘黨，十分鐘之後……
得到 Important Message
VHUUEFUDIXQHU
然後以為得到了全世界，去提交，結果不對，這就尴尬了，那現在應該怎麼辦呢？ 沒辦法，還是
又回到最初的起點
，想想差了什麼？突然覺得如果撲克牌是為了隱藏文件，那為什麼一定要選K呢，而選擇了K為什麼又是方片K中才有文件呢，是不是還會有別的意思呢？
於是百度了一下撲克牌K
凱撒大帝？什麼意思？那和提交有什麼關系？前面貪吃蛇給了重要信息，好像是什麼串，最終發現了
那到底移多少位呢？寫個小程序跑下吧
[code]#include<stdio.h>
char source[13] ={'V','H','U','U','E','F','U','D','I','X','Q','H','U'};
int line = 1;
void findAnswer(int begin)
{
char test[27];
int i,j,k;
for(i = begin,j = 1;j <= 26;++i,++j) {
test[j] = 'A'+i%26;
}
printf("%2d: ",line++);
for(k = 0;k < 13;++k) {
printf("%c",test[source[k]-'A'+1]);
}
printf("\n");
}
int main(int argc,char *argv[])
{
int i;
for(i = 1;i <= 26;++i) {
findAnswer(i);
}
}一共26種結果如下
沒辦法就一個個粘貼，但是仔細看一遍發現只有第十個是有意義的，沒錯
FREEOPENSHARE
正是
Xiyou Linux Group
的口號，趕緊愉快的去提交
哈哈！長出一口氣，進入第五關
【第五關】
本小關的目的是讓大家了解規則。
本小關方格規模為3*3，左上角黃色格子為起點，右下角紅色格子為重點，頁面右側有一數字，表示當前所累加的數字之和。通過幾次嘗試之後，可以發現，從左上角開始，我們可以按下方向鍵或者右方向鍵來移動方格，直到到達右下角終點格子，路徑所累加的數字和若最大，則視為成功過關，否則失敗重新來過。
上一小關是3*3，總共只有 C(2, 4)=6 種可能(因為需要向下移動2步，向右移動2步，一共4步，所以是C(2, 4))，我們很容易可以心算出正確的路徑，但本關的規模是5*7，可能的路徑數有C(4, 10)=210種，沒有上一關那麼容易了。
我們發現我們嘗試的過程中，總會以當前位置附近的格子作為我們決定向右或者向下移動的選擇依據，這實際上是一種貪心的思想。但是，貪心有它的局部最優性，即，對於我們所參照的目標(當前位置附近的格子)，我們的選擇是最優的，但對於從起點到終點即全部方格而言，它並不一定是最優的。
舉個簡單的例子，你可能會因為當前位置右邊是30，下邊是100，而選擇向下移動，但如果30的右側有很多100呢，你會因為之前的一次貪心，而錯失了後面更好的選擇。
因為本小關規模也依舊不大，直接貪心思想嘗試，成功的概率也是很大的，但有想法的同學應該可以意識到這種方法的錯誤的地方，從而進行思考，想到正確的解法。
這就是設立本小關的目的。
本小關才是真正的重頭戲了，我們將規模設置為了12*20，可能的方案數為C(11, 30)=54627300，它也依舊不算大(其實還想更大的，只是因為屏幕有限)，所以我們將每個數字的范圍由之前的0~100改為了280~320，這樣，大家心算直接貪心成功的幾率就變得很小很小了。
仔細想想，不難發現，對於每個格子而言，能到達它只有兩種可能，就是上面和左邊。
還是舉個例子吧。
就拿3*3，來說，再大規模也是同理的。
15 12 6
35 61 95
53 22 58
我們要求從15到58的最大和路徑。
那麼對於58而言，它的上一步要麼是22，要麼是95，那麼最大的路徑肯定是15到22與95兩者較大的那條。
那麼如果我們得到下面兩個圖的結果，就可以得出我們想要的答案。
15 12 15 12 6
35 61 35 61 95
53 22
同理，他們兩者依舊可以分解，直至1*1。
這樣我們能夠提取出一個公式，令a[i][j]表示第i行第j列方格的數值，令dp[i][j]表示從起點到第i行第j列位置所能獲得的最大數值和。
則 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + a[i][j];
遞推式已得出，代碼就很好寫了。
[code]#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 25;
int dp
;
int a
;
char str[10000];
int main()
{
printf("%s", str);
int len = strlen(str);
int row, col;
row = col = 0;
int num = 0;
//將方格數據轉化為矩陣
for(int i=0; i<len; i++)
{
if(str[i] >= '0' && str[i] <= '9')
{
num = num * 10 + str[i] - '0';
}
else if(i > 0 && str[i-1] >= '0' && str[i-1] <= '9')
{
if(str[i] == ']')
{
a[row][col] = num;
num = 0;
if(str[i+1] != ']')
{
col++;
row = 0;
}
}
else if(str[i] == ',')
{
a[row][col] = num;
row++;
num = 0;
}
}
}
//動態規劃，按照轉移方程，進行迭代
for(int i = 1; i <= row; i++)
for(int j = 1; j <= col; j++)
dp[i][j] = max(dp[i-1][j], dp[i][j-1])+a[i][j];
printf("ans = %d \n", dp[row][col]);
//逆推回來，得到路徑
int i = row;
int j = col;
int k = 0;
while(i >=1 && j >= 1)
{
if(dp[i][j] == dp[i-1][j] + a[i][j])
{
str[k++] = 'D';
i--;
continue;
}
if(dp[i][j] == dp[i][j-1]+a[i][j])
{
str[k++] = 'R';
j--;
continue;
}
}
printf("start : ");
for(int p = k-2; p >= 0; p--)
printf("%c > ", str[p]);
printf("end\n");
return 0;
}
免試題原本在5.3就應該要結束的，但因為做題的玩家(姑且叫玩家吧)，不止大一的小鮮肉，還有高年級的道友們，所以為了讓大家玩得更愉快，臨時增加了本關。
本關乍一看似乎和5.3沒有什麼區別，但當你使用5.3的方法去移動時，發現到了右下角並不會結束。如果你仔細嘗試，才會發現現在方向鍵上和方向鍵左是可以按的了。也就是說，現在我們要從左上角走到右下角再走回左上角，即走一個來回，兩次路徑的方格值總和最大即通過(重復經過的格子只計算一次)。
首先，我們可以將題意轉化為從左上角以兩條路徑走到右下角，獲得經過的方格數值總和。
那麼，依照我們之前的那種思路，
我們令a[i][j]表示第i行第j列方格的數值，令dp[i][j][k][L]四維數組，表示第一條路徑到達(i, j)，第二條路徑到達(k, L)所經過的方格數值總和最大值。那麼顯然，對於(i, j)來說，有兩種可能即(i-1, j), (i, j-1)，同理(k, L)有兩種可能(k-1, L)和(k, L-1)，那麼對於(i, j, k, L)就有4種可能性。
用轉移方程描述就是
dp[i][j][k][L] = max(
dp[i-1][j][k-1][L],
dp[i-1][j][k][L-1],
dp[i][j-1][k-1][L],
dp[i][j-1][k][L-1]
) + (i != k || j != L) ? a[i][j]+a[k][L] : a[i][j];
查看代碼吧：
[code]#include <iostream>
#include <cstring>
#include <math.h>
#include <cstdio>
using namespace std;
const int N = 25;
int dp
;
int a
;
int fa[2][N*N] = {};
char ans[2][100];
char str[10000];
int main()
{
cin>>str;
int len = strlen(str);
int row, col;
row = col = 0;
int num = 0;
//將方格數據轉化為矩陣
for(int i=0; i<len; i++)
{
if(str[i] >= '0' && str[i] <= '9')
{
num = num * 10 + str[i] - '0';
}
else if(i > 0 && str[i-1] >= '0' && str[i-1] <= '9')
{
if(str[i] == ']')
{
a[row][col] = num;
num = 0;
if(str[i+1] != ']')
{
col++;
row = 0;
}
}
else if(str[i] == ',')
{
a[row][col] = num;
row++;
num = 0;
}
}
}
int n = col;
//動態規劃
for(int i=1; i<=row; i++)
for(int j=1; j<=col; j++)
for(int k=1; k<=row; k++)
for(int l=1; l<=col; l++)
{
int mx = 0;
if(mx < dp[i-1][j][k-1][l])
{
mx = dp[i-1][j][k-1][l];
}
if(mx < dp[i-1][j][k][l-1])
{
mx = dp[i-1][j][k][l-1];
}
if(mx < dp[i][j-1][k-1][l])
{
mx = dp[i][j-1][k-1][l];
}
if(mx < dp[i][j-1][k][l-1])
{
mx = dp[i][j-1][k][l-1];
}
if(i == k && j == l)
dp[i][j][k][l] = mx + a[i][j];
else
dp[i][j][k][l] = mx + a[i][j] + a[k][l];
}
cout<<"the ans = "<<dp[row][col][row][col]<<endl;
//逆推得到路徑
int cnt = 0;
int i=row, j=col, k=row, l=col;
while(1)
{
if(i == 1 && j == 1 && k == 1 && l == 1)
break;
dp[i][j][k][l] -= a[i][j];
if(i != k || j != l)
dp[i][j][k][l] -= a[k][l];
if(dp[i][j][k][l] == dp[i-1][j][k-1][l])
{
ans[0][cnt] = 'U';
ans[1][cnt] = 'D';
cnt++;
i--;k--;
}
else if(dp[i][j][k][l] == dp[i-1][j][k][l-1])
{
ans[0][cnt] = 'U';
ans[1][cnt] = 'R';
cnt++;
i--;l--;
}
else if(dp[i][j][k][l] == dp[i][j-1][k-1][l])
{
ans[0][cnt] = 'L';
ans[1][cnt] = 'D';
cnt++;
j--;k--;
}
else
{
ans[0][cnt] = 'L';
ans[1][cnt] = 'R';
cnt++;
j--;l--;
}
}
//輸出路徑
cout<<"load_one > ";
for(int i=0; i<cnt; i++)
cout<<ans[0][i]<<" > ";
cout<<"end"<<endl;
cout<<"load_two > ";
for(int i=cnt-1; i>=0; i--)
cout<<ans[1][i]<<" > ";
cout<<"end"<<endl;
return 0;
}參考鏈接：
朱新全
張明瑞
周攀
師毅
