ACM竞赛简介和入门
ACM竞赛简介：
ACM国际大学生程序设计竞赛是由国际计算机界历史悠久、颇具权威性的组织ACM学会（美国计算机协会）主办，是世界上公认的规模最大、水平最高的国际大学生程序设计竞赛，其目的旨在使大学生运用计算机来充分展示自已分析问题和解决问题的能力。(网上有更详细的介绍，这里只做个简介)
ACM竞赛特点：
竞赛中一般有10道题，比赛时间为5个小时，每支参赛队伍由3名选手组成，可以携带诸如书、手册、程序清单等参考资料，对每一道题编完代码后，将代码提交裁判，每一次提交会被判为正确或者错误，判决结果会及时通知参赛队伍。
在规定时间内提交并通过题目数越多排名越靠前。（时间5小时，题目8~12题，同题目数按所用时间多少排名）
ACM题目限制：
时间限制（即程序运行所用的时间）空间限制（即程序运行时所开内存的多少）
ACM基本要求
?英语
?分析理解能力
?算法
?编码
?合作
ACM竞赛意义
学习编程，并不是为了参加竞赛，ACM竞赛对于我们的意义更多的还是专业能力的提高。在备战过程中，无论是对自己的编程能力，还是团队合作解决问题的能力，都是一种很好的锻炼机会。一般而言，每个在做ACM竞赛的学生，他们的编程能力会比较出色。与数学建模相比，由于ACM竞赛针对的是我们学计算机的同学，所以没有数学建模的比赛规模，但是依旧是国际上最有影响力的大学生竞赛之一。
ACM竞赛入门
现在有很多大学有专门为ACM竞赛开设自己的测评网站，上面有很多贴近竞赛的题目。比如说北大poj，浙大zoj等等。所以选择一个自己专门练习的网站，我们都用北大的poj，然后开始自己在上面做题，和同学交流经验。等到回到本部，要是有了一定的实力和基础，张震老师就会对我们进行选拔和组队，最后参加省赛和亚洲的区域赛。
?在poj上做20左右道简单的题目，熟悉ACM题目的基本特点。（这里列出几道相对
较简单的题目的题号：1000，1003，1004，1046，1207，1226，1504，1552）
?熟悉了poj之后，按照poj的题目分类，买一本或借一本算法的书（暨大ACM校队
的基本都用机械工程出版社的《算法导论》）开始学习，然后做算法的专题，一般每个专题做10~30道。主流的算法分类为：
1.搜索//回溯
2.DP（动态规划）
3.贪心
4.图论//Dijkstra、最小生成树、网络流
5.数论//解模线性方程
6.计算几何//凸壳、同等安置矩形的并的面积与周长
7.组合数学//Polya定理
8.模拟
9.数据结构//并查集、堆
10.博弈论
?专题做完后，你已经很强了，就可以找另外2个同学或师兄组成自己的队伍，开始
做poj上的难题，开始模拟比赛，为今后的竞赛做准备。
如何在北大测评poj网站上开始做题：
?上网站：https://www.wendangku.net/doc/cb14266875.html,/JudgeOnline/
?注册新账号：
点击Register注册。
?登陆
?选择题目-> 读题-> 分析-> 设计
?在自己的VC++上编码-> 调试
?提交题目
点击Submit可进入提交页面。
?查看系统返回的提交状况。
下面是两道例子：
1. poj1000（入门题）
A+B Problem
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 171686 Accepted: 92373
Description （问题描述）
Calculate a+b
Input （输入）
Two integer a,b (0<=a,b<=10)
Output （输出）
Output a+b
Sample Input （输入例子）
1 2
Sample Output （输出例子）
3
代码:(160K 0MS)：
#include
void main(){
int a,b;
scanf("%d %d", &a, &b);
printf("%d",(a+b));
}
2. poj1154（用到算法：搜索）
LETTERS
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 3393 Accepted: 1636
（英文略去，这里解释成中文）
题意：给出一个roe*col的大写字母矩阵，如：
HFDFFB
AJHGDH
DGAGEH
你一开始的位置为左上角（即’H’处），每一步你可以向上下左右四个方向移动一格，并且不能移向曾经经过的字母。请输出最多可以经过几个字母。
例子的解为6个，其中一条路径为HFJADG…
代码:(212K 32MS)
#include
using namespace std;
const int Max = 30;
int row, col, ans = 0;
char map[Max][Max];
bool vis[Max];
int dr[4] = {-1, 0, 0, 1};
int dc[4] = {0, -1, 1, 0};
bool inmap(int r, int c){
if(r >= 1 && r <= row && c >= 1 && c <= col)
return true;
return false;
}
void dfs(int dep, int now_r, int now_c){
if(dep > ans) ans = dep;
for(int i = 0; i < 4; i ++){
int r = now_r + dr[i];
int c = now_c + dc[i];
if(inmap(r, c) && !vis[map[r][c] - 'A']){
vis[map[r][c] - 'A'] = true;
dfs(dep + 1, r, c);
vis[map[r][c] - 'A'] = false;
}
}
}
int main(){
cin >> row >> col;
for(int i = 1; i <= row; i ++)
for(int j = 1; j <= col; j ++)
cin >> map[i][j];
memset(vis, false, sizeof(vis));
vis[map[1][1] - 'A'] = true;
dfs(1, 1, 1);
cout << ans << endl;
return 0;
}
写在最后：
学习计算机，编程是王道，如果你对编程或者ACM感兴趣，在poj上做了些题之后觉得有兴趣做下去；或者对ACM竞赛的存在某些疑问的话，可以联系我，或者加入我们的交流群：108350786 （09暨大ACM交流群），里面有暨大本部ACM队的师兄，其中悦海师兄是全国中学生信息竞赛一等奖，被保送到暨南大学的。有什么问题的话可在群内讨论，一起努力，谢谢…
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训练题集一
poj1035:拼写检查 时间限制： 2000毫秒内存限制： 65536K 提交总数： 11190 ： 4140 说明 作为一个新的拼写检查程序的开发团队成员，你写的模块，将检查使用一切形式的所有已知的正确的话字典的 话的正确性。如果这个词在字典中缺席那么它可以取代正确的话（从字典）可以取得下列操作之一： 从单词的一个字母删去 ;在任意一个字母的单词一个字母 取代，插入一个？任意字母到单词 ，你的任务是编写程序，会发现每一个给定的单词从字典中所有可能的替代。 输入 输入文件的第一部分包含从字典中的所有单词。每个字中占有它自己的行。完成这部分是由一个单独的行上的单字符'＃' 。所有的字是不同的。将有10000字的字典。 文件的下一部分，包含了所有的单词进行检查。每个字中占有它自己的行。这部分也完成了由一个单独的行上的单字符'＃' 。将有最多50个字进行检查。 输入文件中的所有单词（从字典和被检查的词字）只包括小字母字符，每一个包含15个字符最多。 输出 写入到输出文件中完全检查它们在输入文件的第二部分中出现的顺序每个字一行。如果这个词是正确的（即它在字典中存在）写留言：“是正确的“，如果这个词是不正确的，那么先写这两个字，然后写字符。”：“（冒号），并在一个单独的空间写了所有可能的替代品，用空格隔开这些替代应在书面的顺序。其在字典中（在输入文件的第一部分）。出现，如果有这个字没有替换，然后换行，应立即按照冒号。 样例输入 我是有我更多的比赛，我太iF奖＃我知道米的较量HAV OO或我的网络连接MRE＃
输出范例 我是正确的认识到：奖米：我的我的比赛是正确的甲肝：已经有OO：太：我是正确的FI：我MRE：更多的我 poj3080:蓝色牛仔裤 时间限制： 1000毫秒内存限制： 65536K 提交总数： 6173 接受日期： 2560 说明 基因地理工程是IBM与国家地理学会，是分析，从成千上万的贡献者地图地球是如何填充DNA的研究伙伴关系，作为IBM的研究人员，你一直负责编写一个程序，会发现共性之间个人调查资料，以确定新的遗传标记，可与相关的DNA 片段。DNA碱基序列是指出在它们在分子中发现的顺序列出的氮基地。有四种碱基：腺嘌呤（A），胸腺嘧啶（T），鸟嘌呤（G），胞嘧啶（C）。一个6碱基的DNA序列可以作为TAGACC代表。鉴于一组DNA碱基序列，确定在所有序列中出现的最长的系列基地。 输入 输入到这个问题，将开始与行包含一个单一的整数n表示数据集的数目。每个数据集由以下几部分组成组成： ?一个正整数m（2 <= M <= 10）的碱基序列，在此数据集。 ?m行每片含60个碱基组成的单一碱基序列。 输出 对于每一个输入数据集，输出基地序列的最长共同所有的碱基序列。如果最长的公共子序列的长度小于3基地，显示字符串“没有显着的共性”。如果存在多个子序列相同的长度最长，只输出序列的按字母顺序排列第一。
(2020年编辑)ACM必做50题的解题-数论
poj 1061 青蛙的约会 这题用的是解线性同余方程的方法，之前没接触到过，搜索资料后看到一个人的博客里面讲的很好就拷贝过来了。内容如下： 对于方程：ax≡b(mod m)，a，b，m都是整数，求解x 的值，这个就是线性同余方程。符号说明： mod表示：取模运算 ax≡b(mod m)表示：(ax - b) mod m = 0，即同余 gcd(a,b)表示：a和b的最大公约数 求解ax≡b(mod n)的原理：对于方程ax≡b(mod n)，存在ax + by = gcd(a,b)，x，y是整数。而ax≡b(mod n)的解可以由x，y来堆砌。具体做法如下： 第一个问题：求解gcd(a,b) 定理一：gcd(a,b) = gcd(b,a mod b) 欧几里德算法 int Euclid(int a,int b) { if(b == 0) return a; else return Euclid(b,mod(a,b)); } 附：取模运算 int mod(int a,int b) { if(a >= 0) return a % b; else return a % b + b; } 第二个问题：求解ax + by = gcd(a,b) 定理二：ax + by = gcd(a,b)= gcd(b,a mod b) = b * x' + (a mod b) * y' = b * x' + (a - a / b * b) * y' = a * y' + b * (x' - a / b * y') = a * x + b * y 则：x = y' y = x' - a / b * y' 以上内容转自https://www.wendangku.net/doc/cb14266875.html,/redcastle/blog/item/934b232dbc40d336349bf7e4.html
ACM必做50题——数学
1、POJ 2249 Binomial Showdown 组合数学。 高精度，也可把分子分母的数组进行两两约分 #include
有一个溢出问题；比如64位全是p的序列，那么max会溢出，值为-1；同理min在全是n 时也会溢出，为1；显然是max>=0,min<=1,溢出时产生异常，依次可以判断； ②是否是最大限和最小限之间的数都能表示呢？ 都可以，而且能够表示的数是2^k个，这个原始2进制是一样的；因为每个位上要么是0，要么是1，而且每个位上的权重唯一的，不能通过其他位的01组合获得；最后，我们就可以仿照原始二进制来算在类2进制下的表示；不断求N的二进制最后一位和右移；如果取余是1，则该位上一定是1，如果该位对于字母为‘n’，则高位应该再加1；这里对2取余可能会出错，因为对于负数，补码的表示，最后一位一定是和原码一样的每次的右移后(有时需先加1）补码表示正好符合要求（可找实例验证）； #include
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、最长递增子串、三角剖分、记忆化dp 6.博弈类算法。博弈树，二进制法等。 7.最大团，最大独立集。 8.判断点在多边形内。 9. 差分约束系统. 10. 双向广度搜索、A*算法，最小耗散优先. 第三阶段：
前两个阶段是打基础，第三阶段是锻炼在比赛中可以快速建立模型、想新算法 。这就要平时多做做综合的题型了。 1. 把oibh上的论文看看（大概几百篇的，我只看了一点点，呵呵）。 2. 平时扫扫zoj上的难题啦，别老做那些不用想的题.(中大acm的版主经常说我挑简单的来 做:-P ) 3. 多参加网上的比赛，感受一下比赛的气氛，评估自己的实力. 4. 一道题不要过了就算，问一下人，有更好的算法也打一下。 5. 做过的题要记好:-) （一） 不可能都完全记住那么多的算法. 常用算法,拿过来就可以写出来 不常用的,拿起书来,看10分钟,就能理解算法(因为以前记过). 对以前没有记过的算法,就不好说了,难的可能要研究好几天. 这样就可以了. 应该熟练掌握的常用的算法应该有: 各种排序算法（插入排序、冒泡排序、选择排序，快速排序，堆排序，归并排序） 线性表(一般的线性表,栈,队列)的插入和删除 二叉树的遍历（前序，中序，后序） 图的遍历（深度优先，广度优先） 二分法查找，排序二叉树，Hash查找（处理冲突的方法）。 （二） 分析一个东西,你可以用不同的眼光去看待,有很多时候,就跟自己生活一样,觉得小时候看待问题很幼稚,现在看问题全面了,而且方式不一样了,为什么,就是成长吧,就跟这个一样的,你对算法,比如写一个程序,可能直接写很简单,可是可以有一些有趣的方式,比如通过什么样来表达,怎么样更高效..等等吧 （三） 于大学里把基本的专业课学扎实就ok，如：数据结构，离散，操作系统等。碰到一些基本的数据结构和算法，如查找排序要根据原理马上能写出相应的代码就行了，我个人是这样理解的，对于更深层次的东西，也是建立在自己熟练的基础之上的吧 （四）
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、最长递增子串、三角剖分、记忆化dp 6.博弈类算法。博弈树，二进制法等。 7.最大团，最大独立集。 8.判断点在多边形内。 9. 差分约束系统. 10. 双向广度搜索、A*算法，最小耗散优先. 第三阶段： 前两个阶段是打基础，第三阶段是锻炼在比赛中可以快速建立模型、想新算法 。这就要平时多做做综合的题型了。 1. 把oibh上的论文看看（大概几百篇的，我只看了一点点，呵呵）。
ACM数论方面十道基础题目详解
1、公约数和公倍数 https://www.wendangku.net/doc/cb14266875.html,/JudgeOnline/problem.php?pid=40 这道题目是非常基础的题目，在学习了欧几里德算法之后，应该很好就能做的出来了。注意两个数的最小公倍数和最大公约数之间有关系为： a*b=gcd(a,b)*lcm(a,b); 代码如下： #include ?????≡≡≡)33(mod ) 28(mod )23(mod d n e n p n 那么找到k1、k2、k3满足： k1：k1%23==0&&k1%28==0&&k1%33==1 k2：k2%33==0&&k2%28==0&&k2%23==1 k3：k3%33==0&&k3%23==0&&k3%28==1 则n=k2*p+k3*e+k1*i+k*21252； 代码如下： #include 数论50题 1．由1，3，4，5，7，8这六个数字所组成的六位数中，能被11整除的最大的数是多少？ 【分析】各位数字和为1+3+4+5+7+8=28 所以偶数位和奇数位上数字和均为14 为了使得该数最大，首位必须是8，第2位是7，14-8=6 那么第3位一定是5，第5位为1 该数最大为875413。 2．请用1，2，5，7，8，9这六个数字（每个数字至多用一次）来组成一个五位数，使得它能被75整除，并求出这样的五位数有几个？ 【分析】75=3×25 若被3整除，则各位数字和是3的倍数，1+2+5+7+8+9=32 所以应该去掉一个被3除余2的，因此要么去掉2要么去掉8 先任给一个去掉8的，17925即满足要求 1）若去掉8 则末2位要么是25要么是75，前3位则任意排，有3！=6种排法 因此若去掉8则有2*6=12个满足要求的数 2）若去掉2 则末2位只能是75，前3位任意排，有6种排法 所以有6个满足要求 综上所述，满足要求的五位数有18个。 3．已知道六位数20□279是13的倍数，求□中的数字是几？ 【分析】根据被13整除的判别方法，用末三位减去前面的部分得到一个两位数，十位是7，个位是（9-□），它应该是13的倍数，因为13|78,所以9-□=8 □中的数字是1 4．某自然数，它可以表示成9个连续自然数的和，又可以表示成10个连续自然数的和，还可以表示成11个连续自然数的和，那么符合以上条件的最小自然数是？（2005全国小学数学奥赛） 【分析】可以表示成连续9个自然数的和说明该数能被9整除，可以表示成连续10个自然数的和说明该数能被5整除，可表示成连续11个自然数的和说明该数能被11整除 因此该数是[9,5,11]=495，因此符合条件的最小自然数是495。 5．一次考试中，某班同学有考了优秀，考了良好，考了及格，剩下的人不及格，已知该班同学的人数不超过50，求有多少人不及格？ 【分析】乍一看这应该是一个分数应用题，但实际上用到的却是数论的知识，由于人数必须是整数，所以该班同学的人数必须同时是2，3，7的倍数，也就是42的倍数，又因为人数不超过50，所以只能是42人，因此不及格的人数为（1---）×42=1人 6．（1）从1到3998这3998个自然数中，有多少个能被4整除？ （2）从1到3998这3998个自然数中，有多少个数的各位数字之和能被4整除？ （第14届迎春杯考题） 【分析】（1）3998/4=999….6所以1-3998中有996个能被4整除的 （2）考虑数字和，如果一个一个找规律我们会发现规律是不存在的 因此我们考虑分组的方法 我们补充2个数，0000和3999，此外所有的一位两位三位数都在前面加上0补足4位 然后对这4000个数做如下分组 ACM培训资料 目录 第一篇入门篇 (3) 第1章新手入门 (5) 1ACM国际大学生程序设计竞赛简介 (5) 2ACM竞赛需要的知识 (8) 3团队配合 (14) 4练习、练习、再练习 (15) 5对新手的一些建议 (16) 第2章C++语言介绍 (22) 1C++简介 (22) 2变量 (23) 3C++数据类型 (25) 4C++操作符 (30) 5数组 (35) 6字符数组 (38) 7字串操作函数 (41) 8过程控制 (45) 9C++中的函数 (54) 10函数规则 (59) 第3章STL简介 (61) 1泛型程序设计 (61) 2STL 的组成 (67) 第二篇算法篇 (102) 第1章基本算法 (103) 1算法初步 (103) 2分治算法 (115) 3搜索算法 (124) 4贪婪算法 (135) 第2章进阶算法 (165) 1数论基础 (165) 2图论算法 (180) 3计算几何基础 (222) 第三篇实践篇 (246) 第1章《多边形》 (247) 第2章《灌溉问题》 (255) 第3章《L GAME》 (263) 第4章《NUMBER》解题报告 (271) 第5章《J OBS》解题报告 (275) 第6章《包裹运送》 (283) 第7章《桶的摆放》 (290) 第一篇入门篇 练就坚实的基础，总有一天…… 我们可以草木皆兵！ 第1章新手入门 1ACM国际大学生程序设计竞赛简介 1.1背景与历史 1970年在美国TexasA&M大学举办了首次区域竞赛，从而拉开了国际大学生程序设计竞赛的序幕。1977年，该项竞赛被分为两个级别，即区域赛和总决赛，这便是现代ACM竞赛的开始。在亚洲、美国、欧洲、太平洋地区均设有区域赛点。1995至1996年，来自世界各地的一千多支高校的代表队参加了ACM区域竞赛。ACM 大学生程序设计竞赛由美国计算机协会（ACM）举办，旨在向全世界的大学生提供一个展示和锻炼其解决问题和运用计算机能力的机会，现已成为全世界范围内历史最悠久、规模最大的大学生程序设计竞赛。 1.2竞赛组织 竞赛在由各高等院校派出的3人一组的队伍间进行，分两个级别。参赛队应首先参加每 清华大学ACM集训队培训资料（内部使用） 一、C++基础 基本知识 所有的C++程序都是有函数组成的，函数又叫做子程序，且每个C++程序必须包含一个main函数，编译器（能够把源代码转换成目标代码的程序）把翻译后的目标代码和一些启动代码组合起来，生成可执行文件，main函数就是可执行文件的入口，所以，每个C++程序有且只有一个main函数。 下面我们看一个最简单C++程序。(程序1.1) 程序1.1 int main(){return 0;} 在这个程序中，如果缺少任何一个字符，编译器就无法将其翻译成机器代码。 此外，C++是对大小写敏感的，这就意味着，如果我将mian()函数拼为Main(),哪么，编译器在编译这段程序的时候就会出错。 编辑源文件 能够提共管理程序开发的所有步骤，包括编辑的程序成为集成开发环境（integrated development evironments, IDE）。在windows系统下，使用较为广泛的有Microsoft Visual C++、Dev-Cpp等，在UNIX系统下，有Vim、emacs、eclipes等。这些程序都能提供一个较好的开发平台，使我们能够方便的开发一个程序，接下我们所要了解的都是标准C++，所有源代码都在Dev-cpp下编写，能够编译通过。 如果我们修改程序1.1中的main()函数的名称，将其改为Main()，那么，IDE就会给出错误信息，比如“ [Linker error] undefined reference to `WinMain@16'”，因为编译器没有找到main函数。 接下来，我们来看一个经典的C++例子（程序1.2） 程序1.2 #include 断断续续的学习数论已经有一段时间了，学得也很杂，现在进行一些简单的回顾和总结。学过的东西不能忘啊。。。 1、本原勾股数： 概念：一个三元组(a,b,c)，其中a,b,c没有公因数而且满足：a^2+b^2=c^2 首先，这种本原勾股数的个数是无限的，而且构造的条件满足： a=s*t,b=(s^2-t^2)/2,c=(s^2+t^2)/2 其中s>t>=1是任意没有公因数的奇数！ 由以上概念就可以导出任意一个本原勾股数组。 2、素数计数（素数定理） 令π(x)为1到x中素数的个数 19世纪最高的数论成就就是以下这个玩意儿： lim(x->∞){π(x)/(x/ln(x))}=1 数论最高成就，最高成就！！！有木有！！！ 3、哥德巴赫猜想(1+1) 一个大偶数(>=4)必然可以拆分为两个素数的和，虽然目前还没有人能够从理论上进行证明，不过我根据科学家们利用计算机运算的结果，如果有一个偶数不能进行拆分，那么这个偶数至少是一个上百位的数！！ 所以在ACM的世界中（数据量往往只有2^63以下）哥德巴赫猜想是成立的！！所以拆分程序一定能够实现的 4、哥德巴赫猜想的推广 任意一个>=8的整数一定能够拆分为四个素数的和 证明： 先来说8=2+2+2+2，（四个最小素数的和）不能再找到比2小的素数了，所以当n小于8，就一定不可能拆分为四个素数的和！ 那么当n大于等于8，可以分情况讨论： （1）n&1==0(n为偶数)，那么n就一定可以拆分为两个偶数的和 那么根据哥德巴赫猜想，偶数可以拆分为两个素数的和，于是，n一定可以拆分为四个素数的和 （2）n&1==1(n为奇数)，n一定可以拆分为两个偶数+1 由于有一个素数又是偶数，2，那么奇数一定有如下拆分：2+3+素数+素数 得证。 ACM小组内部预定函数数学问题： 1.精度计算——大数阶乘 2.精度计算——乘法（大 数乘小数） 3.精度计算——乘法（大 数乘大数） 4.精度计算——加法 5.精度计算——减法 6.任意进制转换 7.最大公约数、最小公倍 数 8.组合序列 9.快速傅立叶变换（FFT）10.Ronberg算法计算积分11.行列式计算12.求排列组合数 字符串处理： 1.字符串替换 2.字符串查找 3.字符串截取 计算几何： 1.叉乘法求任意多边形面 积 2.求三角形面积 3.两矢量间角度 4.两点距离（2D、3D） 5.射向法判断点是否在多边形内部 6.判断点是否在线段上 7.判断两线段是否相交 8.判断线段与直线是否相 交 9.点到线段最短距离10.求两直线的交点11.判断一个封闭图形是 凹集还是凸集 12.Graham扫描法寻找凸 包 数论： 1.x的二进制长度 2.返回x的二进制表示中 从低到高的第i位 3.模取幂运算 4.求解模线性方程 5.求解模线性方程组(中 国余数定理) 6.筛法素数产生器 7.判断一个数是否素数图论： 1.Prim算法求最小生成树 2.Dijkstra算法求单源最 短路径 3.Bellman-ford算法求单 源最短路径 4.Floyd算法求每对节点 间最短路径 排序/查找： 1.快速排序 2.希尔排序 3.选择法排序 4.二分查找数据结构： 1.顺序队列 2.顺序栈 3.链表 4.链栈 5.二叉树 一、数学问题 1.精度计算——大数阶乘 语法：int result=factorial(int n); 参数： n： n 的阶乘 返回值：阶乘结果的位数 注意： 本程序直接输出n!的结果，需要返回结果请保留long a[] 需要 math.h 源程序： int factorial(int n) { long a[10000]; int i,j,l,c,m=0,w; a[0]=1; for(i=1;i<=n;i++) { c=0; for(j=0;j<=m;j++) { a[j]=a[j]*i+c; c=a[j]/10000; a[j]=a[j]%10000; } if(c>0) {m++;a[m]=c;} } w=m*4+log10(a[m])+1; printf("\n%ld",a[m]); for(i=m-1;i>=0;i--) printf("%4.4ld",a[i]); return w; } ACM入门之新手入门 1.ACM国际大学生程序设计竞赛简介 1)背景与历史 1970年在美国T exasA&M大学举办了首次区域竞赛，从而拉开了国际大学生程序设计竞赛的序幕。1977年，该项竞赛被分为两个级别：区域赛和总决赛，这便是现代ACM竞赛的开始。在亚洲、美国、欧洲、太平洋地区均设有区域赛点。1995至1996年，来自世界各地的一千多支s代表队参加了ACM区域竞赛。ACM大学生程序设计竞赛由美国计算机协会（ACM）举办，旨在向全世界的大学生提供一个展示和锻炼其解决问题和运用计算机能力的机会，现已成为全世界范围内历史最悠久、规模最大的大学生程序设计竞赛。 2)竞赛组织 竞赛在由各高等院校派出的3人一组的队伍间进行，分两个级别。参赛队应首先参加每年9月至11月在世界各地举行的“区域竞赛(Regional Contest)”。各区域竞赛得分最高的队伍自动进入第二年3月在美国举行的“总决赛(Final Contest)”，其它的高分队伍也有可能被邀请参加决赛。每个学校有一名教师主管队伍，称为“领队”(faculty advisor)，他负责选手的资格认定并指定或自己担任该队的教练(coach)。每支队伍最多由三名选手(contestant)组成，每个选手必须是正在主管学校攻读学位的学生。每支队伍最多允许有一名选手具有学士学位，已经参加两次决赛的选手不得再参加区域竞赛。 3)竞赛形式与评分办法 竞赛进行5个小时，一般有6~8道试题，由同队的三名选手使用同一台计算机协作完成。当解决了一道试题之后，将其提交给评委，由评委判断其是否正确。若提交的程序运行不正确，则该程序将被退回给参赛队，参赛队可以进行修改后再一次提交该问题。 程序运行不正确是指出现以下4种情况之一： (1)运行出错(run-time error)； (2)运行超时〔time-limit exceeded〕； (3)运行结果错误(wrong answer)； (4)运行结果输出格式错误(presentation error)。 竞赛结束后，参赛各队以解出问题的多少进行排名，若解出问题数相同，按照总用时的长短排名。总用时为每个解决了的问题所用时间之和。一个解决了的问题所用的时间是竞赛开始到提交被接受的时间加上该问题的罚时(每次提交通不过，罚时20分钟)。没有解决的问题不记时。美国英语为竞赛的工作语言。竞赛的所有书面材料(包括试题)将用美国英语写出，区域竞赛中可以使用其它语言。总决赛可以使用的程序设计语言包括PASCAL，C，C++及Java，也可以使用其它语言。具体的操作系统及语言版本各年有所不同。 4)竞赛奖励情况 总决赛前十名的队伍将得到高额奖学金：第一名奖金为12000美元，第二名奖金为 6000美元，第三名奖金为3000美元，第四名至第十名将各得到l500美元。除此之外还将承认北美冠军、欧洲冠军、南太平洋冠军及亚洲冠军。 2.ACM竞赛需要的知识 语言是最重要的基本功 无论侧重于什么方面，只要是通过计算机程序去最终实现的竞赛，语言都是大家要过的第一道关。亚洲赛区的比赛支持的语言包括C/C++与JAVA。首先说说JAVA，众所周知，作为面向对象的王牌语言，JAVA在大型工程的组织与安全性方面有着自己独特的优势，但是对于信息学比赛的具体场合，JAVA则显得不那么合适，它对于输入输出流的操作相比于C++要繁杂很多，更为重要的是JAVA程序的运行速度要比C++慢10倍以上，而竞赛中对于JAVA程序的运行时限却往往得不到同等比例的放宽，这无疑对算法设计提出了更高的要求，是相当 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 -北大poj acm题目推荐50题 POJ == 北京大学ACM在线评测系统https://www.wendangku.net/doc/cb14266875.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/cb14266875.html,。 对于每个题目只要求一个POJxxxx.cpp 或POJxxxx.java (xxxx表示POJ该题题号) 的文件，注意不要加入整个project 。 11. 如果有同学很早做完了要求的题目，请尽快和我们联系，我们将指导下一步的训练。 下面是一个解题报告的范例： 例如：POJ1000.cpp 目录 数A01 敲七 (1) 数A02 三角形面积 (2) 数A03 3n+1数链问题 (3) 数A04 统计同成绩学生人数 (4) 数A05 分解素因子 (5) 数A06 亲和数 (6) 数B01 寒冰王座 (7) 数B02 整数对 (8) 数B03 麦森数 (9) 数B04 Feli的生日礼物 (10) 注：数表示本题属于初等数论，A表示简单，B表示稍难。 数A01 敲七 【问题描述】 输出7和7的倍数，还有包含7的数字例如（17，27，37...70，71，72，73...）【数据输入】一个整数N。(N不大于30000) 【数据输出】从小到大排列的不大于N的与7有关的数字，每行一个。 【样例输入】 20 【样例输出】 7 14 17 数A02 三角形面积 【问题描述】 给出三角形的三个边长为a，b，c，根据海伦公式来计算三角形的面积： s = (a+b+c)/2； area = sqrt(s*(s-a)*(s-b)*(s-c)); 【数据输入】测试的数据有任意多组，每一组为一行。 每一行为三角形的三个边长为a，b，c； 【数据输出】输出每一个三角形的面积，两位小数。如果不是一个三角形，则输出错误提示信息：“Input error!” 【样例输入】 3 4 5 6 8 10 1 2 3 【样例输出】 6.00 24.00 Input error! 数A03 3n+1数链问题 【问题描述】 在计算机科学上，有很多类问题是无法解决的，我们称之为不可解决问题。然而，在很多情况我们并不知道哪一类问题可以解决，那一类问题不可解决。现在我们就有这样一个问题，问题如下： 1. 输入一个正整数n； 2. 把n显示出来； 3. 如果n=1则结束； 4. 如果n是奇数则n变为3n+1 ，否则n变为n/2； 5. 转入第2步。 例如对于输入的正整数22，应该有如下数列被显示出来： 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 我们推测：对于任意一个正整数，经过以上算法最终会推到1。尽管这个算法很简单，但我们仍然无法确定我们的推断是否正确。不过好在我们有计算机，我们验证了对于小于1,000,000的正整数都满足以上推断。对于给定的正整数n，我们把显示出来的数的个数定义为n的链长，例如22的链长为16。 你的任务是编写一个程序，对于任意一对正整数i和j，给出i、j之间的最长链长，当然这个最长链长是由i、j之间的其中一个正整数产生的。我们这里的i、j之间即包括i也包括j。 【数据输入】输入文件只有一行，即为正整数i和j，i和j之间以空格隔开。0 < i ≤j < 10,000。 【数据输出】文件只能有一行，即为i、j之间的最长链长。 【样例输入】 1 10 【样例输出】 20 实用标准文案 ACM培训大纲 基础内容： 数据结构——》搜索 ——》图论 DP 数论 博弈 中级内容 数据结构 网络流 第一章搜索 1.二分搜索 三分搜索2. 栈 3. 队列 4. 深搜 5.广搜 6. 第二章数据结构 1.优先队列 并查集 2.二叉搜索树3. 线段树（单点更新） 4. Trie 5. 精彩文档． 实用标准文案 第三章图论 1.图的表示 1.1二维数组 1.2邻接表 1.3前向星 2.图的遍历 2.1双连通分量 2.2拓扑排序 3.最短路 3.1迪杰斯特拉 3.2弗洛伊德 3.3SPFA 4.匹配匈牙利算法 5.生成树 6.网络流简介 第四章动态规划 1.状态转移方程 2.引入 2.10-1背包 2.2硬币问题 2.3矩阵链乘 3.区间DP 4.按位DP 5.树形DP 6.状压DP 第五章数论 1.欧几里得 扩展欧几里得 2.因数分解3.费马小定理 4.欧拉定理 5.素数6. 6.1筛法 6.2素数判定 6.2.1O(√n)方法 精彩文档． 实用标准文案 6.2.2Miller-rabin测试 第六章博弈 1.Nim和 2.SG函数 第七章中级数据结构 1.树状数组 RMQ 2. KMP 3. AC自动机4. 线段树（区间更新）5. 第八章图论进阶 1.网络流问题 精彩文档． 实用标准文案 综述 在很多人眼里，东北大学秦皇岛分校不算是985高校。所以我们要用自己的能力证明我们有985的实力。ACM是计算机界认可度最高的一个比赛，可以说只要区域赛有过奖牌，国内任何IT公司没有理由不要。同时，在高校之中，对一个大学计算机专业的评价，大部分人也会首先看ACM 的水平。将ACM打出学校，在国内打出一定成绩，对扩大我校影响力很有帮助。 考虑到本校暂时没有进行专题训练的出题能力，专题训练的题目主要从UESTC 2014年集训队专题训练中获取，再加上从别的OJ上找一些题目。训练的平台设置在华中科技大学的vertual judge上面。本人将在毕业之前承担培训任务。在2015学年开始之前，培训计划为每两周一次，中间空闲的时间由大二或者大一熟悉C++的同学给不熟悉C++的同学进行基础的讲解。寒假时间计划每周一次。2015学年开始之后，考虑到本人要进行考研备考，培训的频率定为一个月一次，根据实际情况增加课程，所以将在寒假结束之前尽量完成多的培训任务。培训的目标是在2015年区域赛中能够获得出线的资格，并且在2016年邀请赛中能够有队伍能够拿到银牌的水平。 根据各大高校的培训资料及总校给的资料汇总，将ACM的内容分成以下几章。每章的开始根据本人的认知经验，分成必考题和常考题两类。必考题为每场必出题型，大部分水题在必考题范围之内。想取得成绩必考题必须作对。常考题型有时候会最为水题，有时候会作为拉分题。 培训分为基础部分和中级部分，本人实力有限，没有能力进行高级部分的讲解。高级部分留给学弟学妹们继续努力^_^。 第一章搜索 二分和三分是很基础的一种技术。参考外校的培训教材，没有把二分和三分放入搜索一章。但是实在不知道应该放到哪里去，就在这里讲。反正都是搜索。 二分最基本的应用是求单调函数跟x轴交点的问题使用的方法，有些算法也会使用二分搜索2）算法优化为O（nlogn）O来降低复杂度。一个应用是在最长递增子序列中将DP的（?? 三分的应用是求抛物线等在一定区间内有唯一极值的问题中，求极值的方法。 栈和队列本属于数据结构的内容，考虑到这两种数据结构在搜索中应用较多，将其放入搜索一章。栈是一种先入先出的数据结构。可以用一个数组来保存栈中元素，用一个指针指向栈顶，就实现了一个栈，也可以用STL中提供的栈。 队列是一种先入后出的数据结构。可以用一个数组来保存队列的元素，一个指针指向队列头，一个指针指向队列尾，每次入队列队尾向后一个，出队列队首向后一个。STL也提供了队列。 递归转换是一个很常见的优化措施。有些题目可能会卡着让递归形式的算法超时，这个时候就必数论50题
ACM培训资料
清华大学ACM集训队培训资料内部使用
数论
清华内部ACM培训资料-各类经典算法
ACM入门之新手入门
ACM部分练习题目答案
北大 poj acm题目推荐50题
step1-数论 程序设计基础题ACM
ACM培训大纲