第一篇：ACM 筛素数总结

【总结】关于求素数的说【两种筛法】（学习小结，请无视）

素数大家都很熟了，不多说了，这里只想说一下求素数。

当然先是唯一素因子分解定理：合数a仅能以一种方式，写成如下的乘积形式：a=p1e1p2e2…prer 其中pi为素数，p1

对于一个整数n，当其在 小于sqrt（n）范围里有一个约数，那么必然在 大于sqrt（n)的范围里有对应的另一个Eratosthenes（埃拉托斯特尼筛法）都是到 sqrt（n）的范围。①。试除法判素数

对于大于1的正整数a，如果a具有小于或等于sqrt（a）的素因子，则a为合数，否则a为素数。

因此，可用区间[2,sqrt(a)]内的数去试除a，只要有一个数能整除a，则a为合数，否则a为素数。这种判断素复杂度O(sqrt(n)).IsPrime(a)for(i=2;i*i<=a;i++)if(a%i==0)return a为合数

return a为素数

②。Sieve Of Eratosthenes（埃拉托斯特尼筛法）可以筛出2~n 范围里的所有素数。

1)将所有候选数2~n放入筛中;2)找出筛中最小数P，P一定为素数。

3)宣布P为素数，并将P的所有倍数从筛中筛去;4)重复2)至3)直到筛空.其实，当P>sqrt(n)时筛中剩下的数就已经都是素数了。//用数组prime[MAXN]记录是否为素数； //prime[i]为0表示i为素数，否则为合数 int prime[MAXN]={0};for(i=2;i*i<=n;i++){ if(prime[i]==0){ for(j=i+i;j<=n;j+=i)prime[j]=1;} } ③。线性筛法

对于Sieve Of Eratosthenes，普通的筛法如果是一个合数，那么会被多次筛掉，比如6,当2作为素数时筛掉一线性筛法保证所有合数只被筛掉一次

具体详见《ftfish利用积性函数的优化》，讲到了 积性函数（对于正整数n的一个算术函数f(n)，当中f(1)=1且称它为积性函数。）

for(int i = 2;i < maxn;i ++){ if(!fg[i])prim[np++] = i;//如果没被筛掉，那么就是素数

for(int j = 0;j < np && i*prim[j] < maxn;j ++){ //注意i不是素数的时候也筛

fg[i*prim[j]] = 1;if(i % prim[j] == 0)break;//这一步保证了筛法是线性的，这是整个算法的关键

} } 摘：

利用了每个合数必有一个最小素因子。

每个合数仅被它的最小素因子筛去正好一次。所以为线性时间。代码中体现在：

if(i%prime[j]==0)break;prime数组 中的素数是递增的,当 i 能整除 prime[j]，那么 i*prime[j+1] 这个合数肯定被 prime[j] 乘以某个数筛因为i中含有prime[j], prime[j] 比 prime[j+1] 小。接下去的素数同理。所以不用筛下去了。在满足i%pr[j]==0这个条件之前以及第一次满足改条件时,pr[j]必定是pr[j]*i的最小因子。

第二篇：ACM赛后总结

赛后总结

虽然已经是大二第二学期了，这却是我的第一真正的ACM比赛经历，赛后感觉自己水平很差，感觉很不好，或许只有受到了了打击，才会有成长，也只有在一次次的打击中吸取经验，成为自己前进的动力。

这次比赛总结起来发现了我们的好多不足之处，第一个就是我们经验的缺失，毕竟是我们第一次参加这样的比赛，还有就是对做题顺序的把握不好，对题目难易程度判断不准确，如果做一个题发现思路错了，我们应该要及时改变思路，跳过去，先去做下面容易的题，等回过头来在做，要用尽量短的时间把我们知道做的题做出来，有些题，我们有思路，不敢保证完全做出来，就放到后面再去做，还有就是比赛的时候心态不好，中间做的时候就比较焦急，这样对自己的思路也会有影响，要调节好自己的情绪，还有就是要及时改变策略，多看榜，看到有很多人a的题目，我们肯定要去看一下，一开始我们就应该把题目全部都看一遍，最重要的是我们的实力还是不行，对于有些简单的题目还是不够熟练，思路不够清晰，下阶段要进一步有针对的加强训练！

比赛结束，我们真的是百感交集，有过遗憾，有过不甘心，有过失望，本来这次比赛应该是很好拿奖的，但最终我们还是与奖状擦肩而过，可能与经验的缺乏有关，我想更多的应该还是实力的差距，自己的实力不行，做什么都是白搭。所幸的是，我们明年还有一次机会，再努力一年，我想我们明年再战的时候，一定可以取得一个很好的成绩。

