西邮Linux兴趣小组2017纳新免试题揭秘

声明

今年的免试题按照关卡顺序依次是由小组15级成员何攀、楚东方、宫展京、杜肖孟、王一妃同学精心准备的（鼓掌），每个人总结了一下自己负责关卡的解法，我这里整理了一下，给出一套完整的免试题详解，免试题通过方法不唯一哦，想分享的可以留言。文末附上小组前几年的免试题详解，感兴趣的同学可以参考着玩一下。Let’s go!

第一关

免试题链接：点此进入 ，进去之后会有如下页面映入眼帘：

首先，我们看到的是一段代码（运行结果是 11，代表着我们小组成立 11 周年）和一段关于 π 的视频，在欣赏完这曲美妙的钢琴曲后发现并没有什么其他的信息了，然后我们应该想到查看网页源代码（Ctrl+u 或 F12），然后会发现在网页源代码里有一个压缩包文件，如下图:

把这个压缩文件 XiyouLinuxGroup.zip 下载下来后，发现这个压缩包是加密的，然后我们应该想到这个密码肯定隐藏在这个网页的某个地方，这时候应该想起网页上的那段代码和视频，那这个代码的运行结果 11 与关于 π 的视频和那个压缩包的密码有什么联系呢？我们都知道 π 是一个无限不循环小数，所以密码不可能是 π ，然后,再联想一下那个 11，可以猜到密码应该是 π 的前 11 位，或者 π 的小数点后 11 位，试着输入一下，会发现密码就是 π 的前 11 位 3.141592653，解压完成后我们得到了这样一张图片:

这是我们小组的微信公众号，得到它后应该做什么呢？当然是关注了～

关注了之后呢，发现并没有什么过关提示，然后，我们再仔细看一下网页源代码，发现并没有什么可用的信息了，然后我们应该思考一下这个图片是不是有什么问题，用编辑器打开这个图片，这里以 vim 为例，发现文件头是没问题的，然后往下翻，会发现在文件尾有一些信息(可以在 vim 中执行命令 G 直达文件尾)，如下图:

发现这段 Unicode 码，可以用 shell 命令把它提取出来，如下图所示:

找一个 Unicode 在线转换工具将这段 Unicode 码转换为字符，如下图所示:

了解 linux 的同学应该很容易看出这是一个 shell 命令，然后该怎么办呢？当然是找一台装有 linux 环境的机器（包括各种 linux 的发行版本，虚拟机，服务器等），这里以 Fedora 25 为例，运行结果如下图所示:

得到了这个运行结果后该干嘛呢？在网页上似乎也没发现可以提交的入口，这时候我们应该想到前期得到二维码后关注的那个公众号，把这个结果发到这个公众号试试，看看有什么效果，如下图所示:

微信自动回复是不区分大小写的，所以输入小写字母也是可以的，然后得到了这段大写数字，将它转换一下会发现这就是通往下一关的IP: 112.74.212.172

Note:
   本关网页上的那段代码寓意西邮Linux兴趣小组成立 11 周年，主要考察大家的分析、联想能力，还有就是对 linux 命令的掌握情况（当然也有一点儿为我们小组公众号打广告的成分），这就是免试题第一关的详解。

第二关

链接：点此进入

第二关界面上是一首诗、一首歌、n和m。歌的名字是“给我一首歌的时间”，暗示着只有一首歌的时间答题。事实上在一首歌的时间过后，其数据就会刷新。

首先审查元素，在这一首诗的上下分别找到了两个网址，我们首先访问第一个（点此进入），发现其为一个矩阵相乘得到矩阵a的问题，但是只给了第一个矩阵的信息，并没有第二个矩阵的信息，只是给了提示第二个矩阵已经发给我们。

我们审查元素发现该网址上有一段JS代码，其向我们发送了一个名为 “Matrix_2.html” 的矩阵，我们利用浏览器上的Network进行抓包，找到了第二矩阵，发现第二个矩阵为一个100×100的蛇型矩阵。

利用Network进行抓包

通关以上步骤，我们已经得到了矩阵a。然后我们打开第二个链接，如果未翻墙的童鞋可能打不开，因为这个网址是由Google提供，需要翻墙才能访问，我们打开网页后发现其是一个公式：

