当前位置：文档库 › ACM经验之谈

ACM经验之谈

（一）

不可能都完全记住那么多的算法。

常用算法，拿过来就可以写出来。

不常用的，拿起书来看10分钟，就能理解算法（因为以前记过）。对以前没有记过的算法，就不好说了，难的可能要研究好几天。

应该熟练掌握的常用的算法应该有：

各种排序算法（插入排序、冒泡排序、选择排序、快速排序、堆排序、归并排序）

线性表（一般的线性表，栈，队列)的插入和删除）

二叉树的遍历（前序，中序，后序）

图的遍历（深度优先，广度优先）

二分法查找，排序二叉树，H a s h查找（处理冲突的方法）。

（二）

分析一个东西，你可以用不同的眼光去看待，有很多时候，就跟自己生活一样，觉得小时候看待问题很幼稚，现在看问题全面了，而且方式不一样了，为什么？就是成长吧。就跟这个一样的，你对算法，比如写一个程序，可能直接写很简单，可是可以有一些有趣的方式，比如通过什么样来表达，怎么样更高效…等等吧

（三）

大学里把基本的专业课学扎实就o k，如：数据结构，离散数学，操作系统等。碰到一些基本的数据结构和算法，如查找排序要根据原理马上能写出相应的代码就行了，我个人是这样理解的，对于更深层次

的东西，也是建立在自己熟练的基础之上的吧！

（四）

《算法与数据结构考研试题精析》陈守孔，第2版机械工业出版社如果你想练习的话，这里有N多的题可以来练习，但实际中能用到的比较少，除非搞一些高端的玩意，不过平时也可以在自己的项目中结合使用。

（五）

数据结构在平时可能用不上，但数据结构可以培养你写程序时如何注意效率的意识，一个学过数据结构的人和一个没有学过数结构的人写出来的程序可能在效率上有差别。

（六）

搞A C M需要掌握的是算法。

要注意，A C M的竞赛性强，因此应该和自己的实际应用联系起来。适合自己的才是好的，有的人不适合搞算法，喜欢系统架构，因此不要看到别人什么就眼红，发挥自己的长处,这才是重要的。

ACM题

求体积 #include #include #define PI 3.1415927 int main() { double x; while(scanf("%lf",&x)!=EOF) { printf("%.3lf\n",(4.0*PI*x*x*x)/3.0); } return 0; } 求a+b II. #include #include #define N 1005 char A[N],B[N],sum[N]; int main() { int T,i,j,k,x,sign; while(scanf("%d",&T)!=EOF) { for(i=0;i

{ sum[x]=(A[j]-'0')+(B[k]-'0')+sign-10; sign=1; } } #include using namespace std; int main() { int a, b; while(cin >> a >> b) cout << a + b << endl; return 0; 求a+b #include using namespace std; int main() { int a,b,s; while(cin>>a>>b) { s=a+b; cout< #include int main() { char s[3],a,b,c,temp; while(scanf("%s",s)!=EOF) { a=s[0];b=s[1];c=s[2]; if(a>b) { temp=a; a=b;

ACM竞赛试题集锦

取石子游戏 Time Limit:1S Memory Limit:1000K Total Submit:505 Accepted:90 Description 有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。 Input 输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000,000。 Output 输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。 Sample Input

2 1 8 4 4 7 Sample Output 1 跳蚤 Time Limit:1S Memory Limit:1000K Total Submit:198 Accepted:44 Description Z城市居住着很多只跳蚤。在Z城市周六生活频道有一个娱乐节目。一只跳蚤将被请上一个高空钢丝的正中央。钢丝很长，可以看作是无限长。节目主持人会给该跳蚤发一张卡片。卡片上写有N+1个自然数。其中最后一个是M，而前N个数都不超过M，卡片上允许

有相同的数字。跳蚤每次可以从卡片上任意选择一个自然数S，然后向左，或向右跳S个单位长度。而他最终的任务是跳到距离他左边一个单位长度的地方，并捡起位于那里的礼物。比如当N=2，M=18时，持有卡片(10, 15, 18)的跳蚤，就可以完成任务：他可以先向左跳10个单位长度，然后再连向左跳3次，每次15个单位长度，最后再向右连跳3次，每次18个单位长度。而持有卡片(12, 15, 18)的跳蚤，则怎么也不可能跳到距他左边一个单位长度的地方。当确定N和M后，显然一共有M^N张不同的卡片。现在的问题是，在这所有的卡片中，有多少张可以完成任务。 Input 两个整数N和M(N <= 15 , M <= 100000000)。 Output 可以完成任务的卡片数。 Sample Input

