LightOJ Beginners Problems 部分题解

相关代码请戳 https://coding.net/u/tiny656/p/LightOJ/git

1006 Hex-a-bonacci. 用数组模拟记录结果,注意取模

1008 Fibsieve's Fantabulous Birthday. 找规律题,左边列是1 3平方 5平方......下边行是1 2平方 4平方......,找到当前数被包夹的位置,然后处理一下位置关系,注意奇偶。

1010 Kinghts in Chessboard. 规律题,对于m,n大于2的情况下,使用交叉放置的方法。特判一下情况,对于min(m,n)=1,结果m*n。对于min(m,n) =2时候,采用4方格间隔放置的方法。

1042 Secret Origins. 定义一个数,n的二进制1的个数就是这个值,求二进制1个数相同的下个数。首先,拆分为2进制,寻找最先出现的01,然后交换两者顺序,对于010111100的这类情况,结果应该是011000111,所以要把后面的连续1后移到权值为1的位置。

1045 Digits of Factorial. 求b进制下n阶乘的位数有多少,用stirling公式和b^x=result. 求出x就是位数

1053 Higher Math. 给三角形的三边,判断是否是直角三角形。按照边大小排序,1.勾股定理 2.两边之和大于第三边,两边之差小于第三边。

1107 Calm Down. 简单的数学计算,连接两个大圆心和两个小圆心形成一个三角形,连接的角度为360/n度,利用余弦定理建立方程,可以求解出r。

1109 False Ordering. 筛法把所有1-1000的数,因子全部求出来,然后排序查结果。O(n^2)筛法,排序O(nlogn) ,每次查询O(1).

1113 Discover the Web. 模拟网页的前进后退访问,算法的步骤已经在题目中详细说明

1116 Ekka Dokka. 把一个大数拆成奇数乘以偶数。注意x&1判断就就可以。

1133 Array Simulation. 模拟加减乘除数组运算。

1136 Division by 3. 1,12,123,1234,...,12345678910,...这种模式an = n*(n+1)/2,给an 在[a,b]之间,判断被3整除的有多少个。只要判断n或者n+1是否能被3整除,通过左右界a,b运算就可以得到结果。n被3整除数量b / 3 - a / 3 + ((a % 3) == 0 ? 1 : 0),n+1被3整除数量(b + 1) / 3 - (a + 1) / 3 + (((a + 1) % 3) == 0 ? 1 : 0),注意结果用long long

1182 Parity. 计算二进制1的个数。多种方法

1189 Sum of Factorials. 计算给定数是否能由阶乘和来表示。注意不要遗漏0!=1。思考fac(n) >= fac(n-1)+...+fac(0). 对于给定一个恰好大于fac(n)小于fac(n+1)的数,fac(0...n-1)都是小于等于fac(n),所以不可能由他们构成给定数,由此我们只用贪心的从大向小取值即可。

1211 Intersection of Cubes. 给N个长方体的对角线坐标(x1,y1,z1),(x2,y2,z2),其中x1<x2,y1<y2,z1<z2,求这N个长方体的共有的相交体积是多大。先从二维入手,然后再进行三维。求出所有x1,y1,z1的最大值,x2,y2,z2的最小值,所得的就是相交长方体,如果构成不了长方体,就为0。

1214 Large Division. 大数取模,注意加法溢出。

1227 Boiled Eggs. n个鸡蛋取出p个不超过q的重量,问最多能取出几个。直接从头贪心加最小的。

1241 Pinocchio. 呀,好坑的一道题,其实就是要找递增序列,上升跳跃过几次,但是每次跳跃最多是1-5cm,而且初始是2cm,对于2 8序列,结果跳跃肯定是2了,对于3 3这种,结果上来要从2->3。注意这些情况就好了。Sigh!

1249 Chocolate Thief. 总和除以人数,就是平均水平,枚举所有人,大于平均就是贼,小于平均就是受害者。

1305 Area of a Parallelogram. 求四边形的第四个顶点和面积。cx-dx = bx-ax, cy-by = dy-ay. 然后是点到直线距离公式. H = |A*x0+B*y0+C| / sqrt(A^2+B^2). S = Lab*H 下面可以约掉的根号可以约掉

1331 Agent J. 推公式,三圆相切,求中间空白面积。圆心构造三角形,用三角形面积减去三个圆弧面积。 海伦公式,求出角平分线交点到各边高,以及反正切函数求角。

1414 February 29. 求两个日期之间的闰年数量。2015编程之美资格赛原题。定义求n年前的闰年数量,func(n)=n/4-n/100+n/400, 即找出所有能被4整除的年,减去能被100整除年,加上400整除的年数量,就是n年(包括n)之前的闰年数量,那么a-b之间闰年数量就是func(b)-func(a-1)。注意处理一下月和天,修改年。比如第一段时间月份大于等于3,算成下一年。第二段月份如果在2月29之前,算成上一年。

原文地址:https://www.cnblogs.com/tiny656/p/4471664.html