现在目标很明确了，我们知道了a,n,m，又得到了公式，我们要做的就是计算得到结果。那么我们又遇到两个问题，一是n是一个非常大的数，如果一个for循环相乘的话是无法在规定时间内得到结果的。二是一个数的n次幂是一个非常大的数，long long 和 int 都无法存下。（python 、php等不要求变量类型的语言除外）

为了解决着两个问题，这里提供两个解决方案
针对第一个问题，我们利用快速幂，把时间复杂度从O(n)降为O(log(n))。

对于第二个问题，我们采用乘法和加法的取模公式：

(a+b)%m = a%m + b%m
(a*b)%m = ((a%m)*(b%m))%m

---

下面给出解题代码(C++)：

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#define MOD 1000000007
using namespace std;

typedef long long ll;
void FillMtrix(int matrix[][105],int num);

void  get_re (int num);
vector<int> v,re;
ll qpow(ll p,ll q)
{
    ll f=1;
    while(q)
    {
        if(q&1)
            f=(f*p)%MOD;
        p=p*p%MOD;
        q>>=1;
    }
    return f;
}
int a[105][105];
int t ;
int main() 
{
    ll n ;
    cout <<"please input the number n: "<<endl;
    cin >> n;
    int ha = 100;
    FillMtrix(a, ha);
    /*for (int i = 0; i < ha; i++)
    {
        for (int j = 0; j < ha; j++)
        {
            cout << a[i][j]<<" ";
        }
        cout << endl;
    }*/
    cout << "please input the Mtrix: "<<endl;
    for(int i=0;i<100;i++)
    {
        cin >> t;
        v.push_back(t);
    }
    get_re(ha);
    ll ans =0;
    for(int i=0;i<re.size();i++)
    {
        ans +=  qpow(re[i],n);
        ans %=MOD;
        //cout << re[i]<< endl;
    }
    cout << "the answer :"<<endl;
    cout << ans<<endl;
    return 0;
}

void  get_re (int num)
{
    for(int i = 0;i<num;i++)
    {
        int tt=0;
        for(int j  = 0 ; j < num ; j++)
        {
            tt += v[j]*a[j][i];
        }
        re.push_back(tt);
    }
}




void FillMtrix(int matrix[][105],int num)
{
    int x = 0, y = 0;
    int val = 0;
    int curr_x = num, curr_y = num;

    while(x < curr_x && y < curr_y){

        //填充一行
        for(int i = y; i < curr_y; ++i){
            matrix[x][i] = ++val;
        }

        for(int i = x+1; i < curr_x; ++i){
            matrix[i][curr_y-1] = ++val;
        }

        for(int i = curr_y-2; i > y; --i){
            matrix[curr_x-1][i] = ++val;
        }

        for(int i = curr_x-1; i > x; --i){
            matrix[i][x] = ++val;
        }

        x++;
        y++;
        curr_x--;
        curr_y--;
    }

}

得到答案后，我们就来到了第三关，恭喜哦～～

第三关

链接：点此进入

首先，我们看到了一大段01串，但是却没有任何有效的信息。所以还是老套路，先看看源码里面有什么，我们发现了一个压缩包，解压后得到了一个a.out文件，这是linux下的可执行文件。执行看看:

发现需要参数，可是参数是什么呢，联想到我们一开始看到的01串，可能这01串就是提供给我们的参数，试着将前面几个字符转换成ASCII码，得道 U ，作为参数运行一下。

发现我们的思路是正确的，全部转换完成后如下

输入发现参数还不够，但我们得到了一条信息，png这是图片的一种格式。我们想想哪里还有图片？我们再回到这一关的入口，发现还有一个小组LOGO，按照套路来打开图片编码发现没有什么异常，那么再仔细观察一下这个图片，我们发现书上的字很突出(仰望星空，脚踏实地)，这是在提示我们什么？我们发现企鹅并没有仰望星空，到却在它的脚下发现了两段英文字串。

这会不会是第二个参数呢，试一下。

发现参数正确，我们得到了最后一个参数的提示，又是一大段的正方形01串,看起来好像是个二维码，可是我们该怎么转换呢？这里提供几种思路:
1. 碰到1输出黑方框，0输出白方框
2. 可以采用execl画图的方式
3. python生成二维码

最后我们得到了一张二维码,扫完后得到了第三个参数CRBRKY++（如果扫不出来就反色一下二维码）

