下载文档原格式
实验1——统计字符数 1实验2——串匹配问题 3实验3——0/1背包问题 4实验4——哈夫曼编码 5实验1——统计字符数1．实验题目判断一个由a-z 这26 个字符组成的字符串中哪个字符出现的次数最多2．实验目的熟练掌握在acm竞赛中常出现的有关字符串操作题目3．实验要求设计实验程序验证分析结果。
4．输入输出样例Input：第1 行是测试数据的组数n，每组测试数据占1 行，是一个由a-z 这26 个字符组成的字符串，每组测试数据之间有一个空行，每行数据不超过1000 个字符且非空。
Output：n 行，每行输出对应一个输入。
一行输出包括出现次数最多的字符和该字符出现的次数，中间是一个空格。
如果有多个字符出现的次数相同且最多，那么输出ascii 码最小的那一个字符。
Sample Input2abbcccadfadffasdfSample Outputc 3f 4分析：每读入一个字符串，将这个字符串作为一个字符型数组，依次判断每个数组元素分别是什么字母。
统计出各个字母在字符串中分别出现了多少次，找到出现次数最多的。
这里要注意三点：(1)输入字符串时，可以象一般变量一样，一次输入一个字符串。
scanf函数通过空格或者回车字符判断一个字符串的结束。
而一般数组在输入时，每次只能输入一个数组元素。
(2)字符串是一个字符型数组，可以象访问一般数组的元素一样，通过下标访问其中的各个元素。
scanf函数输入字符串时，并不返回所输入字符串的长度。
可以使用字符串处理函数strlen函数计算字符串中包括多少个字符。
(3)输入的字符串中，可能有多个字符出现的次数相同且最多的情况。
此时要输出ascii 码最小的那一个字符。
实验2——串匹配问题1．实验题目给定一个文本，在该文本中查找并定位任意给定字符串。
2．实验目的⑴深刻理解并掌握蛮力法的设计思想；⑵提高应用蛮力法设计算法的技能；⑶理解这样一个观点：用蛮力法设计的算法，一般来说，经过适度的努力后，都可以对算法的第一个版本进行一定程度的改良，改进其时间性能。
acm程序设计竞赛基础教程
ACM程序设计竞赛基础教程是一本专门针对ACM程序设计竞赛的教程，该书由中国大学MOOC（慕课）在线教育平台和北京大学计算机科学与技术系合作，主要面向程序设计竞赛爱好者和准备参加竞赛的学生。
本教程共分为10个章节，从基础的算法和数据结构开始讲解，到高级的算法和数据结构，并涵盖了常见的编程语言和各种经典算法的实现和应用。
每个章节都有一些简单的例子和练习题，旨在帮助学生巩固所学的知识和提高编程能力。
本教程的作者是来自北京大学计算机科学与技术系的教授和研究生，他们有丰富的ACM竞赛经验和创新思维，对于如何有效地学习和练习编程有着深入的理解和实践。
同时，本教材也收录了一些国际著名的ACM竞赛题目和优秀的代码答案，以便学生更好地了解和掌握这个领域的最新进展和应用。
总之，ACM程序设计竞赛基础教程是一本集理论和实践于一体的学习资料，对于想要学习和了解ACM竞赛的人来说是一本必备的参考书。
ACM练习建议一位高手对我的建议：一般要做到50行以内的程序不用调试、100行以内的二分钟内调试成功.acm 主要是考算法的，主要时间是花在思考算法上，不是花在写程序与debug上。
下面给个计划你练练：第一阶段：练经典常用算法，下面的每个算法给我打上十到二十遍，同时自己精简代码，因为太常用，所以要练到写时不用想，10-15分钟内打完，甚至关掉显示器都可以把程序打出来.1.最短路(Floyd、Dijstra,BellmanFord)2.最小生成树(先写个prim,kruscal要用并查集，不好写)3.大数（高精度）加减乘除4.二分查找. (代码可在五行以内)5.叉乘、判线段相交、然后写个凸包.6.BFS、DFS,同时熟练hash表(要熟，要灵活,代码要简)7.数学上的有：辗转相除（两行内），线段交点、多角形面积公式.8. 调用系统的qsort, 技巧很多，慢慢掌握.9. 任意进制间的转换第二阶段：练习复杂一点，但也较常用的算法。
如：1. 二分图匹配（匈牙利），最小路径覆盖2. 网络流，最小费用流。
3. 线段树.4. 并查集。
5. 熟悉动态规划的各个典型：LCS、最长递增子串、三角剖分、记忆化dp6.博弈类算法。
博弈树，二进制法等。
7.最大团，最大独立集。
8.判断点在多边形内。
9. 差分约束系统.10. 双向广度搜索、A*算法，最小耗散优先.第三阶段：前两个阶段是打基础，第三阶段是锻炼在比赛中可以快速建立模型、想新算法。
这就要平时多做做综合的题型了。
1. 把oibh上的论文看看（大概几百篇的，我只看了一点点，呵呵）。
2. 平时扫扫zoj上的难题啦，别老做那些不用想的题.(中大acm的版主经常说我挑简单的来做:-P )3. 多参加网上的比赛，感受一下比赛的气氛，评估自己的实力.4. 一道题不要过了就算，问一下人，有更好的算法也打一下。
5. 做过的题要记好:-)50题第一类搜索(至少4题)1011 1033 1129 2049 2056 2488 2492 (稍难，也可并查集)第二类最短路(至少3题)1062 1125 1797 2253 2679 Bellman-Ford (难)第三类动态规划(至少6题，2479 and 2593必做)2479 and 2593 1015 1042 (也可贪心) 1141 1050 1080 1221 1260 2411 (稍难) 1276 第四类贪心(至少2题)1065 2054 (难) 1521 2709第五类并查集(至少2题)1861 1182 (难) 1308 2524第六类最小生成树(至少2题, 而且Prim 和Kruskal 至少各用一次)1251 1258 1789 2485第七类二分图(至少3题)1325 1469 2195 (KM 算法或最小费用最大流) (难) 2446 1422 and 2594第八类最大流(至少2题)1087 1459 1149 2516 (最小费用最大流) (难)第九类快速查找(B-Search, Hash and so on) (至少3题)2503 2513 (+Euler回路的判定) 1035 1200 2002第十类数论(至少2题)1061 1142 2262 2407 1811(难) 2447 (难)第十一类线段树(无最少题数要求)2352 (可用简单方法) 2528第十二类计算几何(至少2题，1113凸包算法必做)1113 1292 2148 (难) 2653 1584第十三类高精度(至少3题，1001必做)1001 1047 1131 1503 1504 1060 and 1996 (多项式)SCU1002, 1003, 1004 (/soj)第十四类模拟(至少5题)1029 and 1013 1083 and 2028 2234 and 1067 1012 1026 1068 1120 2271 2632第十五类数学(至少4题)2249 1023 2506 1079 1019 and 1095 1905 and 1064 (二分)POJ分类1、排序1423, 1694, 1723, 1727, 1763, 1788, 1828, 1838, 1840, 2201, 2376, 2377, 2380, 1318, 1877, 1928, 1971, 1974, 1990, 2001, 2002, 2092, 2379,1002（需要字符处理，排序用快排即可）1007（稳定的排序）2159（题意较难懂）2231 2371（简单排序）2388（顺序统计算法）2418（二叉排序树）2、搜索、回溯、遍历1022 1111 1118 1129 1190 1562 1564 1573 1655 2184 2225 2243 2312 2362 2378 23861010,1011,1018,1020,1054,1062,1256,1321,1363,1501，1650,1659,1664,1753,2078,2083,2303,2310,2329简单：1128, 1166, 1176, 1231, 1256, 1270, 1321, 1543, 1606, 1664, 1731, 1742, 1745, 1847,1915, 1950, 2038, 2157, 2182, 2183, 2381, 2386, 2426,不易：1024, 1054, 1117, 1167, 1708, 1746, 1775, 1878, 1903, 1966, 2046, 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 2080 （这种题要小心）4、枚举1012，1046，1387，1411，2245，2326，2363，2381，1054（剪枝要求较高），1650 （小数的精度问题）5、数据结构的典型算法容易：1182, 1656, 2021, 2023, 2051, 2153, 2227, 2236, 2247, 2352, 2395,不易：1145, 1177, 1195, 1227, 1661, 1834,推荐：1330, 1338, 1451, 1470, 1634, 1689, 1693, 1703, 1724, 1988, 2004, 2010, 2119, 2274, 1125(弗洛伊德算法) ，2421（图的最小生成树）6、动态规划1037 A decorative fence、1050 To the Max、1088 滑雪、1125 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、贪心1042, 1065, 1230, 1323, 1477, 1716, 1784,1328 1755（或用单纯形方法），2054，1017，1328，1862，1922 ，2054，2209，2313，2325，2370。
ACM入门训练指南目标读者：想要在ACM/ICPC里进行发展，并通过SDUTOJ进行训练的初学者。
使用语言：只要会一门程序设计语言，就可以进行ACM训练了。
通过训练，可以更好地掌握语言使用能力、程序和算法设计能力。
一般通用语言如C、C++和JAVA都可以，它们有各自的优势和缺点：1．C语言设计算法效率比较高，但输入输出的格式控制比较麻烦，而ACM 对程序进行评测时对输入输出的格式要求比较高，使用C务必要熟练掌握输入输出方法。
2．C++封装了输入输出流，方便输入输出操作，减少出错的可能性；C++提供了非常强大的标准模版库（STL），使得很多在C上实现起来比较麻烦的代码，在C++上却非常方便。
3．JAVA在大型工程和安全方面有比较独特的优势，但在ACM里面却不是一种优秀的语言，因为JAVA的执行效率要比C、C++慢很多，而ACM的题目都对程序运行时间有限制，如果题目限时比较紧的话，就不适合用JAVA，然而JAVA却提供了很方便的高精度运算（大整数运算）。
建议刚学完C就用纯C来训练，在训练过程中可以学习C++，有时间再把STL 好好学学。
输入输出：初次接触ACM训练时经常会遇到的问题，就是输入和输出问题。
如果对语言的输入输出问题不是很熟悉的话，一定要先重点研究一下，特别在输入和输出时不能有冗余信息，因为学习语言时可能习惯了使用提示信息来提高程序的交互性，但ACM不需要任何交互性。
不严格按照题目要求进行输入输出的程序是无法通过系统测试的。
在线评测系统：在线评测系统，英文叫Online Judge（简称OJ），是开放的程序自动评判系统。
只要能上网，注册并登录系统后，就可以选择题目，编写程序，提交程序代码，然后由系统自动进行编译和执行，并通过系统预设测试数据来检验程序代码的正确性。
通过使用OJ训练，可以提高编程和算法设计能力，随着训练的深入，可以参加在评测系统上举行的ACM-ICPC程序设计竞赛。
很多学校都有自己的在线评测系统，里面提供了很多题目给平时学习训练用。
《ACM程序设计竞赛》课程教学大纲(ACM Programming Contest )一、课程说明课程编码：045844301,课程总学时34、周学时2、学分2,开课学期：第7学期。
1.课程性质：本课程是专业任选课。
2.适用专业：适用于计算机科学与技术专业。
3.课程教学目的与要求：通过本学科的教学，使学生能掌握ACM竞赛的基本知识，掌握与了解计算机专业英语、高级数据结构、离散数学、初等数论、数值计算、计算机算法、人工智能、时空权衡、图算法、计算几何等等内容。
并能综合运用这些知识，利用程序语言进行ACM竞赛题目的设计与编写。
4.本门课程与其它课程关系：先修课：C程序设计语言，离散数学，数据结构，算法设计与分析，高等数学，线性代数5.推荐教材及参考书：(1)陈根方，《ACM程序设计竞赛讲义》，自编教材，2005.12。
(2)郭嵩山，崔昊，吴汉荣，陈明睿著，《国际大学生程序设计竞赛辅导教程》，北京大学出版社，2001年12月第1版。
6.课程教学方法与手段：结合具体的问题讲授概念与理论，辅以课堂讨论、做习题等多项教学手段。
7.课程考试方法与要求：平时考核与期终考核相结合。
平时考核包括作业与课堂表现，侧重于了解和督促学生的学习，占课程总评分的50%。
期末开卷考核侧重于考核学生对有关ACM题目的理解，考核学生运用具体知识与算法，分析与解决实际问题的能力，并促进学生对ACM的学习和钻研，占课程总评分的50%。
8.实践教学内容安排：在教学过程中，安排学生深入有关实际问题进行研究，加深对所学理论的认识，利用网站http://acm. z ju. edu. cn 进行程序设计。
实验一：字符串处理,No. 1623实验二：DFS 算法,No. 1909实验三：队列组处理,No. 1948实验四：树与搜索算法组合应用,No. 1002二、教学内容与学时分配教学内容与时间安排表序号内容总课时理论课时实践课时一ACM程序设计比赛介绍 2 2 0二计算机专业英语4 2 2三高级数据结构及ACM例题20 2四离散数学1 1 0五初等数论3 3 0六数值计算2 2 0七人工智能2 2 0八常用算法及ACM例题2 2 0九时空权衡及ACM例题2 2 0十动态规划算法4 2 2十一图算法6 4 2十二计算几何2 2 0十三ACM模拟例题综合分析2 2 0（一）ACM程序设计比赛介绍（2学时）1.主要内容ACM程序设计比赛，中国，浙江，本校ACM竞赛情况。
目录1.河内之塔 .............................................................................................................. 错误!未定义书签。
Gossip: 费式数列 ................................................................................................. 错误!未定义书签。
3.巴斯卡三角形 .................................................. 错误!未定义书签。
Gossip: 三色棋.................................................. 错误!未定义书签。
Gossip: 老鼠走迷官（一）........................................ 错误!未定义书签。
Gossip: 老鼠走迷官（二）........................................ 错误!未定义书签。
Gossip: 骑士走棋盘.............................................. 错误!未定义书签。
Gossip: 八皇后.................................................. 错误!未定义书签。
Gossip: 八枚银币................................................ 错误!未定义书签。
Gossip: 生命游戏................................................ 错误!未定义书签。
Gossip: 字串核对................................................ 错误!未定义书签。