ACM经典算法及配套练习题

POJ上的一些水题(可用来练手和增加自信) (poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,p oj2255,poj3094) 初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序(poj1094) (5)二分图的最大匹配(匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) 三.数据结构. (1)串(poj1035,poj3080,poj1936) (2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299) (3)简单并查集的应用. (4)哈希表和二分查找等高效查找法(数的Hash,串的Hash) (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503) (5)哈夫曼树(poj3253) (6)堆 (7)trie树(静态建树、动态建树) (poj2513) 四.简单搜索 (1)深度优先搜索(poj2488,poj3083,poj3009,poj1321,poj2251) (2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414) (3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129) 五.动态规划 (1)背包问题. (poj1837,poj1276) (2)型如下表的简单DP(可参考lrj的书page149): 1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533) 2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159) 3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题) 六.数学 (1)组合数学:

Acm集训营培训心得

Acm集训营培训心得参加暑期acm训练营的培训，让我收获了好多，感想也特别特别多，也学会了许多。所以特别感谢集训营中为我们上课的老师对我们做的培训。经过特训营的培训，我了解到了许多关于acm的一系列知识。我感触特别深。作为ACM的新手，有兴趣而经验不足，然而有些热心的学者与老师多是向新手推荐书籍，如刘汝佳的算法竞赛入门经典，算法艺术与信息学竞赛及算法导论。不知这些是否是有针对ACM的系统教材，始终在这偌大的书籍中感到彷徨。但我觉得一方面它们倾向于理论证明、缺乏实战性，当时总是希望有位知识渊博的学者能带着我走。可这一切只是天方夜谭，更多的只能希冀在自己的身上。暑假集训从早上9点到下午5点，中间吃饭睡觉花掉3个小时左右，一天有6个小时上课时间，也许这段时间的确不是很长，每上五天课便会放假一天。看似好轻松，然而过于集中精力死盯这电脑屏幕，久而久之会有突如其来的疲倦。如果您想要从一个新手改造成一个合格的队员，你所感到的便是你的疯狂。引入ACM的历史，然后便是三道都是A+B，而且有样例程序培训，开始的第一节莫过于热身。这不仅能带给我们激情和勇气，同时看似基础性的东西却往往是胜败的关键点，使得我们不可松懈。接着便是从最简单的算法开始介绍，依次是：线性表，栈，队列，枚举法，递推法，递归法，分治法，树，搜索，图论的相关知识，并查集，动态规划，大数问题，字符串问

题。线性表，栈，队列：都有顺序结构和链式结构；栈和队列是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于基本操作的特殊性，栈必须按"后进先出"的规则进行操作，而队列必须按"先进先出"的规则进行操作。和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。而这三者都是来自数据结构的知识，数据结构数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。同时这门课程也是非常难学，需要我们花费更多的功夫。对于ACM的竞赛，更多的是注重于你对题目的灵活运用，采取比较简便的方法，所以便引入了枚举法，递推法，递归法，分治法，动态规划等技巧性较强的专门课程。复杂的ACM竞赛题往往蕴藏着精深的数学道理，需要的是数学知识的结合，学以灵活变通。就是这样才让人感觉到它是种让人从粗浅走向智慧，从蒙昧走向文明，从低级走向高级，从不完善走向完善的艰难历程。除了对这些学术上的专业注重，然而也需要学习英语知识，大多数的竞赛题目是英文，为了更加趋于国际化，英语也成为国际的交流语言，所以学习英语义不容辞，不可推卸。通过以上报告间隙，我结合自身学习实际，进行了客观的对比与反思。在今后的学生涯中，我要查漏补缺，通过学习来完善自身专业素养，努力为自己的梦想实践。

ACM题目整理

