重生学神有系统

    至于想要保送清北，也不是完全没机会，拿到国赛前几名，基本就没问题了。

    当然，如果在省赛中可以拿下550分，甚至更高的分数，那又另当别论。

    对于那样出类拔萃的特长生，就算是最顶级的高校，也难免要加以关注，甚至网开一面，破格签约。

    随便聊了几句后，高俊德说起时间问题。

    按照比赛规程，复赛一共两天，每天8点半开始，12点结束。

    每天3个半小时，只考3道题，所以只要不卡壳，时间一般是没问题的。

    但高俊德知道江寒有个坏习惯，喜欢提前交卷，所以特别叮嘱:“不管你答得好赖，给我坚持到12点整，多测试几遍程序，早交卷又不给你加分。”

    江寒叹了口气:“可我今天不光这一件事啊。”

    &nb




第246章 Vigenère密码和国王游戏
    江寒按了一下电脑电源按钮，很快显示器上出现了noilinux的启动界面。

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

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

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

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

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

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

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

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

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

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

    这样就可以键入代码了。

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

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

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

    首先完成一个测试代码。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    再次调试正确后，就得到了一份c++模板代码。

    一会儿比赛正式开始，只需要在模板的基础上，进行一些修改和填补就可以了。

    这些都搞定之后，还剩下大约15分钟时间，比赛才能正式开始。

    江寒在vim中随便输入了几个小程序段，快速排序、堆排序、二分查找……进行赛前热手，以提升手感。

    8点20分，监考人员通知大家登陆ftp服务器，用公用账号和密码下载试题压缩包。

    江寒只用了30秒，就把试题压缩包下载到了自己的桌面上，并解压到了一个文件夹中。

    随后依次点开3道试题的说明文档，认真查看了起来。

    只用了10分钟，他就将3道题都看完一遍，并理清了解题思路。

    然后按照题目难度，排了个序。

    巧的是，三道题的编号和难度系数一一对应。

    当然这是对于他来说，换个人看，很可能觉得第2题才是最难的……

    江寒在【jianghan】文件夹里，创建了三个子文件夹，按照要求，分别命名为【vigenere】、【game】和【drive】，一会儿为各个题目编写的代码，就分别存放于对应的文件夹中。

    江寒先看第一题:密码。

    这是一个密码学问题，加密规则很简单。

    密钥k是一个字符串，，时，，i?ki。

    ?是一个规则表，列，每一行代表一种字母替换方式，第一行从a到z顺序排列，第i+1行是第i行循环左移1个字符得到。

    ?运算不区分大小写，加密结果套用明文的大小写格式。

    当m的长度大于k的长度时，重复使用k。

    问题:给出密钥和密文，求原本的明文。

    如果让江寒给这道题的难度评级，大约只肯给出1星。

    这么简单的题目，约等于白给。

    解题思路十分明确，找出加密规则?的数学描述，然后使用?的逆运算，代入密钥k和密文c，求出明文m。

    如果实在不想麻烦，也可以将规则表建立成一个字符数组，然后反向查表。

    可以说，只要认真训练过的选手，这道题没理由会丢分。

    江寒迅速在草稿纸上，将流程图画了出来，然后编写c++代码。

    &nbs



