C++博客-A code a day, keeps the girls away!

hdu 3918 Beiju

AmazingCaddy — Sat, 13 Aug 2011 08:25:00 GMT

摘要: http://acm.hdu.edu.cn/showproblem.php?pid=3918一个如上图所示的杯子，一开始为空，且杯子的重量不计，沿着杯壁往里面慢慢地倒水，直到杯子倒了为止，最高能往里面倒多少水，求最后水的高度。做法：将杯身分割成梯形，每个梯形中，重心是在x轴的分量，是往一个方向偏移，也就是有单调性。求出从下往上枚举每个梯形，求出第一个使得杯子倒掉的梯形，然后在这个梯形内部二分，求出... 阅读全文

AmazingCaddy 2011-08-13 16:25 发表评论

hdu 3869 Color the Simple Cycle

AmazingCaddy — Sat, 13 Aug 2011 08:15:00 GMT

摘要: http://acm.hdu.edu.cn/showproblem.php?pid=3869polya计数题里给的环，可以从某个顶点开始，按照逆时针顺序，依次将经过的边权和点权构成一个序列，那么这个序列唯一确定这个环。并且，一切旋转，都相当于对形成的序列进行循环移位。因此可以用扩展KMP算法，将两个原序列拼接作为匹配串，将原序列作为模式串，就可以在O(N)内知道所有能和原串重合的移位方法。对于... 阅读全文

AmazingCaddy 2011-08-13 16:15 发表评论

hdu 3911 Black And White

AmazingCaddy — Sat, 13 Aug 2011 08:11:00 GMT

摘要: http://acm.hdu.edu.cn/showproblem.php?pid=3911久违的线段树啊，亲好久没写线段树了，都不会写了。。。在队友的指导下，艰难地写完了。。。 Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> ... 阅读全文

AmazingCaddy 2011-08-13 16:11 发表评论

hdu 3930 Broot

AmazingCaddy — Sat, 13 Aug 2011 08:07:00 GMT

摘要: http://acm.hdu.edu.cn/showproblem.php?pid=3930题目意思很简单对于方程 x^k = b mod p，给出k，b，p，求所有的x ( 0<= x < p )，题目的数据范围很恶心，其实没有那么大，只有10^12那么大，可以打素数表了亲，再大的话，只能rho来分解了。。。 1) 先暴力求p的原根g 2) ... 阅读全文

AmazingCaddy 2011-08-13 16:07 发表评论

pku 3659 Cell Phone Network

AmazingCaddy — Tue, 10 May 2011 08:32:00 GMT

摘要: http://poj.org/problem?id=3659题意: 给出一棵树(无向图),让你在上面选点放塔, 塔覆盖范围为当前点和相邻的点,用最小的塔覆盖所有点解法1：树型DP dp[ i ][ 0 ], 表示该点不放塔, 且被祖先结点覆盖 dp[ i ][ 1 ], 表示该点不放塔, 不被祖先覆盖 dp[ i ][ 2 ], 放塔 u为i 的子结点d... 阅读全文

AmazingCaddy 2011-05-10 16:32 发表评论

hdu 2865 Birthday Toy

AmazingCaddy — Sun, 27 Feb 2011 10:59:00 GMT

摘要: http://acm.hdu.edu.cn/showproblem.php?pid=2865题意：AekdyCoin大神对一个特殊的玩具进行染色，跟pku2888（http://www.cppblog.com/AmazingCaddy/archive/2011/02/27/140750.html）差不多。玩具如题中所示，中间一个圆，外面圆周上排列了N个小圆，形成一个大圈，一共N+1个圆，每个小圆都... 阅读全文

AmazingCaddy 2011-02-27 18:59 发表评论

pku 2888 Magic Bracelet

AmazingCaddy — Sun, 27 Feb 2011 10:43:00 GMT

摘要: http://poj.org/problem?id=2888题意：Harry Potter 要用m种颜色的珠子做一个长度为n的手镯，手镯首尾相接。其中某些颜色的珠子不兼容，不能放在一起。求Harry Potter能够早多少种不同的手镯（每种颜色的珠子都有无限多颗，旋转之后能够吻合的算同一种）。解法：polya计数，sum = sigma ( Euler( n / i )*Gettr( i ) ) ... 阅读全文

AmazingCaddy 2011-02-27 18:43 发表评论

pku 2154 Color

AmazingCaddy — Sat, 26 Feb 2011 13:08:00 GMT