题目来源：福州大学acm网站代码：fpcdq 一、入门熟悉ACM竞赛规则以及程序提交注意事项例题： Problem 1000 A+B Problem Time Limit: 1000 mSec Memory Limit : 32768 KB Problem Description Calculate a + b. Input The input will consist of a series of pairs of integers a and b,separated by a space, one pair of integers per line. Output For each pair of input integers a and b you should output the sum of a and b in one line,and with one line of output for each line in input. Sample Input 1 5 2 3 Sample Output 6 5

My answer： #include main() { long a,b; while((scanf("%ld%ld",&a,&b))!=EOF) { printf("%ld\n",a+b); } } 详情参考https://www.wendangku.net/doc/7912879807.html,/faq.php 二、ACM分类主流算法： 1.搜索//回溯 Problem 1019 猫捉老鼠 Time Limit: 1000 mSec Memory Limit : 32768 KB Problem Description 一只猫和一只老鼠在10*10的迷宫中。迷宫中的每个方格可以是空的，或者含有障碍。猫和老鼠可以进入任意一个空的方格中。当他们相遇时，猫和老鼠在同一个方格中。但是，无论猫或老鼠都不能进入有障碍的方格。我们可以用字符组成的二维数组表示迷宫，如下图所示。

acm动态规划总结

