第246章 Vigenre密码和国王游戏 (第2/2页)


    密钥k是一个字符串，，时，，iKi。

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

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

    当M的长度大于K的长度时，重复使用K。

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

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

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

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

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

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

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

    5分钟搞定代码，然后在中编制了10组测试数据，一一代入进行模拟计算。

    输出的结果与纸笔计算十分吻合。

    此题结束。

    由于linux系统区分大小写，所以江寒在解题的过程中，除了题目中有规定的输出文本等，程序中使用的所有变量等等，一律使用小写字母。

    接下来是第二题：国王游戏

    N个大臣排成一队，国王站在队伍最前方，每个人左右手上，分别写有一个数字。

    国王按照规则，赐予每个大臣一定数量的金币。

    每个大臣所能得到的金币数，等于排在该大臣之前所有人左手数字之乘积，除以其右手的数字，结果向下取整。

    问题是，如何调整大臣的顺序，才能让获得的金币最多的那个人，得到的金币尽可能的少。

    注意，国王始终站在队伍最前方。

    然后在输入数据说明中，有如下提示。

    对于20%的数据，有1≤n≤10，0
    对于40%的数据，有1≤n≤20，0
    对于60%的数据，有1≤n≤100；且答案不超过10^9；

    对于100%的数据，有1≤n≤1，000，0
    这道题的难度比第一题稍有提高，但也不算特别费劲。

    此题的坑点在于，输入的数据有可能很大，使用通常的编程方式，只能通过前40%的数据校验，想得高分，就必须使用高精度编程。

    解题思路就是穷举法。

    针对给出的大臣数N，以及给出的N 1组左右手数字a、b，计算每种可能的站位情况所对应的金币最大值，m3，……mk}中的最小值。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    对拍。