摘要: http://poj.org/problem?id=2154楼爷的题目，题目大意就是一个长度为n的项链，首尾相接，用n种颜色去染色，求有多少种染色方案（经过旋转之后一样的，算同一种方案），最后只要输出总方案 mod P。解法：polya定理由于n很大，所以对n进行分解之后，再DFS求出所有的因数。 1/**//* 2*&nb... 阅读全文

AmazingCaddy 2011-02-26 21:08 发表评论

pku 3696 The Luckiest number

AmazingCaddy — Tue, 08 Feb 2011 11:19:00 GMT

摘要: http://poj.org/problem?id=36968*10^0+8*10^1+8*10^2+8*10^3+8*10^4+.....+8*10^(n-1) = 8*(10^n-1)/9由题意有 8 * ( 10^n - 1 ) / 9 = 0 ( mod L ) 求最小的 n-------> 8 * ( 10^n - 1 ) = 0 ( mod 9 * L )-------> ... 阅读全文

AmazingCaddy 2011-02-08 19:19 发表评论

tzc 2352 Factovisors

AmazingCaddy — Sun, 30 Jan 2011 15:22:00 GMT

http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=2352

好久没有做数论题了，弱死了，这题弄了N久，因为没有考虑0这个特殊的家伙不能作为除数。
题意相当简单，就是判断m能否整除n！。
解法：对m进行素因数分解，m = p1^t1 * p2^t2 * ... * ps^ts。那么对于pi，判断n！是否含有x个因数，使得x >= ti。

tzc_2352

AmazingCaddy 2011-01-30 23:22 发表评论

fzu 1971 A math problem

AmazingCaddy — Thu, 21 Oct 2010 12:54:00 GMT

摘要: http://acm.fzu.edu.cn/problem.php?pid=19712010年福州网赛A题，AC出的身体，看了AC的解题报告写的，死活不会那个证明，然后就用了第二种方法。题解详见：http://hi.baidu.com/aekdycoin/blog/item/e87f5f9653423c6255fb969b.html Orz AekdyCoin PS: 题目有个... 阅读全文

AmazingCaddy 2010-10-21 20:54 发表评论

sgu 433 Japhshan and Ramshut

AmazingCaddy — Wed, 06 Oct 2010 14:08:00 GMT

摘要: http://acm.sgu.ru/problem.php?contest=0&problem=433题目大意：要求使用一个长为L，宽为1的矩形，刚好填充一个大的矩形。解法：比较裸的DLX，knuth的论文中有更加复杂的图案。建图：行代表以一个格子为起点，使用第i个小矩形，横着或者竖着填充大矩形。 &nbs... 阅读全文

AmazingCaddy 2010-10-06 22:08 发表评论

sgu 435 UFO Circles

AmazingCaddy — Mon, 04 Oct 2010 18:08:00 GMT

摘要: http://acm.sgu.ru/problem.php?contest=0&problem=435题目大意，每个UFO会使长草的地面变成荒地，使荒地长出草来，作用范围是一个圆，求最后荒地和草地面积各为多少。圆的离散化，比赛的时候没有想仔细，没有做出来，赛后经haozi一点拨，发现可以做，就拿以前写的一个圆离散化的代码改了改，结果精度不够。重新写了一个，结果打错了一个变量，一直没有发现，... 阅读全文

AmazingCaddy 2010-10-05 02:08 发表评论

eoj 2830 Hamster 2

AmazingCaddy — Tue, 28 Sep 2010 16:27:00 GMT

摘要: http://www.acm.cs.ecnu.edu.cn/problem.php?problemid=2830题目大意：空中有很多竖直的门，一个点以V0的初速度抛出，忽略空气阻力，重力加速度为10m/s2,求此点最多能穿过几个门。解法：对于每个门，根据斜抛运动，解出初速度与x轴的夹角范围，然后求出重叠次数最大的区域，输出该次数。 eoj 2830Code highlighting produc... 阅读全文

AmazingCaddy 2010-09-29 00:27 发表评论

hdu 2966 In case of failure

AmazingCaddy — Tue, 07 Sep 2010 03:26:00 GMT

摘要: http://acm.hdu.edu.cn/showproblem.php?pid=2966题目的意思是：平面上有n个点（n<100000），求每个点的最近点到该点的平方距离。KD_Tree可以解决此题。详细资料可以参看此链接 http://en.wikipedia.org/wiki/Kd-tree，上面给出了算法。PS: 这道题时限开了恐怖的30秒。 hdu_2966Code high... 阅读全文

AmazingCaddy 2010-09-07 11:26 发表评论