2012年9月23日

修改自:http://hi.baidu.com/arorua_/item/381bb88d817b122d100ef3a1
Number one:poj2480 http://poj.org/problem?id=2480
题意是:求∑gcd(i, N) 1<=i <=N.  N(1 < N < 2^31)
解法:gcd(i, n) == ∑(fac[i] * phi(n / fac[i])) (fac存的是n的所有约数)
代码:
poj2480



posted @ 2012-09-23 18:19 phonism 阅读(78) | 评论 (0)编辑 收藏

2012年9月18日

<题意题解等等再补^_^>
求概率:
uvalive5863
 hdu4089
求期望:
poj2096 zoj3329 hdu4035
posted @ 2012-09-18 20:07 phonism 阅读(79) | 评论 (0)编辑 收藏

2012年9月17日

筛素数和欧拉函数
再贴个筛区间素数的:
筛区间素数
posted @ 2012-09-17 18:23 phonism 阅读(63) | 评论 (0)编辑 收藏

2012年8月9日

    学习状态压缩,首先要会基础的位运算,然后要知道位运算的一些基本应用,这方面Matrix67大牛总结的很好。学习了这些,接下来可以看看这篇论文,讲的挺好。
posted @ 2012-08-09 12:29 phonism 阅读(54) | 评论 (0)编辑 收藏

2012年8月4日

贴个专题http://acm.hdu.edu.cn/forum/read.php?tid=15908

FOJ1683:http://acm.fzu.edu.cn/problem.php?pid=1683
题意:已知 F(n)=3 * F(n-1)+2 * F(n-2)+7 * F(n-3),n>=3,其中F(0)=1,F(1)=3,F(2)=5,对于给定的每个n,输出F(0)+ F(1)+ …… + F(n) mod 2009。
题解:找到递推矩阵

[S(n-1)]   [1 3 2 7]     [S(n)]

[F(n-1)] * [0 3 2 7]  =  [F(n)]

[F(n-2)]   [0 1 0 0]     [F(n-1)]

[F(n-3)]   [0 0 1 0]     [F(n-2)]

然后矩阵快速幂就破了 代码就不贴了。

HDU2256:http://acm.hdu.edu.cn/showproblem.php?pid=2256

这题可以用矩阵乘法解,非常巧妙。。。

贴个解题报告吧:
http://chensmiles.blog.163.com/blog/static/12146399120107310
4757471/

 




posted @ 2012-08-04 20:32 phonism 阅读(43) | 评论 (0)编辑 收藏
今天做了一下背包专题,连接http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=10736#overview密码是:sduacm 个人觉得这几题都很不错
额,第一题就不说了,普通的0-1背包

G题(HDU4091)是2011年上海区预赛第一题,据说AC这道题就可以拿铜牌了(囧) 题意是给俩个物品,每个物品有价值和体积,显然直接贪心不对,可以当作背包来解,但背包的容量很大,不能直接背包。这题的做法是:现求总容量对俩个物品的体积的LCM取余的余数,然后在余数中枚举,对其他的容量贪心,很容易证明这个思路的正确性。
HDU4091

I题(SGU259)单机调度问题,题意是只有一个打印机,有许多传单需要打印和分发,打印的时间T[i],分发的时间是L[i],每个传单必须先打印后分发,假设有很多分发员,问将左右的传单打印并且分发完所用完的最短时间。这题直观有个感觉就是因为分发员有很多人,分发时间长的传单显然先打印比较好,并且很容易证明这个贪心思想的正确性。因此对L从大到小排序,然后再求的时间就是最短的时间。
SGU259

SPOJ39_PIGBANK:这题是个经典的完全背包问题,题意是有个储蓄罐,知道了空的时候的质量和装满硬币的质量,给了一些硬币的质量和价值,求储蓄罐装满时硬币的最小价值。
经典题。
SPOJ39_PIGBANK






posted @ 2012-08-04 18:05 phonism 阅读(118) | 评论 (0)编辑 收藏

2012年8月3日

今天发现这个网站http://www.donews.com/挺不错的  虽然上面没有什么的算法,但是都是IT行业一些比较前沿的新闻什么的,对以后应该会有作用吧
posted @ 2012-08-03 21:43 phonism 阅读(43) | 评论 (0)编辑 收藏
仅列出标题  

导航

<2019年2月>
272829303112
3456789
10111213141516
17181920212223
242526272812
3456789

统计

常用链接

留言簿

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