nbhkdz.com冰点文库

学军中学Crazy Land 模拟赛题解

时间:2012-11-22


Crazy Land 模拟赛
By crazygirl 猫和老鼠 Tom and Jerry
枚举较短两边的和,Tom 的路线(如果合法的话)一定是走在了一条最长边的相 邻两面上(即一定为 sqrt(a2 + (b + c)2)同时 a > b 且 a > c) ,这样就可以方便的计 算了。 计算 1 到 n 的平方和可以使用公式 注意答案需要使用

long long 或 int64 这题的想法比较常规,程序难度也不大,应该较容易拿下。

双城记 A Tale of Two Cities
由于是求最大值,显然可以贪心 对于 1-n 的情况显然所有小于 n 的一半的奇数都可以放入 A,那么全部放入 A, 对应的放入 B,ans 增加[n / 4]*2 剩下的偶数均为 4n+2 形式 我们用 f(x) = (x + 2) / 4 将剩下的偶数变为 1-n 形式, 同时对应法则变为 x 对应 2x, n 变为[(n + 2) / 4] 同理可以将所有小于或等于新的 n 一半的奇数和对应的数全部取出,ans 增加[(n + 2)/4]*2,最后剩下的偶数为 4n 形式 类似转化后对应法则稳定变为 x 对应 2x,n 变为[n / 4] 每一次 n 都在变小,最后 n = 1 时停下 需要高精度(不写高精度 80 分,鉴于是联赛模拟部分分就给高点了) ,并且需要 压位(不压位会 T 一个点) 。 正确性证明就不具体给出了,可以用抽屉原理说明

源代码 Source Code
阅读理解题 其实就是倒置的强化版汉诺塔,每层的普通语句数即为对应大小的圆盘的个数 递推即可,不用加任何优化 f[i]表示移动前 i 种盘子需要的步数,f[i] = 2 * f[i - 1] + a[i] 如果看出了本题的实际模型,不用任何优化就可以 AC 本题了,其实算是送分了 由于第二题是高精度,所以本题就不再考验大家的高精度水准了,改成了模一个 数输出。

PS:
本次的题目,第一题来自 ACM,第二题改自课堂数学题,第三题纯属突发奇 想+恶搞。 整套题目的题面(仅仅是题面)有一定杂糅了 “盗梦空间 (Inception) 和 ” “源 代码(Source Code) ”概念的成分 三题的题目名称均有来源 第一题, “猫和老鼠” ,我想 Tom 和 Jerry 两位兄弟应该给我们每个人的童年 都留下了不少有趣的记忆吧。 第二题, 《双城记》 ,查尔斯·狄更斯的小说,高中好像是必读书目之一。故 事梗概我就不写了,有兴趣的自己去百度百科吧~~ 第三题, “源代码” ,电影,已经下映了(中国 8 月底才上映啊,美国 4 月就 上映了怨念啊) ,讲述一个与平行宇宙理论有关的故事。其中的源代码计划拥有 创造平行宇宙的能力(但开发者不知道) ,推荐一看。