ACM

CodeForces 732B Cormen — The Best Friend Of a Man(简单贪心,模拟)

CodeForces 732B Cormen — The Best Friend Of a Man(简单贪心,模拟)
题意:给出一组数据,两个数之间要大于或等于某个数才能符合要求,你可以将原来的数加上一个整数使他符合要求,输出之后的数据以及你总共加了多少。很简单,从第二个开始模拟就行了。题目地址:http://codeforces.com/problemset/problem/732/B代码:Memory: 4 KBTime: 15 MSLanguage: GNU G++ 5.1.0... 继续阅读 »
ACM

SCU-2090 单色三角形(计数)

SCU-2090	 单色三角形(计数)
题意:找具有三条边颜色相同的三角形数这个题数据比较水,直接暴力也能过,不过@freeloop建议我们用单色三角形理论去计算,于是看了别人的题解。大致就是先求出非单色三角形数目,然后用总的减去非单色三角形。总的数目是C(n,3),非单色三角形我们只需要遍历每个点,看看他的边是否具有同样颜色(这里要注意除以2,因为遍历三角形另外点的时候具有重复计算)就可以了。题目地址:http://acm.scu.e... 继续阅读 »
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:... 继续阅读 »