动态规划题目总结(一) 对于一个有数字组成的二叉树，求由叶子到根的一条路径，使数字和最大，如： 7 38 8 1 0 2 7 4 4 4 5 2 6 5 这个是经典的动态规划，也是最最基础、最最简单的动态规划，典型的多段图。思路就是建立一个数组，由下向上动态规划，保存页子节点到当前节点的最大值，Java核心代码如下： for(int i=num-2;i>=0;i--){ for(int j=0;j<=i;j++){ //该句是整个动态规划的核心 number[i][j]=Math.max(number[i+1][j],number[i+1][j+1])+number[i][j]; } } Pku acm 1579 Function Run Fun 动态规划题目总结(二) Consider a three-parameter recursive function w(a, b, c): if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns: 1 if a > 20 or b > 20 or c > 20, then w(a, b, c) returns: w(20, 20, 20) if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) 这本身就是一个递归函数，要是按照函数本身写递归式，结果肯定是TLE，这里我开了一个三维数组，从w(0,0,0)开始递推，逐步产生到w(20,20,20)的值，复杂度O(n^3). 总结：这道题是很地道的DP，因为它的子问题实在是太多了，所以将问题的结果保存起来，刘汝佳《算法艺术和信息学竞赛》中115页讲到自底向上的递推，这个例子就非常典型。总体来说这个题目还是非常简单的，不过这个思想是地道的动态规划。 Pku acm 2081 Recaman's Sequence 动态规划题目总结(三) 一道很简单的动态规划，根据一个递推公式求一个序列，我选择顺序的求解，即自底向上的递推，一个int数组result根据前面的值依此求出序列的每一个结果，另外一个boolean数组flag[i]记录i是否已经出现在序列中，求result的时候用得着，这样就避免

Acm试题及答案

Acm试题及答案 1001 Sum Problem ............................................. 错误!未定义书签。1089 A+B for Input-Output Practice (I) ...................... 错误!未定义书签。1090 A+B for Input-Output Practice (II) ..................... 错误!未定义书签。1091 A+B for Input-Output Practice (III) .................... 错误!未定义书签。1092 A+B for Input-Output Practice (IV) ...................... 错误!未定义书签。1093 A+B for Input-Output Practice (V) ...................... 错误!未定义书签。1094 A+B for Input-Output Practice (VI) ..................... 错误!未定义书签。1095 A+B for Input-Output Practice (VII) ..................... 错误!未定义书签。1096 A+B for Input-Output Practice (VIII) ................... 错误!未定义书签。2000 ASCII码排序............................................ 错误!未定义书签。2001计算两点间的距离........................................ 错误!未定义书签。2002计算球体积.............................................. 错误!未定义书签。2003求绝对值................................................ 错误!未定义书签。2004成绩转换................................................ 错误!未定义书签。2005第几天.................................................. 错误!未定义书签。2006求奇数的乘积............................................ 错误!未定义书签。2007平方和与立方和.......................................... 错误!未定义书签。2008数值统计................................................ 错误!未定义书签。2009求数列的和.............................................. 错误!未定义书签。2010水仙花数................................................ 错误!未定义书签。2011多项式求和.............................................. 错误!未定义书签。2012素数判定................................................ 错误!未定义书签。2014青年歌手大奖赛_评委会打分............................... 错误!未定义书签。

ACM题目

【题目 1】N皇后问题(含八皇后问题的扩展，规则同八皇后)：在N*N的棋盘上，放置N个皇后，要求每一横行每一列，每一对角线上均只能放置一个皇后，问可能的方案及方案数。【题目 2】排球队员站位问题 ┏━━━━━━━━┓图为排球场的平面图，其中一、二、三、四、五、六为位置编号，┃ ┃二、三、四号位置为前排，一、六、五号位为后排。某队比赛时，┃ ┃一、四号位放主攻手，二、五号位放二传手，三、六号位放副攻┠──┬──┬──┨手。队员所穿球衣分别为１，２，３，４，５，６号，但每个队 ┃ 四 │ 三 │ 二 ┃员的球衣都与他们的站位号不同。已知１号、６号队员不在后排，┠──┼──┼──┨２号、３号队员不是二传手，３号、４号队员不在同一排，５号、┃ 五 │ 六 │ 一 ┃６号队员不是副攻手。 ┗━━┷━━┷━━┛编程求每个队员的站位情况。【算法分析】本题可用一般的穷举法得出答案。也可用回溯法。以下为回溯解法。【题目 2】把自然数Ｎ分解为若干个自然数之和。【参考答案】 n │ total 5 │ 7 6 │ 11 7 │ 15 10 │ 42 100 │ 190569291 【题目 3】把自然数Ｎ分解为若干个自然数之积。【题目 4】马的遍历问题。在Ｎ＊Ｍ的棋盘中，马只能走日字。马从位置(x,y)处出发，把棋盘的每一格都走一次，且只走一次。找出所有路径。【参考程序】 {深度优先搜索法} 【题目 5】加法分式分解。如：1/2=1/4+1/4.找出所有方案。输入：ＮＭＮ为要分解的分数的分母Ｍ为分解成多少项【题目 6】地图着色问题【题目 7】在n*n的正方形中放置长为2,宽为1的长条块,问放置方案如何【题目 8】找迷宫的最短路径。（广度优先搜索算法）

整理出ACM所有题目及答案

1111111杭电： 1000 A + B Problem (4) 1001 Sum Problem (5) 1002 A + B Problem II (6) 1005 Number Sequence (8) 1008 Elevator (9) 1009 FatMouse' Trade (11) 1021 Fibonacci Again (13) 1089 A+B for Input-Output Practice (I) (14) 1090 A+B for Input-Output Practice (II) (15) 1091 A+B for Input-Output Practice (III) (16) 1092 A+B for Input-Output Practice (IV) (17) 1093 A+B for Input-Output Practice (V) (18) 1094 A+B for Input-Output Practice (VI) (20) 1095 A+B for Input-Output Practice (VII) (21) 1096 A+B for Input-Output Practice (VIII) (22) 1176 免费馅饼 (23) 1204 糖果大战 (25) 1213 How Many Tables (26) 2000 ASCII码排序 (32) 2001 计算两点间的距离 (34) 2002 计算球体积 (35) 2003 求绝对值 (36) 2004 成绩转换 (37) 2005 第几天？ (38) 2006 求奇数的乘积 (40) 2007 平方和与立方和 (41) 2008 数值统计 (42) 2009 求数列的和 (43) 2010 水仙花数 (44) 2011 多项式求和 (46) 2012 素数判定 (47) 2014 青年歌手大奖赛_评委会打分 (49) 2015 偶数求和 (50) 2016 数据的交换输出 (52) 2017 字符串统计 (54) 2019 数列有序! (55) 2020 绝对值排序 (56) 2021 发工资咯：） (58) 2033 人见人爱A+B (59) 2037 今年暑假不AC (61) 2039 三角形 (63) 2040 亲和数 (64)

牛人的ACM-POJ的题型分类总结!

主流算法： ? 1.搜索//回溯 ? 2.DP（动态规划） ? 3.贪心 ? 4.图论//Dijkstra、最小生成树、网络流 ? 5.数论//解模线性方程 ? 6.计算几何//凸壳、同等安置矩形的并的面积与周长 ?7.组合数学//Polya定理 ?8.模拟 ?9.数据结构//并查集、堆 ?10.博弈论 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 2386 1010,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、

acm ZOJ刷题推荐

初学者题： 1001 1037 1048 1049 1051 1067 1115 1151 1201 1205 1216 1240 1241 1242 1251 1292 1331 1334 1337 1338 1350 1365 1382 1383 1394 1402 1405 1414 1494 1514 1622 1715 1730 1755 1760 1763 1796 1813 1879 1889 1904 1915 1949 2001 2022 2099 2104 2108 2172 2176 2201 2208 2321 2345 2351 2376 2388 2405 2417 2433 模拟问题： 1006 1009 1012 1016 1019 1023 1026 1028 1038 1042 1045 1051 1056 1057 1058 1061 1065 1066 1068 1072 1073 1078 1087 1088 1097 1098 1099 1103 1111 1121 1124 1126 1128 1133 1138 1146 1152 1154 1160 1175 1178 1187 1194 1207 1222 1224 1244 1259 1267 1274 1275 1277 1278 1279 1281 1282 1294 1295 1300 1308 1317 1324 1339 1351 1362 1392 1393 1397 1398 1399 1400 1402 1432 1434 1444 1452 1475 1487 1493 1497 1517 1526 1527 1530 1531 1552 1569 1573 1592 1601 1610 1623 1631 1641 1652 1657 1659 1682 1692 1700 1702 1707 1708 1712 1728 1732 1737 1746 1747 1750 1752 1754 1758 1764 1768 1774 1797 1799 1804 1807 1811 1822 1824 1831 1834 1837 1838 1842 1844 1845 1854 1858 1862 1870 1881 1884 1889 1896 1906 1921 1951 1969 1978 2000 2022 2040 2046 2047 2051 2072 2084 2101 2112 2131 2133 2138 2148 2153 2156 2160 2164 2172 2178 2184 2185 2187 2189 2193 2196 2201 2204 2208 2211 2212 2220 2229 2233 2239 2240 2261 2262 2269 2277 2288 2301 2309 2311 2312 2316 2320 2321 2322 2328 2330 2350 2389 2405 2410 2414 2420 2421 2483 2508 2560 2569 2572 2593 2613 2617 2680 2681 2731 2732 2743 动态规划：

部分ACM题目与答案

1001 Sum Problem (2) 1089 A+B for Input-Output Practice (I) (3) 1090 A+B for Input-Output Practice (II) (3) 1091 A+B for Input-Output Practice (III) (3) 1092 A+B for Input-Output Practice (IV) (3) 1093 A+B for Input-Output Practice (V) (3) 1094 A+B for Input-Output Practice (VI) (3) 1095 A+B for Input-Output Practice (VII) (3) 1096 A+B for Input-Output Practice (VIII) (3) 2000 ASCII码排序 (3) 2001计算两点间的距离 (3) 2002计算球体积 (3) 2003求绝对值 (3) 2004成绩转换 (3) 2005第几天？ (3) 2006求奇数的乘积 (3) 2007平方和与立方和 (3) 2008数值统计 (3) 2009求数列的和 (3) 2010水仙花数 (3) 2011多项式求和 (3) 2012素数判定 (3) 2014青年歌手大奖赛_评委会打分 (3) 2015偶数求和 (3) 2016数据的交换输出 (3) 2017字符串统计 (3) 2019数列有序! (3) 2020绝对值排序 (3) 2021发工资咯：） (3) 2033人见人爱A+B (3) 2039三角形 (3) 2040亲和数 (3)

DP类型各题总结-acm

最大连续子序列 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 11540 Accepted Submission(s): 4856 还需要输出该子序列的第一个和最后一个元素。对每个测试用例，在1行里输出最大和、最大连续子序列的第一个和最后一个元素，中间用空格分隔。如果最大连续子序列不唯一，则输出序号i和j最小的那个（如输入样例的第2、3组）。若所有K个元素都是负数，则定义其最大和为0，输出整个序列的首尾元素。思路：一路加如果sum变成小于0了从当前位置重新新开始加（小于0的话就对整个段没有贡献了而且会使整个段的和变小） #include int main() { int n,i,a[10005],start,end,sum,max,sta,flag,cnt; while(1) { cnt=0; sum=0;max=-1;flag=1; scanf("%d",&n); if(n==0) return 0; for(i=0;i

ACM部分练习题目答案

ACM部分习题答案： A + B Problem Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 100972 Accepted Submission(s): 33404 Problem Description Calculate A + B. Input Each line will contain two integers A and B. Process to end of file. Output For each case, output A + B in one line. Sample Input 1 1 Sample Output 2 # include Int main() {int x,y,s; while(scanf("%d %d",&x,&y)!=EOF) {s=x+y; printf("%d\n",s);} return 0; } Sum Problem Time Limit: 1000/500 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 85964 Accepted Submission(s): 19422 Problem Description Hey, welcome to HDOJ(Hangzhou Dianzi University Online Judge). In this problem, your task is to calculate SUM(n) = 1 + 2 + 3 + ... + n. Input The input will consist of a series of integers n, one integer per line. Output For each case, output SUM(n) in one line, followed by a blank line. You may assume the result will be in the range of 32-bit signed integer. Sample Input 1 100 Sample Output 1 5050 # include int main() {int n; long int s;

北大 poj acm题目推荐50题

-北大poj acm题目推荐50题 POJ == 北京大学ACM在线评测系统https://www.wendangku.net/doc/7912879807.html,/JudgeOnline 1. 标记难和稍难的题目大家可以看看，思考一下，不做要求，当然有能力的同学可以直接切掉。 2. 标记为A and B 的题目是比较相似的题目，建议大家两个一起做，可以对比总结，且二者算作一个题目。 3. 列表中大约有70个题目。大家选做其中的50道，且每类题目有最低数量限制。 4. 这里不少题目在BUPT ACM FTP 上面都有代码，请大家合理利用资源。 5. 50个题目要求每个题目都要写总结，养成良好的习惯。 6. 这50道题的规定是我们的建议，如果大家有自己的想法请与我们Email 联系。 7. 建议使用C++ 的同学在POJ 上用G++ 提交。 8. 形成自己编写代码的风格，至少看上去美观，思路清晰(好的代码可以很清楚反映出解题思路)。 9. 这个列表的目的在于让大家对各个方面的算法有个了解，也许要求有些苛刻，教条，请大家谅解，这些是我们这些年的经验总结，所以也请大家尊重我们的劳动成果。 10. 提交要求：一个总文件夹名为bupt0xx (即你的比赛帐号), 这个文件夹内有各个题目类别的子目录(文件夹)，将相应的解题报告放入对应类别的文件夹。在本学期期末，小学期开始前，将该文件夹的压缩包发至buptacm@https://www.wendangku.net/doc/7912879807.html,。对于每个题目只要求一个POJxxxx.cpp 或POJxxxx.java (xxxx表示POJ该题题号) 的文件，注意不要加入整个project 。 11. 如果有同学很早做完了要求的题目，请尽快和我们联系，我们将指导下一步的训练。下面是一个解题报告的范例：例如：POJ1000.cpp

acm题库[大全]

acm题库[大全] 座位调整题目描述: 百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，工作效率会大大提高。因此，百度决定进行一次员工座位的大调整。调整的方法如下: 1 ( 首先将办公区按照各种零食的摆放分成 N 个不同的区域。(例如:可乐区，饼干区，牛奶区等等)。 2 ( 每个员工对不同的零食区域有不同的喜好程度(喜好程度度的范围为 1 —100 的整数，喜好程度越大表示该员工越希望被调整到相应的零食区域)。 3 ( 由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案令到总的喜好程度最大。数据输入: 第一行包含两个整数 N ， M ，( 1<=N ， M<=300 )。分别表示 N 个区域和M 个员工。第二行是 N 个整数构成的数列 a ，其中 a[i] 表示第 i 个区域可以容纳的员工数， (1<=a[i]<=M ， a[1]+a[2]+..+a[N]=M) 。紧接着是一个 M*N 的矩阵 P ， P ( i ， j )表示第 i 个员工对第 j 个区域的喜好度。答案输出: 对于每个测试数据，输出可以达到的最大的喜好程度。 3 3

1 1 1 100 50 25 100 50 25 100 50 25 输出样例 175 3 10 2 4 4 100 50 25 100 50 25 100 50 25 100 50 25 100 50 25 100 50 25 100 50 25 100 50 25 100 50 25 100 50 25 2006 年百度之星程序设计大赛初赛题目 4 2007-05-14 17:39 剪刀石头布 N 个小孩正在和你玩一种剪刀石头布游戏。 N 个小孩中有一个是裁判，其余小孩分成三组(不排除某些组没有任何成员的可能性)，但是你不知道谁是裁判，也不知道小孩们的分组情况。然后，小孩们开始玩剪刀石头布游戏，一共玩 M 次，

(整理)ACM大量习题题库及建议培养计划.

//别人总结的，确实很多，但有信心就能学完！一.基本算法: (1)枚举.(poj1753,poj2965) (2)贪心.(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法.(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法.(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序.(poj1094) (5)二分图的最大匹配(匈牙利算法).(poj3041,poj3020) (6)最大流的增广路算法(KM算法).(poj1459,poj3436) 三.数据结构. (1)串.(poj1035,poj3080,poj1936) (2)排序(快排、归并排(与逆序数有关)、堆排).(poj2388,poj2299) (3)简单并查集的应用. (4)哈希表和二分查找等高效查找法.(数的Hash,串的Hash) (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503) (5)哈夫曼树.(poj3253) (6)堆. (7)trie树(静态建树、动态建树).(poj2513) 四.简单搜索 (1)深度优先搜索.(poj2488,poj3083,poj3009,poj1321,poj2251) (2)广度优先搜索.(poj3278,poj1426,poj3126,poj3087.poj3414) (3)简单搜索技巧和剪枝.(poj2531,poj1416,poj2676,1129) 五.动态规划 (1)背包问题. (poj1837,poj1276) (2)型如下表的简单DP(可参考lrj的书page149): 1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533) 2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159) 3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题) 六.数学 (1)组合数学: 1.加法原理和乘法原理. 2.排列组合. 3.递推关系. (POJ3252,poj1850,poj1019,poj1942) (2)数论.

ACM学习感想

学习ACM感想大二上半学期，由于报了大学生电子商务竞赛而进入实验室。在大一时，比较迷茫，不知道自己的专业什么内容重要，什么内容不重要。所以在大一下半学期学习C语言这门最基础的程序设计课的时候，老师上课在讲自己也不认真听讲。觉得只要考试能过就行了。结果考试是过了，但对于C语言还是一窍不通。在大二下班学期，由于选了面向对象程序设计和数据结构，老师的内容不怎么听的懂。开始认识到C语言的重要性，自己从头开始自学，把非计算机专业的C语言借来看，慢慢的赶上去，不懂的就问问同学。把书认真的看了两遍后，再接触接触计量OJ上的题目提高一下自己。就这样我开始接触了ACM。ACM=算法+数据结构。第一次接触ACM，刚开始做简单题的时候我也感觉并不容易，比如有些英文题目看起来比较费劲，要看很久才能搞清楚题目意思，有时候简单题目交上去不正确，题目有很多trick，有时候代码看多了，人就会觉得很厌倦和郁闷，但是不要灰心，我觉得做什么事贵在坚持，只要坚持下来，就会越来越体会到ACM 的无穷乐趣了。后来自己独立思考，把一些没有算法的题目基本上都提交成功了。也觉得有一些成就感，从一点都不会到现在能把一些简单的题目解决。有算法的题目，就自己百度或查一些资料，由于没有老师的指导，有些算法还是模棱两可。在数据结构的课上，老师也给我们介绍了一些算法。下面是我自己总结的算法：一.基本算法: (1)枚举. (2)贪心 (3)递归和分治法 (4)递推 (5)构造法 (6)模拟法二.图算法 (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法 (3)最小生成树算法 (4)拓扑排序 (5)二分图的最大匹配 (6)最大流的增广路算法(KM算法) 三.数据结构 (1)串 (2)排序(快排、归并排(与逆序数有关)、堆排) (3)简单并查集的应用. (4)哈希表和二分查找等高效查找法 (5)哈夫曼树 (6)堆 (7)trie树(静态建树、动态建树)