ACM

BZOJ 3211 花神游历各国(线段树)

BZOJ 3211 花神游历各国(线段树)
题意:就是中文,都能看懂。看到区间很大,肯定得上线段树。不过这里直接上线段树肯定还是TLE,所以得用一种类似于剪枝的方法,当一个数多次开根号之后肯定是1了,所以一旦为1就不要往下更新?题目地址:http://www.lydsy.com/JudgeOnline/problem.php?id=3211代码:Memory: 7552 KBTime: 1976 MSLanguage:&... 继续阅读 »
ACM

HDU-1115 Lifting the Stone(凸包,求多边形重心)

HDU-1115 Lifting the Stone(凸包,求多边形重心)
题意:给出一个多边形的N个点的坐标,求这个多边形的重心。1、质量集中在顶点上:n个顶点坐标为(xi,yi),质量为mi,则重心 :X = ∑( xi×mi ) / ∑mi  Y = ∑( yi×mi ) / ∑mi  若每个点的质量相同,则有X&nb... 继续阅读 »
ACM

HDU 1071 The area

HDU 1071	The area
题意:给你三个点,分别代表抛物线的顶点以及一条直线与他的两个交点。请计算他们的闭合区域的面积。一道简单的数学积分题,就是自己推导的时候变量比较多有点繁琐。这里我使用了直线的两点式和抛物线的两点式。(比较坑爹的一点是y1这个变量不能定义,用c++编译器会报错,所以用g++过的。还有就是用函数返回积分会耗费15ms,如果不用函数则是0ms)题目地址:http://acm.hdu.edu.cn/show... 继续阅读 »
ACM

HDU 1018 Big Number

HDU 1018	Big Number
题意:给一个数n,计算n的阶乘有多少位数。方法一:由于给出的n很大,到了10^7,所以直接计算是肯定不可能的,所以可以使用log。例如:log10(100) = 2;log10(1000)=3,log10(54321)~4.7,log10(12345)~4.0...我们可以看出,以10为底计算log10(x)向下取整就是这个数的位数-1,而:log10(n!)=log10(n*(n-1)*...*... 继续阅读 »
ACM

HDU-1060 Leftmost Digit

HDU-1060 Leftmost Digit
题意:给你一个n,求n的n次方的最左边的数。这里使用对数来求解比如:3^3 = 2727 = 2.7 * 10^1n^n =x * 10^yx的整数部分就是我们要求的数,即为(int)x。两边取对数:lg(n^n) = lg(x * 10^y)化简求得:x = 10^(n*lgn - y);而y = lgn^n向下取整数。所以x就可以得出了。代码:Memory: 1820 KBTime:... 继续阅读 »
ACM

HDU-1051 Wooden Sticks

HDU-1051 Wooden Sticks
题意:大概就是要加工木头,第一根放进去的要1分钟,后面如果长度和重量都比之前放的大就不用时间,求处理完木头最少的时间。LIS问题,每次求完之后标记一下下次不再处理。题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1051代码:Memory: 1852 KBTime: 31 MSLanguage: C++Result:&nb... 继续阅读 »
ACM

HDU-1041 Computer Transformation

HDU-1041 Computer Transformation
题意:电脑机器翻译,1会翻译成0 1,0会翻译成1 0,问现在有一个数字1在n步后有这段序列中存在多少对0。我们先来找下规律1011001011010011001011001101001......我们可以发现,当前位置n成对的0都来自于两个地方:1、n-2中1的个数2、n-2中00的个数找到规律后打个表就好了。不过这里要注意,给出的n达到了1000,2^1000这个数就很大了,所以我们要使用大数... 继续阅读 »
ACM

HDU-1044 Collect More Jewels

HDU-1044 Collect More Jewels
题意:有一个人在地牢里面,现在他得知地牢要GG了,他要在规定的时间内逃出去,但是地牢里面还有很多珠宝,每个珠宝价值不一样,他在出逃的时候想获得最大的价值并且逃出去(如果能逃出去的话)。BFS+DFS同时使用的题,用的数组特别多容易乱。大概就是先用bfs找出起点,宝石,终点这些点之间的距离保存在数组里面,然后用dfs找最大价值的最短路径。题目地址:http://acm.hdu.edu.cn/show... 继续阅读 »
ACM

HDU-1045 Fire Net

HDU-1045 Fire Net
题意:给你一个地图,然后地图上会放置一些炮台,这些炮台会往四个方向发射无穷远,保证多个炮台之间不能被打到,求最大放置的炮台数。其实就是类似于炸弹人游戏一样,不过这里是射程无穷远而已。DFS题,注意数组状态保存以及方向变化。题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1045代码:Memory: 1804 KBTime: 15 M... 继续阅读 »
ACM

HDU1047-Integer Inquiry

HDU1047-Integer Inquiry
一个大数加法题,处理大数用倒置加,但是不用像网上那样倒置来倒置去的,直接长度递减就好,还有就是输出0,坑了好几次,自己写的print倒置输出竟然忘记了还有0这个输出特例。题目:http://acm.hdu.edu.cn/showproblem.php?pid=1047代码:Memory: 1584 KBTime: 0 MSLanguage: G++Result:&nb... 继续阅读 »