2.置換，置換的運算 置換的概念還是比較好理解的，《組合數學》里面有講。對于置換的冪運算大家可以參考一下潘震皓的那篇《置換群快速冪運算研究與探討》，寫的很好。*簡單題：（應該理解概念就可以了）pku3270 Cow Sorting http://acm.pku.edu.cn/JudgeOnline/problem?id=3270 pku1026 Cipherhttp://acm.pku.edu.cn/JudgeOnline/problem?id=1026 *置換冪運算：pku1721 CARDShttp://162.105.81.212/JudgeOnline/problem?id=1721 pku3128 Leonardo's Notebookhttp://162.105.81.212/JudgeOnline/problem?id=3128 *推薦：（不錯的應用）pku3590 The shuffle Problemhttp://162.105.81.212/JudgeOnline/problem?id=3590
3.素數，整數分解，歐拉函數素數是可能數論里最永恒，最經典的問題了（我們的隊名就叫PrimeMusic^-^）。素數的判斷，篩法求素數，大素數的判斷···還有很多其他問題都會用到素數。*最水最水的：（心情不爽時用來解悶吧）pku1365 Prime Landpku2034 Anti-prime Sequencespku2739 Sum of Consecutive Prime Numberspku3518 Prime Gappku3126 Prime Pathpku1595 Prime Cutspku3641 Pseudoprime numberspku2191 Mersenne Composite Numberspku1730 Perfect Pth Powerspku2262 Goldbach's Conjecturepku2909 Goldbach's Conjecture*篩法：pku2689 Prime Distance（很好的一個應用）http://162.105.81.212/JudgeOnline/problem?id=2689 *反素數：zoj2562 More Divisorshttp://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2562 *素數判斷，整數分解：這兩題都要用到miller_rabin的素數判斷和pollard_rho的整數分解，算法書上都會有，應該是屬于模板題吧，不過最好看懂自己敲一遍。pku1811 Prime Testhttp://acm.pku.edu.cn/JudgeOnline/problem?id=1811 pku2429 GCD & LCM Inversehttp://acm.pku.edu.cn/JudgeOnline/problem?id=2429 *歐拉函數：數論里很多地方都能用到歐拉函數，很重要的。pku1284 Primitive Roots （很水）http://acm.pku.edu.cn/JudgeOnline/problem?id=1284 pku2407 Relatives （很水）http://acm.pku.edu.cn/JudgeOnline/problem?id=2407 pku2773 Happy 2006http://162.105.81.212/JudgeOnline/problem?id=2773 pku2478 Farey Sequence （快速求歐拉函數）http://162.105.81.212/JudgeOnline/problem?id=2478 pku3090 Visible Lattice Points （法雷級數）http://acm.pku.edu.cn/JudgeOnline/problem?id=3090 *推薦：（歐拉函數，費馬小定理）pku3358 Period of an Infinite Binary Expansionhttp://acm.pku.edu.cn/JudgeOnline/problem?id=3358 *整數分解這個也很重要的耶，包括大數的表示方法。pku2992 Divisorshttp://acm.pku.edu.cn/JudgeOnline/problem?id=2992 fzu1753 Another Easy Problem http://acm.fzu.edu.cn/problem.php?pid=1753 hit2813 Garden visitinghttp://acm-hit.sunner.cn/judge/show.php?Proid=2813 pku3101 Astronomy （分數的最小公倍數）http://acm.pku.edu.cn/JudgeOnline/problem?id=3101
4.擴展歐幾里得，線性同余，中國剩余定理 這應該是數論里比較重要的一個部分吧，這類的題目也挺多，具體的內容最好先看看數論書，我也整理過一些，可以參考參考：http://hi.baidu.com/%B1%BF%D0%A1%BA%A2%5Fshw/blog/item/0676025d56a87d4afbf2c093.html *簡單題：pku1006 Biorhythmshttp://acm.pku.edu.cn/JudgeOnline/problem?id=1006 pku1061 青蛙的約會http://acm.pku.edu.cn/JudgeOnline/problem?id=1061 pku2891 Strange Way to Express Integershttp://acm.pku.edu.cn/JudgeOnline/problem?id=2891 pku2115 C Looooopshttp://acm.pku.edu.cn/JudgeOnline/problem?id=2115 pku2142 The Balancehttp://162.105.81.212/JudgeOnline/problem?id=2142 *強烈推薦：sgu106 The equation http://acm.sgu.ru/problem.php?contest=0&problem=106 pku3708 Recurrent Function （經典）http://acm.pku.edu.cn/JudgeOnline/problem?id=3708
5.約瑟夫環問題這個問題還是比較有意思的，不是很難。*簡單題：pku3517 And Then There Was Onehttp://acm.pku.edu.cn/JudgeOnline/problem?id=3517 pku1781 In Dangerhttp://acm.pku.edu.cn/JudgeOnline/problem?id=1781 pku1012 Josephhttp://162.105.81.212/JudgeOnline/problem?id=1012 pku2244 Eeny Meeny Moohttp://162.105.81.212/JudgeOnline/problem?id=2244 *推薦：pku2886 Who Gets the Most Candies?http://162.105.81.212/JudgeOnline/problem?id=2886
6.高斯消元法解方程其實解方程并不是很難，就是按線性代數中學的那種方法，把系數矩陣化成上三角矩陣或數量矩陣，不過有些題目要判斷是否有解，或枚舉所有解。不過這類題目我認為比較難的還是怎么去建立這個方程組，這個理解了，就沒什么大問題了。*簡單題：pku1222 EXTENDED LIGHTS OUThttp://162.105.81.212/JudgeOnline/problem?id=1222 pku1681 Painter's Problemhttp://162.105.81.212/JudgeOnline/problem?id=1681 pku1830 開關問題http://162.105.81.212/JudgeOnline/problem?id=1830 *推薦：pku2947 Widget Factoryhttp://162.105.81.212/JudgeOnline/problem?id=2947 pku2065 SETIhttp://162.105.81.212/JudgeOnline/problem?id=2065 *強烈推薦：pku1753 Flip Gamehttp://162.105.81.212/JudgeOnline/problem?id=1753 pku3185 The Water Bowlshttp://162.105.81.212/JudgeOnline/problem?id=3185 *變態題：pku1487 Single-Player Gameshttp://162.105.81.212/JudgeOnline/problem?id=1487 7.矩陣用矩陣來解決問題確實很常見，但我現在用到還不是很好，很多難題我還不會做。建議大家可以去看Matrix67的那篇關于矩陣的十個問題，確實很經典，但不太好看懂。*簡單：pku3070 Fibonaccihttp://162.105.81.212/JudgeOnline/problem?id=3070 pku3233 Matrix Power Serieshttp://162.105.81.212/JudgeOnline/problem?id=3233 pku3735 Training little catshttp://162.105.81.212/JudgeOnline/problem?id=3735
8.高次同余方程有關這個問題我應該是沒什么發言權了，A^B%C=D，我現在只會求D和B，唉，很想知道A該怎么求。就先推薦幾道題目吧，這里涉及到了一個baby-step，giant-step算法。fzu1759 Super A^B mod Chttp://acm.fzu.edu.cn/problem.php?pid=1759 pku3243 Clever Yhttp://162.105.81.212/JudgeOnline/problem?id=3243 pku2417 Discrete Logginghttp://162.105.81.212/JudgeOnline/problem?id=2417 hdu2815 Mod Treehttp://acm.hdu.edu.cn/showproblem.php?pid=2815
9.容斥原理，鴿巢原理 很有用的兩個定理，但好像單獨考這兩個定理的不是很多。*鴿巢原理：pku2365 Find a multiplehttp://162.105.81.212/JudgeOnline/problem?id=2356 pku3370 Halloween treatshttp://162.105.81.212/JudgeOnline/problem?id=3370 *容斥原理：hdu1695 GCDhttp://acm.hdu.edu.cn/showproblem.php?pid=1695 hdu2461 Rectangleshttp://acm.hdu.edu.cn/showproblem.php?pid=2461
10.找規律，推公式這類題目的設計一般都非常巧妙，真的是很難想出來，但只要找到規律或推出公式，就不是很難了。我很多都是在參考別人思路的情況下做的，能自己想出來真的很不容易。*個人感覺都挺不錯的：pku3372 Candy Distributionhttp://162.105.81.212/JudgeOnline/problem?id=3372 pku3244 Difference between Tripletshttp://162.105.81.212/JudgeOnline/problem?id=3244 pku1809 Regetnihttp://162.105.81.212/JudgeOnline/problem?id=1809 pku1831 不定方程組http://162.105.81.212/JudgeOnline/problem?id=1831 pku1737 Connected Graphhttp://162.105.81.212/JudgeOnline/problem?id=1737 pku2480 Longge's problemhttp://162.105.81.212/JudgeOnline/problem?id=2480 pku1792 Hexagonal Routeshttp://acm.pku.edu.cn/JudgeOnline/problem?id=1792
11.排列組合，區間計數，計數序列這些題目可能需要一些組合數學知識，基本上高中的知識就夠了。區間計數問題一般不難，但寫的時候需要仔細一些，各種情況要考慮到位。至于像卡特蘭數，差分序列，斯特靈數···都還挺有意思，可以去看看《組合數學》。*簡單題：pku1850 Codehttp://162.105.81.212/JudgeOnline/problem?id=1850 pku1150 The Last Non-zero Digithttp://162.105.81.212/JudgeOnline/problem?id=1150 pku1715 Hexadecimal Numbershttp://162.105.81.212/JudgeOnline/problem?id=1715 pku2282 The Counting Problemhttp://162.105.81.212/JudgeOnline/problem?id=2282 pku3286 How many 0's?http://162.105.81.212/JudgeOnline/problem?id=3286 *推薦：pku3252 Round Numbershttp://162.105.81.212/JudgeOnline/problem?id=3252 *計數序列：pku1430 Binary Stirling Numbershttp://162.105.81.212/JudgeOnline/problem?id=1430 pku2515 Birthday Cakehttp://acm.pku.edu.cn/JudgeOnline/problem?id=2515 pku1707 Sum of powershttp://acm.pku.edu.cn/JudgeOnline/problem?id=1707
12.二分法二分的思想還是很重要的，這里就簡單推薦幾個純粹的二分題。*簡單：pku3273 Monthly Expensehttp://162.105.81.212/JudgeOnline/problem?id=3273 pku3258 River Hopscotchhttp://162.105.81.212/JudgeOnline/problem?id=3258 pku1905 Expanding Rodshttp://162.105.81.212/JudgeOnline/problem?id=1905 pku3122 Piehttp://162.105.81.212/JudgeOnline/problem?id=3122 *推薦：pku1845 Sumdivhttp://acm.pku.edu.cn/JudgeOnline/problem?id=1845
13.穩定婚姻問題 無意中接觸到這個算法，還蠻有意思的，《組合數學》中有詳細的介紹。pku3487 The Stable Marriage Problemhttp://acm.pku.edu.cn/JudgeOnline/problem?id=3487 zoj1576 Marriage is Stablehttp://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1576
14.數位類統計問題 在航點月賽中第一次接觸到這類問題，scau大牛little龍推薦我看了一篇論文，09年劉聰的《淺談數位類統計問題》，這篇論文相當精彩，也相當詳細，每道題都有詳細的分析和作者的參考代碼。所以我也沒什么可說的了，這些題的代碼我博客里也就不貼了，大家直接去看論文吧。簡單：ural1057 Amount of degreeshttp://acm.timus.ru/problem.aspx?space=1&num=1057 spoj1182 Sorted bit squencehttps://www.spoj.pl/problems/SORTBIT/ hdu3271 SNIBBhttp://acm.hdu.edu.cn/showproblem.php?pid=3271 較難：spoj2319 Sequencehttps://www.spoj.pl/problems/BIGSEQ/ sgu390 Ticketshttp://acm.sgu.ru/problem.php?contest=0&problem=390
以上分類的題目在我的博客里都可以找到詳細的解題報告和參考代碼，由于比較麻煩就沒加鏈接，需要的可以用我的站內搜索找到。
Powered by: C++博客 Copyright © Kevin_Zhang