14物联网 贾文彪

第三篇：ACM错误汇总

出错种类与问题解决

结果如果不是Accepted，那么我也恭喜你。你和OJ题目搏斗的生涯从此开始了！其实也不用灰心丧气，程序写出来哪有不出错的，让我们来一点一点分析，修改程序让它通过吧！

常见错误与原因分析

Compile Error

编译错，就是程序写出来编译报错。程序还没调通就提交？如果在本地通过了调试还出现上述问题，可以注意一下是不是犯了以下错误。

贴程序的时候没贴全——少个分号什么的到了平台上自然会告诉你编译错 语言选择错误——C语言的代码用JAVA的编译器编译无论如何也不能对…… Wrong Answer

常见错误之一，程序输出了错误的结果。

首先查一下自己的算法是否正确，之后再检查一下是不是有什么边界情况没有考虑到吧。有些程序会有很恶心的情况的，比如说0长度数组之类的。边界情况考虑的越全面这类错误可能发生的情况越小。

Runtime Error

常见错误之二，程序出现了运行时段错误。

最可能由于越界访问数据或者空指针等潜在问题导致。编程时注意程序的规范性可以有效的规避此类错误。

Time Limit Exceeded

程序执行超时。可能你的算法不够优。尽量减少循环的重数吧！

Memory Limit Exceed

占用内存超过限制。

程序中申请了过多的空间，有可能用了大数组吧?试着少申请一些空间或者使用动态内存申请并且及时释放这些无用的空间吧！

Output Limit Exceed

输出了过多的东西，应该好好检查代码中输入输出的部分，看看是不是陷入的死循环。

Presentation Error

初学者最经常犯的错误，输出格式错误。

好好观察Sample output，看看是不是多打了个/n什么的。我当时被这种错误郁闷了好久……

第四篇：ACM组织机构

组织机构及职能

协会内设主席团（正理事一名，副理事三名），下设宣传部、技术部、外联部、组织部、秘书部，各部设部长一人，副部长两人，干事若干。各部门成员对协会负责，协会对各会员负责。

一、主席团职责：

（1）负责拟定本协会的发展计划，把握发展及创新方向，负责制定种规章制度及活动方案，代表本协会与外界进行交流；

（2）执行大会决议，任免各部门负责人，定期对协会的阶段工作做总结；

（3）管理协会日常事务，做好各种活动的筹划准备及善后工作；

（4）协调并指导各部门开展工作，了解各部门的工作情况；

（5）负责协会所有的财务管理及会员大会授予的其他职权。

二、宣传部职责：对外宣传

（1）负责协会的形象设计，如口号、会徽、会服工作证、名片等的设计；

（2）负责对外宣传，利用多种有效的宣传手段，提升本协会的影响力，树立本协会良好的社团形象；

（3）利用海报、宣传单、横幅、流动板等各种形式在每次活动前充分做好宣传，之后积极做好活动总结。

三、外联部职责：筹措资金

（1）作为协会的窗口，有义务对外宣传协会，提高协会知名度，扩大在校外影响力；

（2）负责了解市场行情，把握市场动向，为会员和非会员介绍市场；

（3）与商家建立合作关系以取得技术上支持，并以合法、合理的方式为协会筹措活动经费和发展资金；

（4）主动、积极地与其它高校或有关的社团以及社会媒体沟通接触, 为社团的进一步发展创造良好的外部环境。

四、技术部职责：

（1）作为协会的技术指导，负责协会的义务维修、网站设计维护、装机咨询等技术方面的问题；

（2）维护协会的网络管理，在网络上及时发布协会的活动安排、培训通知等相关信息；

（3）积极开展社会实践活动。

五、秘书部职责：联系会员 统计信息

（1）管理协会所有人力资源、通讯录及会员证的发放；

（2）负责活动的计划统筹，并联系协会各个会员；

（2）负责大会的记录、签到，资料整理，文件的起草和拟定；

（3）组织招干、考核评选、干部培训换届等工作。

六、组织部职责：对内协调

（1）负责提出新颖的活动构想、编写活动策划书；

（2）进行各项活动的组织与实施，活动现场的人员调配、布置工作，维持活动期间的秩序，保证活动的顺利开展；

（3）协调各部门之间的交流，开展协会内部的各项联谊活动。

第五章 会员大会

一、会员大会行使以下权利：

（1）听取和审查部门提交的工作报告；

（2）商讨并决定本协会的重大事务‘

（3）修改本协会的章程；

（4）选举各部门负责人。

