2013 2014 2015 2016 Xiyou Linux Group 免考试题揭秘
首先给出原来几届的免试题解析链接：
2013 Linux 兴趣小组免试题解析
2014 Linux 兴趣小组免试题解析
2015 Linux 兴趣小组免试题解析
目前2016 Linux 兴趣小组免试题还在线，大家有兴趣可以玩一玩。2016年的免试题是由14级成员朱新全、张明瑞、周攀、杨博东、师毅五位同学出的。感谢他们。下面我们进入2016年的免试题揭秘。
这篇文章只是将出题几位同学整理的解析整合了起来，文章最后会给出原文出处。
【第一关】
当打开免试题链接的时候，大家看到了这样一个页面：
毫无疑问点击START，当你还想着和去年一样图片里面含有一些东东的话，那么你可能得走一些弯路了。
点击START进去之后会看到这样一个页面：
然后发现这个简单的页面只有中间的数字可以点击，点击多次之后就会发现你进入死循环了,2006=>2007=>2008……2015=>2006=>2007……
遇上这样的情况我们首先看一下网页的源码:
<!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>然后在中间的数字部分你就会发现存在一个表单：
<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 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的页面：
<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代表摩尔斯电码上面的“-”，那就结了，会有部分人想着直接用手去解，但是那就体现不出我们的专业技能了，干嘛不写一个程序来解呢？好的，下面贴出代码：
#!/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
凯撒大帝？什么意思？那和提交有什么关系？前面贪吃蛇给了重要信息，好像是什么串，最终发现了
那到底移多少位呢？写个小程序跑下吧
#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];
递推式已得出，代码就很好写了。
#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 25;
int dp[N][N];
int a[N][N];
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];
查看代码吧：
#include <iostream>
#include <cstring>
#include <math.h>
#include <cstdio>
using namespace std;
const int N = 25;
int dp[N][N][N][N];
int a[N][N];
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;
}参考链接：
朱新全
张明瑞
周攀
师毅