最后得到了密钥TXSRBSJ，括号内是AES，我们百度一下发现是一个加密算法，可是没有密文。再联想一下参数可能就是密文（毕竟我们没有见过这样的参数），我们找个在线解密网站试一下。

果然，解密后我们得到了一个网址，这个就是下一关的入口啦。

第四关

链接：点此进入
  

来到第四关，我们可以看到是一个非常炫酷的界面，会吸鼠标。上面有两行英文：more than one picture! 下面有一个 <---Go---> 是一个链接，我们点一下，下载了一个图片，有10.4M，这个时候就感觉到有点不对劲，一般图片没这么大。

图片是一张海伦凯勒的假如还有三天光明。我们用一个带GUI的工具以十六进制形式打开这个图片，看这个图片里面有什么玄机。这里我用ghex这个工具。

拉到最后，显示上面是一个压缩ZIP文件，那么我们直接改下这个文件的后缀为.zip，如图

解压这个压缩包，发现需要密码，那么密码在哪里找呢？想想网页上提示 more than one picture! ，那么除了还有一个压缩包外，还有其他什么东西吗？或者我们直接在这个图片编码中找一下这句话吧。

果然，图片中隐藏了这句话，而且我们发现下面的编码是.jpg格式的图片开头，那么下面也是一张图片喽，它被上面这张图片覆盖了，我们把上面这个图片编码删掉，那么这个图片就是展现出来。所以我们把第二章图片前面的编码都删掉，然后保存文件。再看刚才那张图片我们发现变成了下面这样：

这是什么鬼东西，再想想我们刚开始下载的那张图片还没有利用呢啊，会不会和这个图片有关系呢？我们知道海伦凯勒是个盲人，那么这个会不会是盲文。。。我们在网上搜一下盲文对照表，发现果然是这样的。我们可以对照一下，得出这个图片中的盲文表示：l2i0n1u7x，这应该就是那个压缩包的密码，我们试一下，果然成功解压，得到一段音乐。

非常好听的歌《模特》，文件名字翻译过来是请带上耳机（听力好的同学可以直接外放，能听出来左右声道不同，还会有滴答声），提示戴上耳机，可以联想到是不是左右声道有问题，那么我们就来看一下吧。

这里用audacity 打开，可以观察到左声道没问题，下面右声道看起来有几段和其他的明显不同。我们把上面的声道关闭，只听下面的，发现到音乐高潮的时候变成了滴答滴答的声音，这就是摩尔斯电码啦，我们放大下面的频谱，如图：

在网上找到摩尔斯电码对照表，然后把这四段对应的字符找出来，拼成一块发现是个网址：www.tanswer.org/sequin，恭喜你通关啦，这就是下一关的入口。

第五关

链接：点此进入

第五关作为整个免试题的最后一关，主要考察点是算法的图论方面。接下来详细介绍一下第五关的通关攻略lol，首先映入眼帘的是一些星球的连线。

相信有点图论基础的同学此时心里会大概有个方向了吧，页面上有个提交按钮还有一个start:1 end:4的提示告诉你起始点为1目标点为4。页面上暂时没有什么其他的有效信息，好在点比较少，我们可以先一个一个试一下。

对于给定的起始点和目标点来说，我们有以下四种路径：
1：1->2->4
2：1->3->4
3：1->5->4
4：1->6->4
这四条路径权值和分别为：
1->2->4 ：2 + 3 = 5
1->3->4 ：3 + 4 = 7
1->5->4 ：4 + 5 = 9
1->6->4 ：5 + 6 = 11

我们分别尝试这四条路径，发现提交1->3->4这条路径时页面跳转了，进入了第五关的第二个页面。

好吧，我相信在看到第二个页面的时候很多同学的内心是拒绝的O。。。其实我的内心也是拒绝的。。。然而再怎么吐槽这个图出题人也是硬着头皮画的你们也得硬着头皮做。。。ORZ

一开始拿到这个图可能会有些头大，会发现有个残忍的倒计时，但这个时候需要你们理清思路回顾以下上一个页面。在上一个页面中，我们选择1->3->4 这条路径后进入到这个页面，根据上面每条路径权值和的分析，我们发现1->3->4 是所有路径中权值和第二小的的路径。思考到这里，第五关的通关规则就很清楚了，需要你找到从起始点到目标点的次短路径。

但是这么多星球，这么多连线，自己画出来十分的麻烦，这时我们可以延续前四关的优良传统——审查元素。