第六章 协会活动

一、协会以授课方式向会员传授计算机应用知识，并不定期的组织会员培训，上机实践。

二、协会根据具体情况举行有协会特色的活动。

三、在活动中表现突出者给予表彰。

四、协会定期请专业人士或老师为会员授课指导或举行讲座。

五、积极发展同其他社团之间的合作交流。

六、积极配合院团委开展工作。具体人员任职

理事长：张浩奇

副理事：谷瑞 陈雅琦王奕蓝

宣传部：

杨书乐市场营销 ***

QQ494803545

刘亚男材料成型学号6126227

外联部：部长。艾文鹏 2123504 计算机与通信工程

部长.胡霄燕,语言学院4121206 电话***

副部 2121407 谭耀程 大计院 ***

副部长 2123318 *** 张宾宾

吕鑫2123107 吕鑫 ***。

陈思 数学与统计学院 信息与计算科学 ***

组织部：李梅 1123117 ***部长

杨一帆。2123411。计算机与通信学院

2123221

杨容清 ***

技术部：下设acm竞赛部 项目部技术小组

项目部王超嘛

竞赛部，正部，赵晓鹏，副部，徐进 ***赵晓鹏

***徐进

·刘秉天 23:37:54

我就在高中阶段计算机课时学过一点办公软件，例如WORD，EXCEL，POWERPOINT，以及网页的一点东西刘秉天，学号：2125125 电话：***

5123202.刘鹏.数学与统计学院，我电话是***

副的吧，我需要学习，吴凯宏6124202手机号***宿舍2245

冉龙梅

陈函 ***qq.729757478

秘书部：彭圆圆~1122424~***部长

田乐炜，1127223，经贸学院，***。。副部长吧，，部长了。我是王东亚，学号是1126212,联系方式是***

孔令朝2121416***

闵洁，学号是4121129，语言学院英语专业，电话是***,报名秘书部部长。

第五篇：ACM题目分类总结及pku题目分类

ACM题目分类总结及pku题目分类

ACM-题型分类的代码 主流算法：

1．搜索 //回溯 2． DP（动态规划）

3．贪心

4．图论 //Dijkstra、最小生成树、网络流 5．

数论 //解模线性方程

6．计算几何 //凸壳、同等安置矩形的并的面积与周长 7．

组合数学 //Polya定理 8．

模拟

9．数据结构 //并查集、堆 10． 博弈论

1、排序 , 1723, 1727, 1763, 1788, 1828, 1838, 1840, 2201, 2376, 2377, 2380, 1318, 1877, 1928, 1971, 1974, 1990, 202_, 202_, 202_, 2379，1002（需要字符处理，排序用快排即可）1007（稳定的排序）2159（题意较难懂）2231 2371（简单排序）2388（顺序统计算法）2418（二叉排序树）

2、搜索、回溯、遍历

1022 1111 1118 1129 1190 1562 1564 1573 1655 2184 2225 2243 2312 2362 2378 2386 1010 1011 1018 1020 1054 1062 1256 1321 1363 1501 1650 1659 1664 1753 202_ 202_ 2303 2310 2329

简单：1128, 1166, 1176, 1231, 1256, 1270, 1321, 1543, 1606, 1664, 1731, 1742, 1745, 1847, 1915, 1950, 202_, 2157, 2182, 2183, 2381, 2386, 2426

不易：1024, 1054, 1117, 1167, 1708, 1746, 1775, 1878, 1903, 1966, 202_, 2197,2349 推荐：1011, 1190, 1191, 1416, 1579, 1632, 1639, 1659, 1680, 1683, 1691, 1709, 1714, 1753, 1771, 1826, 1855, 1856, 1890, 1924, 1935, 1948, 1979, 1980, 2170, 2288, 2331, 2339, 2340,1979（和迷宫类似）1980（对剪枝要求较高）

3、历法

1008 202_（这种题要小心）

4、枚举

1387，2363，2381，1054（剪枝要求较高），1650（小数的精度问题）

5、数据结构的典型算法

容易：1182, 1656, 202_, 202_, 202_, 2153, 2227, 2236, 2247, 2352, 2395, 不易：1145, 1177, 1195, 1227, 1661, 1834，推荐：1330, 1338, 1451, 1470, 1634, 1689, 1693, 1703, 1724, 1988, 202_, 202_, 2119, 2274, 1125(弗洛伊德算法)，2421（图的最小生成树）

6、动态规划

1037 A decorative fence 1050 To the Max 1088 滑雪

