顶点小说网 > 重生学神有系统 > 第246章 Vigenère密码和国王游戏
    江寒按了一下电脑电源按钮,很快显示器上出现了noilinux的启动界面。

    这就必须“赞”一下了,往年都是用虚拟机进入linux的,今年改成原生系统了。

    这样一来,系统的启动和运行速度,起码要提高一倍以上。

    实际上,有些省份目前还是windows和虚拟机linux并行,选手自行选择趁手的操作系统。

    合江省这次竟然走在了全国前列,率先淘汰了大众熟悉的windows……

    足足等了三十多秒,终于进入了linux桌面。

    江寒先把桌面分辨率等环境参数,调整成了最顺手的设置。

    然后按下【alt+ctrl+t】,调出终端,用“ls”命令查看了一下。

    赛组委果然没有预先建立比赛文件夹,这样就只能自己动手了。

    江寒按照监考教师下发的参赛说明,使用“mkdir”命令建立了一个文件夹,命名为【jianghan】。

    接下来,他又在终端中输入【】,启动了代码编辑器vim的ide界面,然后按“i”键进入插入模式。

    这样就可以键入代码了。

    这次比赛仍然可以在c、c++、pascal三种程序设计语言中任选一款。

    三种语言各有特点,c语言执行效率最高,pascal语法简单,但稍嫌刻板,好处是不容易犯低级错误,c++则更加适合复杂程序的设计。

    江寒毫不犹豫地选择了最为熟悉的c++。

    首先完成一个测试代码。

    功能很简单,就是在标准的“helloworld”基础上,增加了一个从1加到100的循环程序,然后将结果输出到屏幕上。

    江寒编辑完代码,稍微检查了一遍,排除了可能存在的语法错误,然后按“esc”键,退出插入模式,再输入“wq”存盘退出。

    接下来,回到终端中,输入命令行指令:【g++-otest】,回车。

    这样,g++编译器就开始工作,将编译成了可执行文件test。

    编译过程中,如果有错误,就会提示出来。

    但江寒这个测试程序十分简单,并没有犯任何小错误,一次就通过了编译。

    接下来,就可以输入【./test】,来执行生成的可执行文件了。

    稍微观察了一下,确认程序可以正常运行。

    这样系统的检测和调整就初步完成。

    接下来,进行一些进阶的设置。

    江寒用【vim~/.vimrc】命令,再次打开vim界面,并加载了配置文件vimrc。

    然后修改了一下其中的几个参数,将vim编辑器的操作模式,调整成了最顺手的状态。

    接下来,在自己的比赛文件夹中,创建两个文本文件:和。

    再修改测试代码,为其增加文件输入输出功能,并添加对头文件的引用,使其能操作和。

    再次调试正确后,就得到了一份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分钟搞定代码,然后在中编制了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=中的最小值。

    由于n个大臣共有n!种站位,所以一旦n足够大,计算量将是非常恐怖的。

    这道题一共10个检查点,每个检查点10分。

    比赛对于程序运行时间的限制,是每个检查点不超过1秒。

    对于运行空间的限制,是每个程序使用的内存,不得超过128兆。

    无论在哪个检查点超时或者输出错误,都会扣掉该点的分值。

    计算机打分的时候,一般会输入强弱不同的10组测试数据。

    遇上小点的数字,比如本题中前20%的数据,只要程序没有逻辑错误,基本都能通过测试,拿到分数。

    但当n稍微大一点的时候,使用暴力搜索算法,很可能会超过1s的时限。

    所以,一定要找出规律,对输入的n组a、b进行预处理。

    江寒在纸面上推演了一下,很快得到了一个猜想:当大臣们按axb的积升序排序时,得到的序列就是最优的方案。

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

    第一步,排序,求出最优方案时的队列,第二步,计算该情况下的m值。

    毫无疑问,这个算法的效率远比暴力搜索更高,其运行时间取决于使用的排序算法的时间复杂度。

    江寒先编制了一个最朴素的暴力搜索算法,测试了一下,验证程序没有逻辑错误后,另存了一份。

    然后又按照改进后的思路,修改了一下代码,用快速排序整理队列,然后计算m值。

    接下来就是比较好玩的东西了。

    对拍。