第247章 对拍、Day1第三题
    没错，刚才的猜想是凭直觉和少量笔算搞出来的。

    要想验证自己的猜想，除了数学证明，最实用的方式就是对拍。

    所谓对拍程序，通俗的说法，就是数据比较器。

    方法很简单。

    将穷举暴力搜索版本的代码，编译成可执行文件a；

    将运用了猜想，优化后的代码编译成b；

    然后编写一个随机数据生成器，命名为rand；

    接下来，就可以制作对拍程序了。

    代码的主体是个有限次的循环。

    循环体内部，核心部分是几个system函数。

    先调用“./rand“生成随机数据，存入s.in，再分别调用a、b，读取s.in，输出a.out和b.out两个文本文件。

    最后调用“.out“，进行比较。

    如果发现两个文本文件不一致，则说明优化后的程序有问题，于是提示错误信息以及出错原因。

    这就是对拍，号称最强的调试办法，比gdb之类的调试工具好用多了。

    江寒写完对拍之后，设了一个60000次的循环，花了2分多钟跑完一遍。

    结果没有输出任何错误信息，这表示自己的猜想是完全成立的。

    下一步，就该把优化后的代码扩展到高精度了。

    这一步对很多选手来说，都是个难点，很容易大意之下，写漏一些条件。

    比如位数的最大值处理得不好，或者犯下其他的小失误，就会导致运算出bug。

    倒也不一定完全不能运行，只是碰到特殊数据时，可能会得出不正确的输出。

    运气好的时候，也能正常得分，运气差一点，可能就会丢分了。

    高精度运算的基本原理，是模拟手工列竖式计算，其中要考虑数位对齐和进位、借位处理。

    这种代码在网上有的是，但运算效率上，那些比较常见的代码，就有点不敢恭维了。

    江寒在刷《noip宝典》的时候，自己研究出来了一种高精度算法，可以说是不传之秘，比网上能找到的示范代码，要精简和巧妙很多。

    在这道题里，江寒要做的就是模拟手算高精度乘除法。

    如果不打高精度，那么最多仅能满足40%的数据要求。

    这道题满分100，能看懂题目，并写出暴力搜索算法，就能20分。

    能发现规律，写出快速排序，就能得到40分。

    对于实力有限，有自知之明的选手，做到这里就可以收手了。

    只有那些对自己足够自信，且能熟练编写代码进行高精度运算的人，才会继续改造算法，以冲击高分。

    高精度的乘法好写，除法就稍微有点难度了。

    这里又有两种选择，一个是写高精除高精，满足100%的输入数据要求。

    要么就退而求其次，被除数为高精度，除数为单精度，这样也可以满足至少60%的输入数据要求。

    写对高精除以单精，能得60分，写出高精除以高精，才有机会得到满分。

    但高精除以高精，是相当复杂的，一旦写错、写漏了条件，说不定反而得不偿失，连60分都得不到。

    所以，是保证到手60分，还是冒着浪费时间的风险，冲击一下满分

    对于其他人来说，这当然是个艰难的抉择，但对于江寒来说，根本无需纠结。

    反正时间也有的是，当然是选择后者了。

    江寒花了大约半个小时，写出了双高精除法的版本，并调试通过。

    然后设计了几组极限数值，代入进去运算，结果与笔算结果完全一致。

    边界条件没问题，这个程序出问题的几率就相当低了。

    倒也不是不能用系统作弊。

    做出爆搜程序后，可以通过20%的校验点，系统就提示了一次获得“学以致用”积分。

    运用了猜想，改为快速排序后，系统再次提示，获得了“学以致用”积分。

    改成高精度后，系统也有获得更多积分的提示。

    这说明，江寒对程序做出的每次改进，都能使其通过更多的校验点。

    但系统的帮助也只能到这里了，只能据此判断出，每个步骤中的程序，都是可以得分的，却无法判断出是否能得到满分。

    江寒只能依靠自己丰富的编程经验，尽可能保证程序无bug。

    搞定了前两道题后，时间已经过去了1个半小时。

    剩下的两个小时，全部交给最难的第三题。

    题目是《开车旅



第248章 需要对答案吗？
    预处理的方案很多，但各有利弊。

    比如，在这道题中，如果使用线段树来做预处理，需要维护三个值:区间内最小值、最大值、数的个数。

    这种办法有个缺点，当hi的值很大时，有可能会内存开销过大，导致空间超限。

    根据规定，程序可以使用的内存只有128兆，一旦使用的内存超出限制，则整道题0分。

    为了解决这个问题，就需要进行离散化操作，平添难度。

    江寒通过分析，综合比较、权衡了一番后，选择了比较保险的双向链表模拟算法。

    相比线段树，双向链表不需要离散化，但是细节比较多，调试起来会稍微麻烦一点。

    江寒自然不怕这点麻烦，一个是他对双向链表掌握得很好，二来……早上吃那么多东西，就是为了用在这种地方的。

    只要舍得全力开动脑力，编写起这种复杂度的代码来，只是小意思。

    还剩下一个半小时，时间上是完全够用的。

    对输入数据进行了预处理之后，接下来就可以寻求题目要求的解答了。

    这一步，可以用“倍增法”进一步提速，这样就可以保证，在很短的时间内算出答案，避免时间超限。

    由于答案数字很大，这道题也要用高精度来处理一下。

    但和第二题又有点不一样，这道题的精度压力，其实并没有那么离谱，完全可以尝试采用longlong（对应着4）数据类型来解决。