Stockbroker Grapevine 1141 Brackets Sequence 1159 Palindrome 1160 Post Office 1163 The Triangle 1458 Common Subsequence 1579 Function Run Fun 1887 Testing the CATCHER 1953 World Cup Noise 2386 Lake Counting7、贪心 , , 1230, 1323, 1477, 1716, 1784,1328 1755（或用单纯形方法）,202_,1017,1328,1862, 1922, 202_,2209,2313,2325,2370

8、模拟

容易：1006, 1008, 1013, 1016, 1017, 1169, 1298, 1326, 1350, 1363, 1676, 1786, 1791, 1835, 1970, 2317, 2325, 2390，不易：1012, 1082, 1099, 1114, 1642, 1677, 1684, 1886,1281 1928 202_ 2141 202_

9、递归 1664

10、字符串处理

1488, 1598, 1686, 1706, 1747, 1748, 1750, 1760, 1782, 1790, 1866, 1888, 1896, 1951, 202_, 2121, 2141, 2145, 2159, 2337, 2359, 2372, 2406, 2408, 1016 1051 1126 1318 1572 1917 1936 202_ 202_ 2136 2271 2317 2330，2121 2403

11、数论

1014, 1023, 1061, 1152, 1183, 1730, 2262

12、几何有关的题目

凸包：1113, 1228, 1794, 202_, 2187,1113 wall，2187 beauty contest 容易：1319, 1654, 1673, 1675, 1836, 202_, 2137, 2318, 不易：1685, 1687, 1696, 1873, 1901, 2172, 2333，13、任意精度运算、数字游戏、高精度计算

1001 1023 1047 1060 1079 1131 1140 1142 1207 1220 1284 1289 1306 1316 1338 1405 1454 1503 1504 1519 1565 1650 1969 202_ 202_ 202_ 2247 2262 2305 2316 2389 1001, 1220, 1405, 1503,1001（高精度乘法）2413(高精度加法，还有二分查找)

14、概率统计 1037,1050

15、小费用最大流、最大流

2195 going home

2400 supervisor, supervisee 1087 a plug for UNIX 1149 PIGS

1273 drainage ditches 1274 the perfect stall 1325 machine schedule 1459 power network 2239 selecting courses16、压缩存储的DP

1038 bugs integrated inc，1185 炮兵阵地，2430 lazy cow

17、最长公共子串（LCS）

1080 human gene functions，1159 palindrome，1458 common subsequence，2192 zipper

18、图论及组合数学

2421 Constructing Roads 2369 Permutations 2234 Matches Game 2243 Knight Moves 2249 Binomial Showdown 2255 Tree Recovery 202_ Game of Connections 1906 Three powers 1833 排列 1850 Code

1562 Oil Deposits 1496 Word Index 1306 Combinations

1125 Stockbroker Grapevine 1129 Channel Allocation 1146 ID Codes

1095 Trees Made to Order找规律 2247 Humble Numbers 2309 BST

2346 Lucky tickets 2370 Democracy in danger 2365 Rope

2101 Honey and Milk Land 202_ When Can We Meet? 202_ Game of Connections 1915 Knight Moves 1922 Ride to School

1941 The Sierpinski Fractal 1953 World Cup Noise

1958 Strange Towers of Hanoi 1969 Count on Canton 1806 Manhattan 202_ 1809 Regetni 1844 Sum

1870 Bee Breeding 1702 Eva‘s Balance 1728 A flea on a chessboard 1604 Just the Facts 1642 Stacking Cubes 1656 Counting Black

1657 Distance on Chessboard 1662 CoIns 1663 Number Steps 1313 Booklet Printing 1316 Self Numbers 1320 Street Numbers 1323 Game Prediction 1338 Ugly Numbers 1244 Slots of Fun 1250 Tanning Salon 1102 LC-Display 1147 Binary codes 1013 Counterfeit Dollar

19、博弈类

1067 取石子游戏 1740 A New Stone Game 2234 Matches Game 1082 Calendar Game 2348 Euclid‘s Game 2413 How many Fibs? 2419 Forest20、简单、模拟题

1001 Exponentiation 1002 487-3279 1003 Hangover

1701 Dissatisfying Lift 2301 Beat the Spread!2304 Combination Lock 2328 Guessing Game 2403 Hay Points 2406 Power Strings

2339 Rock, Scissors, Paper 2350 Above Average

2218 Does This Make Me Look Fat? 2260 Error Correction 2262 Goldbach‘s Conjecture 2272 Bullseye

