A code a day, keeps the girls away!
C++博客 \| 首頁 \| 發(fā)新隨筆 \| 發(fā)新文章 \| 聯(lián)系 \| 聚合 \| 管理	隨筆：46 文章：0 評(píng)論：16 引用：0

2011年8月13日

hdu 3918 Beiju

摘要: http://acm.hdu.edu.cn/showproblem.php?pid=3918一個(gè)如上圖所示的杯子，一開始為空，且杯子的重量不計(jì)，沿著杯壁往里面慢慢地倒水，直到杯子倒了為止，最高能往里面倒多少水，求最后水的高度。做法：將杯身分割成梯形，每個(gè)梯形中，重心是在x軸的分量，是往一個(gè)方向偏移，也就是有單調(diào)性。求出從下往上枚舉每個(gè)梯形，求出第一個(gè)使得杯子倒掉的梯形，然后在這個(gè)梯形內(nèi)部二分，求出... 閱讀全文

posted @ 2011-08-13 16:25 AmazingCaddy 閱讀(348) | 評(píng)論 (0) | 編輯收藏

hdu 3869 Color the Simple Cycle

摘要: http://acm.hdu.edu.cn/showproblem.php?pid=3869polya計(jì)數(shù) 題里給的環(huán)，可以從某個(gè)頂點(diǎn)開始，按照逆時(shí)針順序，依次將經(jīng)過的邊權(quán)和點(diǎn)權(quán)構(gòu)成一個(gè)序列，那么這個(gè)序列唯一確定這個(gè)環(huán)。并且，一切旋轉(zhuǎn)，都相當(dāng)于對(duì)形成的序列進(jìn)行循環(huán)移位。因此可以用擴(kuò)展KMP算法，將兩個(gè)原序列拼接作為匹配串，將原序列作為模式串，就可以在O(N)內(nèi)知道所有能和原串重合的移位方法。對(duì)于... 閱讀全文

posted @ 2011-08-13 16:15 AmazingCaddy 閱讀(331) | 評(píng)論 (0) | 編輯收藏

hdu 3911 Black And White

摘要: http://acm.hdu.edu.cn/showproblem.php?pid=3911久違的線段樹啊，親好久沒寫線段樹了，都不會(huì)寫了。。。在隊(duì)友的指導(dǎo)下，艱難地寫完了。。。 Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> ... 閱讀全文

posted @ 2011-08-13 16:11 AmazingCaddy 閱讀(348) | 評(píng)論 (0) | 編輯收藏

hdu 3930 Broot

摘要: http://acm.hdu.edu.cn/showproblem.php?pid=3930題目意思很簡(jiǎn)單對(duì)于方程 x^k = b mod p，給出k，b，p，求所有的x ( 0<= x < p )，題目的數(shù)據(jù)范圍很惡心，其實(shí)沒有那么大，只有10^12那么大，可以打素?cái)?shù)表了親，再大的話，只能rho來分解了。。。 1) 先暴力求p的原根g 2) ... 閱讀全文

posted @ 2011-08-13 16:07 AmazingCaddy 閱讀(754) | 評(píng)論 (0) | 編輯收藏

2011年5月10日

pku 3659 Cell Phone Network

摘要: http://poj.org/problem?id=3659題意: 給出一棵樹(無向圖),讓你在上面選點(diǎn)放塔, 塔覆蓋范圍為當(dāng)前點(diǎn)和相鄰的點(diǎn),用最小的塔覆蓋所有點(diǎn)解法1：樹型DP dp[ i ][ 0 ], 表示該點(diǎn)不放塔, 且被祖先結(jié)點(diǎn)覆蓋 dp[ i ][ 1 ], 表示該點(diǎn)不放塔, 不被祖先覆蓋 dp[ i ][ 2 ], 放塔 u為i 的子結(jié)點(diǎn)d... 閱讀全文

posted @ 2011-05-10 16:32 AmazingCaddy 閱讀(313) | 評(píng)論 (0) | 編輯收藏

2011年2月27日

hdu 2865 Birthday Toy

摘要: http://acm.hdu.edu.cn/showproblem.php?pid=2865題意：AekdyCoin大神對(duì)一個(gè)特殊的玩具進(jìn)行染色，跟pku2888（http://www.shnenglu.com/AmazingCaddy/archive/2011/02/27/140750.html）差不多。玩具如題中所示，中間一個(gè)圓，外面圓周上排列了N個(gè)小圓，形成一個(gè)大圈，一共N+1個(gè)圓，每個(gè)小圓都... 閱讀全文

posted @ 2011-02-27 18:59 AmazingCaddy 閱讀(346) | 評(píng)論 (0) | 編輯收藏

pku 2888 Magic Bracelet

摘要: http://poj.org/problem?id=2888題意：Harry Potter 要用m種顏色的珠子做一個(gè)長(zhǎng)度為n的手鐲，手鐲首尾相接。其中某些顏色的珠子不兼容，不能放在一起。求Harry Potter能夠早多少種不同的手鐲（每種顏色的珠子都有無限多顆，旋轉(zhuǎn)之后能夠吻合的算同一種）。解法：polya計(jì)數(shù)，sum = sigma ( Euler( n / i )*Gettr( i ) ) ... 閱讀全文

posted @ 2011-02-27 18:43 AmazingCaddy 閱讀(539) | 評(píng)論 (0) | 編輯收藏

2011年2月26日

pku 2154 Color

