AOAPC I: Volume 1.Maths-Misc

Written by    14:54 November 30, 2014 

<<算法竞赛入门经典>> UVaoj第二卷数学类习题:

113-Power of Cryptography

这题真是…诶…

一开始发现数值好大所以就各种折腾大数模板, 然后就这样活生生地卡在开方算法那里了…最后实在忍不住搜了搜解题报告, 一看到人家的那个double就想起了double…是可以到2^1024的…

我说这么高端的算法怎么AC率那么高…囧.

10161-Ant on a Chessboard

大水题, 初中数学吧.

253-Cube painting

转来转去只有24种可能, 暴力翻转一下就可以了.

621-Secret Research

水题中的战斗机, 不要怀疑自己, 就是这么水.

10025-The ? 1 ? 2 ? … ? n = k problem

因为每增加改变一个数的加减整个式子的数值的改变就是被改变数的两倍, 所以只要满足当式子中的所有数的绝对值大于给的数的绝对值并且相差为偶数即可, 暴力思密达!

591-Box of Bricks

超级大水题, 只要计算出平均值然后所有所有数与平均值的差的一半即可.

107-The Cat in the Hat

一开始看掉了H是constant折腾了半天, 以后读题真的得小心. 要先注意工猫只有一只的情形, 因为工猫的数字一定是N(N>=1)次方数, 所以暴力找到即可, 然后浮点数注意+0.5四舍五入取整, 并且大小判断也不能直接用等于号得判断是否小于1e-4f.

573-The Snail

注意判断的时候一定要是大于那个高度, 不能等于, 不然晚上自己就会滑下去滴~

846-Steps

这个题意有点难懂, 其实给出的两个值不是重要的, 答案只跟给出的值的差值相关, 比如说45和48, 相差3, 于是只能走1 1 1, 如果两个数相差4的话就只能 1 2 1, 总之第一步和最后一步必须是1, 然后每一步之间的插值相差最多为1.

10499-The Land of Justice

就是计算切开过后表面积增加了百分之多少.

10790-How Many Points of Intersection?

选取任意一段, 从一边开始分析, 每计算到一个点的时候只用计算这个点与这个点之前的交点.

11044-Searching for Nessy

不要质疑这道题的水.

10719-Quotient Polynomial

简单的多项式运算, 初中题.

10177-(2/3/4)-D Sqr/Rects/Cubes/Boxes?

全在于找规律, 不用费劲在四维超立方体到底是什么样的, 我们毕竟是三维生物, 那玩意儿太难想象了. 首先得注意到的是某维中除了正方形(或立方体或超立方体)就是矩形(或长方体或超长方体), 然后边(棱)长为a的N维总共有a^N个物体, 其他的都可以找到公式表达.

10916-Factstone Benchmark

取对数!大数模板, double什么的都是浪费生命!

10970-Big Chocolate

请不要质疑它的水.

10014-Simple calculations

a1 = (n*a0+an1-2*(n*c1+(n-1)*c2+…+1*cn))/(n+1)

这一卷题目最难的地方在于总是会情不自禁地质疑题目的水.

Category : acm

Tags :