2136 Vertical Histogram 2174 Decoding Task 2183 Bovine Math Geniuses 202_ Gold Coins 202_ Flow Layout 202_ Argus 202_ Calendar 1918 Ranking List 1922 Ride to School 1970 The Game 1972 Dice Stacking 1974 The Happy Worm 1978 Hanafuda Shuffle 1979 Red and Black 1617 Crypto Columns 1666 Candy Sharing Game 1674 Sorting by Swapping 1503 Integer Inquiry

1504 Adding Reversed Numbers 1528 Perfection

1546 Basically Speaking 1547 Clay Bully 1573 Robot Motion

1575 Easier Done Than Said? 1581 A Contesting Decision 1590 Palindromes

1454 Factorial Frequencies 1363 Rails

1218 THE DRUNK JAILER 1281 MANAGER 1132 Border

1028 Web Navigation21、初等数学

1003 Hangover 1045 Bode Plot

1254 Hansel and Grethel 1269 Intersecting Lines 1401 Factorial 1410 Intersection 2363 Blocks 2365 Rope

2242 The Circumference of the Circle 2291 Rotten Ropes 2295 A DP Problem

2126 Factoring a Polynomial 2191 Mersenne Composite Numbers 2196 Specialized Four-Digit Numbers 1914 Cramer‘s Rule 1835 宇航员 1799 Yeehaa!1607 Deck

1244 Slots of Fun 1269 Intersecting Lines 1299 Polar Explorer 1183 反正切函数的应用

22、匹配

1274, 1422, 1469, 1719, 202_, 2239，23、经典

1011（搜索好题）

1012（学会打表）1013

1019（它体现了很多此类问题的特点）1050（绝对经典的dp）1088（dp好题）

1157（花店，经典的dp）

1163（怎么经典的dp那么多呀？？？）1328（贪心）

1458（最长公共子序列）

1647（很好的真题，考临场分析准确和下手迅速）1654（学会多边形面积的三角形求法）1655（一类无根树的dp问题）1804（逆序对）

202_（经典组合数学问题）

2187（用凸包求最远点对，求出凸包后应该有O(N)的求法，可我就是调不出来）2195（二分图的最佳匹配）2242（计算几何经典）2295（等式处理）

2353（dp，但要记录最佳路径）2354（立体解析几何）2362（搜索好题）2410（读懂题是关键）2411（经典dp）

24、趣味

1067（很难的数学，但仔细研究，是一片广阔的领域）1147（有O(n)的算法，需要思考）

1240（直到一棵树的先序和后序遍历，那么有几种中序遍历呢？dp）1426（是数论吗？错，是图论！）

1648（别用计算几何，用整点这个特点绕过精度的障碍吧）1833（找规律）

1844（貌似dp或是搜索，其实是道有趣的数学题）1922（贪心，哈哈）2231

2305（不需要高精度噢）2328（要仔细噢）2356（数论知识）2359（约瑟夫问题变种）2392（有趣的问题）

25、很繁的题

1001 1008

1087（构图很烦，还有二分图的最大匹配）1128（USACO）1245 1329

1550（考的是读题和理解能力）1649（dp）

2200（字符串处理+枚举）2358（枚举和避免重复都很烦）2361（仔细仔细再仔细）

26、难题

1014（数学证明较难，但有那种想法更重要）1037（比较难的dp）

1405（高精度算法也有等级，不断改进吧）202_（有没有比O(n^2*logn)更有的算法？）202_（极难，很强的思考能力）202_（组合数学）2414（dp，但要剪枝）2415（搜索）

2423（计算几何+统计）

27、多解题

1002（可以用排序，也可以用统计的方法）1338（搜索和dp都可以）1664（搜索和dp都练一练吧）202_（这可是我讲的题噢）2352（桶排和二叉树都行）

28、Note:

1011: 很经典的剪支 1014: 难在数学上

1017: 严格的数学证明貌似不容易 1021: 有点繁,考察对图形进行各种旋转 1083: 巧妙的思考角度 1150: 分奇偶讨论,lg(n)算法

1218: 三行就够,虽然简单,但也有优劣之别 1505: 二分加贪心

1654: 做法也许很多,本人用有向面积做的 1674: 计算圈的个数(算是graph 吧)1700: 数学证明不容易 1742: O(m*n)的算法 1863: 要耐心地慢慢写…^_^ 1988: 并查集 202_: 堆

202_: 不难，但剪支可以做到很好 202_::O(n),你想到了吗？ 202_: 卡特兰数 2182: 线段树

2195: 最小费用最大流 2234: 经典博弈算法 2236: 并查集 2299: 二分思想

2395: Kruskal 最小生成树的拓展 2406: KMP

2411: 用二进制串来表示状态