这么明显的结点信息我想瞎子都能看到吧。。。赶紧先保存下来。

大概看了看，能够发现总共有50个点，97条边，每条边的权值为分数。
现在图信息有了，通关规则也有了，剩下的就是解题了。倒计时为30s，这意味着你肯定不能手动计算，还是乖乖谷歌下次短路算法吧。

---

下面给出代码：

#include <iostream>
#include <string.h>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define N 205
#define MAX 0x03fffffff
using namespace std;
double Metrix[N][N];
double dist[N];
int vist[N];
int path[N];

struct edge
{
    int s,t;
    double cost;
}E[N];

int Dijkstra(int s,int t,int NV)
{
    int u=s,v=t;
    for(int i=1;i<=NV;i++)
    {
        dist[i]=MAX;
        vist[i]=0;
    }
    for(int i=1;i<=NV;i++)
    {
        path[i]=s;
    }
    dist[u]=0;

    for(int i=1;i<=NV;i++)
    {
        double min_value = MAX;
        for(int j=1;j<=NV;j++)
        {
            if(vist[j]==0&&dist[j]<min_value)
            {
                min_value=dist[j];
                u=j;
            }
        }
        vist[u]=1;
        for(int j=1;j<=NV;j++)
        {
            if(vist[j]==0&&dist[u]+Metrix[u][j]<dist[j])
            {
                dist[j]=dist[u]+Metrix[u][j];
                path[j]=u;
            }
        }
    }
    if(fabs(dist[t]-MAX) < 0.000001)return -1;
    return 10;
}

void SP2th(int s,int t,int NV)//NV为节点数
{
    int flag=Dijkstra(s,t,NV);//求最短路
    printf("%lf ", dist[t]);
    if(flag==-1)
    {
        printf("0");
    }
    else
    {
        float min_SP=MAX;
        int u=s,v=t,arcNum=0;
        while(v!=u)//保存最短路到E[i]
        {
            E[arcNum].s=v;
            E[arcNum].t=path[v];
            E[arcNum].cost=Metrix[v][path[v]];
            arcNum++;
            v=path[v];
        }

        for(int i=0;i<arcNum;i++)
        {   //删除E[i]
            u=E[i].s;
            v=E[i].t;
            Metrix[u][v]=Metrix[v][u]=MAX;
            flag=Dijkstra(s,t,NV);//重新计算最短路
           // printf("  %lf-=-=\n", dist[t]);
            if(flag==-1)
            {
                printf("0");
            }
            else
            {
                //OutPath(s,t,NV);
                if(min_SP>dist[t])min_SP=dist[t];
            }
            Metrix[u][v]=Metrix[v][u]=E[i].cost;

            int u = s, v = t;
            while(v != u){
                printf("%d->", v);
                v = path[v];
            }


            printf("%d  %lf\n",s, dist[t]);

        }
        printf("%lf",min_SP);
    }
}
int main(int argc, char * argv[])
{
    int m,n;//n为节点数，m为边数
    int ss = 0;
    int tt = 0;
    ss= atoi(argv[1]);
    tt = atoi(argv[2]);
    freopen("./CASE.txt", "r", stdin);
    cin >> n >> m;
    int s,t;
    int aa, bb;
    double c = 0.0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j)
            {
                Metrix[i][j]=MAX;
            }
            else
            {
                Metrix[i][j]=MAX;
                Metrix[j][i]=MAX;
            }
        }
    }
    for(int i=0;i<m;i++)//每条路的代价
    {
        cin >> s >> t >> aa >> bb;
        c = aa /(bb * 1.0);


        if(c<=Metrix[t][s])
        {
            Metrix[s][t]=Metrix[t][s]=c;
        }
    }

    SP2th(ss,tt,n);//求s->t的次短路

    return 0;
}

30秒的时间真的是有点紧张，不过如果你是用程序的话还是可以来得及的，我们提交下试试

看样子是过咯～至此2017年免试题揭秘到此结束。

结束的话：
通关只是目的之一，免试题并不是难住所有做题的人才高兴，我们其实想让更过的同学参与进来，希望大家能够在做题的过程中学到新的、有用的知识，激发大家对技术研究的兴趣。加油吧少年！

参考链接：
2013 Linux 兴趣小组免试题解析
2014 Linux 兴趣小组免试题解析
2015 Linux 兴趣小组免试题解析
2016 Linux 兴趣小组免试题解析