摘要: http://poj.org/problem?id=2154樓爺?shù)念}目，題目大意就是一個(gè)長(zhǎng)度為n的項(xiàng)鏈，首尾相接，用n種顏色去染色，求有多少種染色方案（經(jīng)過旋轉(zhuǎn)之后一樣的，算同一種方案），最后只要輸出總方案 mod P。解法：polya定理由于n很大，所以對(duì)n進(jìn)行分解之后，再DFS求出所有的因數(shù)。 1/**//* 2*&nb... 閱讀全文

posted @ 2011-02-26 21:08 AmazingCaddy 閱讀(444) | 評(píng)論 (0) | 編輯收藏

2011年2月8日

pku 3696 The Luckiest number

摘要: 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 )-------> ... 閱讀全文

posted @ 2011-02-08 19:19 AmazingCaddy 閱讀(298) | 評(píng)論 (0) | 編輯收藏

2011年1月30日

tzc 2352 Factovisors

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

好久沒有做數(shù)論題了，弱死了，這題弄了N久，因?yàn)闆]有考慮0這個(gè)特殊的家伙不能作為除數(shù)。
題意相當(dāng)簡(jiǎn)單，就是判斷m能否整除n！。
解法：對(duì)m進(jìn)行素因數(shù)分解，m = p1^t1 * p2^t2 * ... * ps^ts。那么對(duì)于pi，判斷n！是否含有x個(gè)因數(shù)，使得x >= ti。

tzc_2352

posted @ 2011-01-30 23:22 AmazingCaddy 閱讀(272) | 評(píng)論 (0) | 編輯收藏

2010年10月21日

fzu 1971 A math problem

摘要: http://acm.fzu.edu.cn/problem.php?pid=19712010年福州網(wǎng)賽A題，AC出的身體，看了AC的解題報(bào)告寫的，死活不會(huì)那個(gè)證明，然后就用了第二種方法。題解詳見：http://hi.baidu.com/aekdycoin/blog/item/e87f5f9653423c6255fb969b.html Orz AekdyCoin PS: 題目有個(gè)... 閱讀全文

posted @ 2010-10-21 20:54 AmazingCaddy 閱讀(360) | 評(píng)論 (0) | 編輯收藏

2010年10月6日

sgu 433 Japhshan and Ramshut

摘要: http://acm.sgu.ru/problem.php?contest=0&problem=433題目大意：要求使用一個(gè)長(zhǎng)為L(zhǎng)，寬為1的矩形，剛好填充一個(gè)大的矩形。解法：比較裸的DLX，knuth的論文中有更加復(fù)雜的圖案。建圖：行代表以一個(gè)格子為起點(diǎn)，使用第i個(gè)小矩形，橫著或者豎著填充大矩形。 &nbs... 閱讀全文

posted @ 2010-10-06 22:08 AmazingCaddy 閱讀(415) | 評(píng)論 (0) | 編輯收藏

2010年10月5日

sgu 435 UFO Circles

摘要: http://acm.sgu.ru/problem.php?contest=0&problem=435題目大意，每個(gè)UFO會(huì)使長(zhǎng)草的地面變成荒地，使荒地長(zhǎng)出草來，作用范圍是一個(gè)圓，求最后荒地和草地面積各為多少。圓的離散化，比賽的時(shí)候沒有想仔細(xì)，沒有做出來，賽后經(jīng)haozi一點(diǎn)撥，發(fā)現(xiàn)可以做，就拿以前寫的一個(gè)圓離散化的代碼改了改，結(jié)果精度不夠。重新寫了一個(gè)，結(jié)果打錯(cuò)了一個(gè)變量，一直沒有發(fā)現(xiàn)，... 閱讀全文

posted @ 2010-10-05 02:08 AmazingCaddy 閱讀(564) | 評(píng)論 (3) | 編輯收藏

2010年9月29日

eoj 2830 Hamster 2

摘要: http://www.acm.cs.ecnu.edu.cn/problem.php?problemid=2830題目大意：空中有很多豎直的門，一個(gè)點(diǎn)以V0的初速度拋出，忽略空氣阻力，重力加速度為10m/s2,求此點(diǎn)最多能穿過幾個(gè)門。解法：對(duì)于每個(gè)門，根據(jù)斜拋運(yùn)動(dòng)，解出初速度與x軸的夾角范圍，然后求出重疊次數(shù)最大的區(qū)域，輸出該次數(shù)。 eoj 2830Code highlighting produc... 閱讀全文

posted @ 2010-09-29 00:27 AmazingCaddy 閱讀(264) | 評(píng)論 (0) | 編輯收藏

2010年9月7日

hdu 2966 In case of failure

摘要: http://acm.hdu.edu.cn/showproblem.php?pid=2966題目的意思是：平面上有n個(gè)點(diǎn)（n<100000），求每個(gè)點(diǎn)的最近點(diǎn)到該點(diǎn)的平方距離。KD_Tree可以解決此題。詳細(xì)資料可以參看此鏈接 http://en.wikipedia.org/wiki/Kd-tree，上面給出了算法。PS: 這道題時(shí)限開了恐怖的30秒。 hdu_2966Code high... 閱讀全文

posted @ 2010-09-07 11:26 AmazingCaddy 閱讀(597) | 評(píng)論 (1) | 編輯收藏

僅列出標(biāo)題下一頁

2010年9月

日

一

二

三

四

五

六

常用鏈接

留言簿

隨筆分類

隨筆檔案

傳送門

AekdyCoin
edwardmj
Felicia
forverlin
haozi
lccycc
matrix67
Puzzle
sha 崽
topsky
ZJ@coreBug