有趣又有用的信息学竞赛

时间如水般悄然流逝，身旁的一切或许早已不再似从前般模样。在这个科技迅速发展的今天，高端电子产品的层出不穷，我们不得不承认这一切的一切都与计算机有莫大的关系。我们都知道计算机很万能，但其实我们对计算机的了解可能仅仅只停留在外观或者是性质。计算机这个事物所带来的并不仅仅是画面激烈的游戏，而是充满理性思维美的一个新的世界。  ### 算法 算法其实就是解决问题的方法，放在计算机里就是用程序解决问题的方法。 举个并不那么确切的例子： **1+2+3+4+……+n-2+n-1+n=？** 或许大家小学就知道怎么做这道题 方法一 **一个一个慢慢加，答案肯定能算出来** 方法二 利用公式 **(1+n)n÷2** 对于同一个问题，你可能有很多种解决方案，当然不同的解决方案优劣不同，比如例子中的方法一，你可能算着算着会出错，或者是心态爆炸。一般人肯定更愿意采用更快，更简单的方法来解决问题，对于此问题中也就是方法二。可见算法是有优劣性的。  计算机运算速度很快，但肯定有上限，大概也就那么4——6亿次每秒，或许你会说，反正都那么快，那还管什么算法优劣性，这里我们又要举个例子了。 就把n个不同身高的人从低到高排序好了 第一次你需要在n个人里面找最高的 第二次你需要在(n-1)个人里面找第二高的 第三次你需要在(n-2)个人里面找第三高的 以此类推…… 我们来算算当n=10000000(1000万)时，一共需要比较几次的身高。 第一次也就那么10000000次 第二次也就那么9999999次 第三次也就那么9999998次 就算它最后一次不用比较好了 其实总共也就那么(10000000+2)*9999999=100000009999998次（约10亿亿次） 那么计算机需要做多久呢？——也就那么2天 我估计下载游戏可能会有人等2天，这种无聊的东西，没有人会愿意等个2天…… 但是已经有些很强的人想出来一些算法，比如快速排序，它可以在估计也就那么NlogN次完成排序。同样是n=1000万的数据下，它只需要不到10秒的时间。计算机并没有变快，都是一样的速度，所应用的算法不同，解决问题的效率完全不一样。  想出这么强的东西，像我们这种普通人肯定干不了。 并不是这样，就是专门有一个竞赛叫OI（Olympiad in Informatics 信息学奥林匹克竞赛） ### 信息学竞赛 我想普通人应该听都听过，高中生应该都听过吧，毕竟五大竞赛中还是有信息学的，搞不好就有些四大竞赛的学校了【瑟瑟发抖】。 ——学信息学啊，好羡慕啊，每天都可以玩游戏！ ——学信息学啊，那你们真舒服啊 ——学信息学的啊，每次月考都是垫底。  我想这些并不那么妥当的言论，应该都源自于不了解吧。信息学，一门超级神秘的学科，几乎每个人都知道其他四大竞赛的选拔方式，唯独信息学考试的方式一直保密，延续至今【滑稽】信息学考试到底怎么考的？电脑又不会算错答案，怎么算分呢？是不是程序代码越长，分数就越高啊？ 又要举个并不那么恰当的例子了 荒野求生都看过吧？  贝爷威武！ 如果把你扔到那个鬼地方 你能活下来吗？ 诶，那你为什么不能活下来？ 原因就是你对现有资源的利用程度和自然环境的险恶程度 同样是用代码写出来的程序，同样是拥有海水藤蔓阳光木头的人 有些程序就满分，有些程序就0分；有些人活下来了，有些人死了。 同样的道理，如果刚开始自然环境很好，不管你会不会什么高端求生技能，你都能活下来一天。如果第一个测试数据的数据量很小，不管你是不是使用了高端算法，你的程序都能算出答案。 但如果自然环境慢慢险恶起来，你就需要一定的求生技能了，不然你就要面临死亡的危险。 但如果测试数据的数据量慢慢大起来，你就需要想出更快的算法，不然你的程序就要面临掉分的可能。  程序就是在孤岛上的人，测试数据就是海啸地震火山什么的。通常都要求人在孤岛上存活几个月，每个月的环境邪恶是不一样的，你多活一个月，分数就多一点，一般环境的邪恶程度是逐渐提高的。换个说法就是，每个测试数据的数据量大小是不一样的，你多过一个测试点，分数就多一点，一般测试数据的数据量是逐渐提高的。说白了，信息学竞赛就是写出要在各种巨大或者刁钻的测试数据下都能做出正确答案的程序。  讲到这，我想提一下信息学与其他学科和生活的关联性 有一次我去参加婚宴，主持人为了活跃气氛玩了一个小游戏“我在卡片上写一个数，你们上来猜，我会告诉你大了还是小了，猜对的人可以拿走红包里的10块钱，这个数不超过1000”  我当时看到很多人瞎猜…… 其实这是个肯定赚的游戏，我们不妨每次猜中间那个数，根据“大了”还是“小了”每次都可以忽略一半的答案可能存在的范围，运气最差10次就能猜出答案，因为每次忽略一半范围2^10=1024>1000，肯定血赚【无奈】 这种方法对应的就是信息学竞赛中的二分答案算法 出去旅行，旅行箱带不回我买的所有东西，怎么办，那我只能选几个东西装，这些东西都能塞进去并且价值和最贵。  不妨设F[i][j]是前i个物品占用体积为j能达到的最大的价值。w[i]是第i个物品的价值,v[i]是第i个物品占用的体积。 对于每一个F[i][j]=F[i-1][j-v[i]]+w[i]; 解读一下这个算式就是，假设每次一定要把当前物品装进箱内，我们肯定希望箱内剩余体积足够，并且箱内已经占用体积所拥有的价值最大。每次都需要最大，最大的最大的最大……，这样下去，就是最后的答案了，讲的专业点就是 满足最优子结构。 这个问题是信息学竞赛中典型的背包问题，所应用的算法是运筹学的一个分支叫动态规划的算法  看图，这是函数图象，最高点就是最大值，如果我们要求这个最大值，怎么求？解决这个问题的算法叫模拟退火。模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却。加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。 ——摘自360百科 在寻找最大值的时候，我们可以以某种概率接受这个当前最大值，毕竟从函数图象上来看，当前最大值不一定是最后的答案。这个概率怎么算出来呢，以粒子在温度T时趋于平衡的概率e-ΔE/(kT)，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。就以这个概率接受当前最大值。  这个算法是不是或多或少和物理有点关系呢？ 咳咳，讲到这，不知道你们对信息学有没有了解了一点呢。 如今人工智能，机器学习等高端科技领域的不断发展，有关计算机方面的研究需要也在不断增大，或许信息学竞赛就这么应运而生了。 最后的最后还是不得不提一下，每个竞赛都是很辛苦的，学科平等真的很重要啊QAQ