ACM

BZOJ-2151 种树(转化思想,优先队列)

BZOJ-2151 种树(转化思想,优先队列)
题意:就是种树咯。三棵树,我们可以选择种中间的一棵树,也可以选择种旁边的两棵树,但是我们怎么知道要取哪种方式呢。所以我们不妨把两棵树之和与中间的树的值之差算出来放到中间的树的暂存值里面去,再把这3棵树看成一棵树,以此类推,最后得到最优解, 但是我们看起来好像觉得这种方法有点虚?其实我一开始也觉得虚,后来看了好几个题解才发现不虚啊!题目地址:http://www.lydsy.com/JudgeOnl... 继续阅读 »
ACM

BZOJ-4029 定价(贪心)

BZOJ-4029 定价(贪心)
题意:中文你懂得其实我们仔细想想如果同样位数,那么0结尾的必定最好,其次是5,再者是尾数最小的那个数。这样我们从一个数的最后一位开始模拟进位计算,使得这个数在上限之内的最小p就好,其实我算法还可以优化一下,40ms比较慢了。题目地址:http://www.lydsy.com/JudgeOnline/problem.php?id=4029代码:Memory: 1300 KBTime:&nb... 继续阅读 »
ACM

BZOJ-1008 越狱(排列组合+快速幂)

BZOJ-1008 越狱(排列组合+快速幂)
题意:这个是中文,不用解释了吧。因为每个人有m种宗教可以信仰,那么一共有m^n种排列情况。而不发生越狱的情况只能是,第一个人选择m的一种,第二个人有m-1种选择,后面为了不同,都是m-1种选择,共m*(m-1)^(n-1)种。由于幂太大,达到连大数都存不下了,所以这里需要用到快速幂来计算。快速幂其实就是把一个带幂的数拆分一下,幂为偶数的时候可以除一半,把底数多一个,奇数的时候先拆一个出来使幂变成偶... 继续阅读 »
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这个数就很大了,所以我们要使用大数... 继续阅读 »