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;
}
2.精度计算——乘法（大数乘小数）
语法：mult(char c[],char t[],int m);
参数：
c[]：被乘数，用字符串表示，位数不限
t[]：结果，用字符串表示
m：乘数，限定10以内
返回
null
值：
注意：
需要 string.h
源程
序：
void mult(char c[],char t[],int m)
{
int i,l,k,flag,add=0;
char s[100];
l=strlen(c);
for (i=0;i s[l-i-1]=c[i]-'0'; for (i=0;i { k=s[i]*m+add; if (k>=10) {s[i]=k%10;add=k/10;flag=1;} else {s[i]=k;flag=0;add=0;} } if (flag) {l=i+1;s[i]=add;} else l=i; for (i=0;i t[l-1-i]=s[i]+'0'; t[l]='\0'; } 3.精度计算——乘法（大数乘大数） 语法：mult(char a[],char b[],char s[]); 参数： a[]：被乘数，用字符串表示，位数不限 b[]：乘数，用字符串表示，位数不限 t[]：结果，用字符串表示 返回 null 值： 注意： 空间复杂度为 o(n^2) 需要 string.h 源程 序： void mult(char a[],char b[],char s[]) { int i,j,k=0,alen,blen,sum=0,res[65][65]={0},flag=0; char result[65]; alen=strlen(a);blen=strlen(b); for (i=0;i for (j=0;j res[i][j]=(a[i]-'0')*(b[j]-'0'); for (i=alen-1;i>=0;i--) for (j=blen-1;j>=0;j--) sum=sum+res[i+blen-j-1][j]; result[k]=sum%10; k=k+1; sum=sum/10; } for (i=blen-2;i>=0;i--) { for (j=0;j<=i;j++) sum=sum+res[i-j][j]; result[k]=sum%10; k=k+1; sum=sum/10; } if (sum!=0) {result[k]=sum;k=k+1;} for (i=0;i for (i=k-1;i>=0;i--) s[i]=result[k-1-i]; s[k]='\0'; while(1) if (strlen(s)!=strlen(a)&&s[0]=='0') strcpy(s,s+1); else break; } } 4.精度计算——加法 语法：add(char a[],char b[],char s[]); 参数： a[]：被乘数，用字符串表示，位数不限 b[]：乘数，用字符串表示，位数不限 t[]：结果，用字符串表示 返回 null 值： 注意： 空间复杂度为 o(n^2) 需要 string.h 源程 序： void add(char a[],char b[],char back[]) { int i,j,k,up,x,y,z,l; char *c; if (strlen(a)>strlen(b)) l=strlen(a)+2; else l=strlen(b)+2; c=(char *) malloc(l*sizeof(char)); i=strlen(a)-1; j=strlen(b)-1; k=0;up=0; while(i>=0||j>=0) { if(i<0) x='0'; else x=a[i]; if(j<0) y='0'; else y=b[j]; z=x-'0'+y-'0'; if(up) z+=1; if(z>9) {up=1;z%=10;} else up=0; c[k++]=z+'0'; i--;j--; } if(up) c[k++]='1'; i=0; c[k]='\0'; for(k-=1;k>=0;k--) back[i++]=c[k]; back[i]='\0'; } 5.精度计算——减法 语法：sub(char s1[],char s2[],char t[]); 参数： s1[]：被减数，用字符串表示，位数不限 s2[]：减数，用字符串表示，位数不限 t[]：结果，用字符串表示 返回 null 值： 注意： 默认s1>=s2，程序未处理负数情况 需要 string.h 源程 序： void sub(char s1[],char s2[],char t[]) { int i,l2,l1,k; l2=strlen(s2);l1=strlen(s1); t[l1]='\0';l1--; for (i=l2-1;i>=0;i--,l1--) { if (s1[l1]-s2[i]>=0) t[l1]=s1[l1]-s2[i]+'0'; else { t[l1]=10+s1[l1]-s2[i]+'0'; s1[l1-1]=s1[l1-1]-1; } } k=l1; while(s1[k]<0) {s1[k]+=10;s1[k-1]-=1;k--;} while(l1>=0) {t[l1]=s1[l1];l1--;} loop: if (t[0]=='0') { l1=strlen(s1); for (i=0;i t[l1-1]='\0'; goto loop; } if (strlen(t)==0) {t[0]='0';t[1]='\0';} } 6.任意进制转换 语法：conversion(char s1[],char s2[],long d1,long d2); 参数： s[]：原进制数字，用字符串表示 s2[]：转换结果，用字符串表示 d1：原进制数 d2：需要转换到的进制数 返回 null 值： 注意： 高于9的位数用大写'A'～'Z'表示，2～16位进 制通过验证 源程 序： void conversion(char s[],char s2[],long d1,long d2) { long i,j,t,num; char c; num=0; for (i=0;s[i]!='\0';i++) { if (s[i]<='9'&&s[i]>='0') t=s[i]-'0'; else t=s[i]-'A'+10; num=num*d1+t; } i=0; while(1) { t=num%d2; if (t<=9) s2[i]=t+'0'; else s2[i]=t+'A'-10; num/=d2; if (num==0) break; i++; } for (j=0;j {c=s2[j];s2[j]=s[i-j];s2[i-j]=c;} s2[i+1]='\0'; } 7.最大公约数、最小公倍数 语法：resulet=hcf(int a,int b)、result=lcd(int a,int b) 参数： a：int a，求最大公约数或最小公倍数 b：int b，求最大公约数或最小公倍数 返回 返回最大公约数（hcf）或最小公倍数（lcd）值： 注意： lcd 需要连同 hcf 使用源程 序： int hcf(int a,int b) { int r=0; while(b!=0) { r=a%b; a=b; b=r; } return(a); } lcd(int u,int v,int h) { return(u*v/h); } 8.组合序列 语法：m_of_n(int m, int n1, int m1, int* a, int head) 参数： m：组合数C的上参数 n1：组合数C的下参数 m1：组合数C的上参数，递归之用 *a：1～n的整数序列数组 head：头指针 返回 null 值： 注意： *a需要自行产生 初始调用时，m=m1、head=0 调用例子：求C(m,n)序列：m_of_n(m,n,m,a,0); 源程 序： void m_of_n(int m, int n1, int m1, int* a, int head) { int i,t; if(m1<0 || m1>n1) return; if(m1==n1) { for(i=0;i cout<<'\n'; return; } m_of_n(m,n1-1,m1,a,head); // 递归调用 t=a[head];a[head]=a[n1-1+head];a[n1-1+head]=t; m_of_n(m,n1-1,m1-1,a,head+1); // 再次递归调用 t=a[head];a[head]=a[n1-1+head];a[n1-1+head]=t; } 9.快速傅立叶变换（FFT） 语法：kkfft(double pr[],double pi[],int n,int k,double fr[],double fi[],int l,int il); 参数： pr[n]：输入的实部 pi[n]：数入的虚部 n，k：满足n=2^k fr[n]：输出的实部 fi[n]：输出的虚部 l：逻辑开关，0 FFT，1 ifFT il：逻辑开关，0 输出按实部/虚部；1 输出按模/幅角返回 null 值： 注意： 需要 math.h 源程 序： void kkfft(pr,pi,n,k,fr,fi,l,il) int n,k,l,il; double pr[],pi[],fr[],fi[]; { int it,m,is,i,j,nv,l0; double p,q,s,vr,vi,poddr,poddi; for (it=0; it<=n-1; it++) { m=it; is=0; for (i=0; i<=k-1; i++) {j=m/2; is=2*is+(m-2*j); m=j;} fr[it]=pr[is]; fi[it]=pi[is]; } pr[0]=1.0; pi[0]=0.0; p=6.283185306/(1.0*n); pr[1]=cos(p); pi[1]=-sin(p); if (l!=0) pi[1]=-pi[1]; for (i=2; i<=n-1; i++) { p=pr[i-1]*pr[1]; q=pi[i-1]*pi[1]; s=(pr[i-1]+pi[i-1])*(pr[1]+pi[1]); pr[i]=p-q; pi[i]=s-p-q; } for (it=0; it<=n-2; it=it+2) { vr=fr[it]; vi=fi[it]; fr[it]=vr+fr[it+1]; fi[it]=vi+fi[it+1]; fr[it+1]=vr-fr[it+1]; fi[it+1]=vi-fi[it+1]; } m=n/2; nv=2; for (l0=k-2; l0>=0; l0--) { m=m/2; nv=2*nv; 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基地，显示字符串“没有显着的共性”。如果存在多个子序列相同的长度最长，只输出序列的按字母顺序排列第一。 转载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练习建议 一位高手对我的建议： 一般要做到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培训资料 目录 第一篇入门篇 (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 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培训大纲 基础内容： 数据结构——》搜索 ——》图论 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也提供了队列。 递归转换是一个很常见的优化措施。有些题目可能会卡着让递归形式的算法超时，这个时候就必 大学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 `WinMain16'”，因为编译器没有找到main函数。 接下来，我们来看一个经典的C++例子（程序1.2） 程序1.2 #include 杭电ACM 1003： 这个问题就是最大字段和的问题，这个问题用以前老是讲过的分治的方法求解，我用了分治，认为感觉还是正确，但是提交超时，他的数列最大是100000个数，不知道是否会有其他的方法，或者是我的程序有问题 ACM做题过程中的一些小技巧。 1.一般用C语言节约空间，要用C++库函数或STL时才用C++; cout、cin和printf、scanf最好不要混用。 2.有时候int型不够用，可以用long long或__int64型(两个下划线__)。 值类型表示值介于-2^63 ( -9,223,372,036,854,775,808) 到2^63-1(+9,223,372,036,854,775,807 )之间的整数。 printf("%I64d",a); printf("%lld",a); 3.OJ判断是只看输出结果的。 所以大部分题处理一组数据后可以直接输出，就不需要用数组保存每一个Case的数据。while(case--) {scanf(...); ...... printf(...); } 4.纯字符串用puts()输出。 数据大时最好用scanf()、printf()减少时间。 先用scanf()，再用gets()会读入回车。 scanf("%c%c",&c1,&c2)会读入空格； 5. 读到文件的结尾，程序自动结束 while( ( scanf(“%d”,&a) ) != -1 ) while( ( scanf(“%d”,&a) ) != EOF) while( ( scanf(“%d”,&a) ) == 1 ) while( ~( scanf(“%d”,&a) ) ) 读到一个0时，程序结束 while( scanf(“%d”,&a) ,a) 读到多个0时，程序结束 while( scanf(“%d%d%d”,&a,&b,&c),a+b+c ) 6.数组定义int a[10]={0};可以对其全部元素赋值为0； 全局变量，静态变量自动初始化为0； 7.有很多数学题是有规律的，直接推公式或用递归、循环。 8.圆周率=cos(-1.0) 自然对数=exp(1.0) 9.如果要乘或除2^n,用位移运算速度快。a>>n;a< Zhejiang University ICPC Team Routine Library by WishingBone(Dec.2002) Last Update(Nov.2004)by Riveria 1、几何25 1.1注意 (25) 1.2几何公式 (25) 1.3多边形 (27) 1.4多边形切割 (30) 1.5浮点函数 (31) 1.6面积 (36) 1.7球面 (37) 1.8三角形 (38) 1.9三维几何 (40) 1.10凸包 (47) 1.11网格 (49) 1.12圆 (49) 1.13整数函数 (51) 2、组合54 2.1组合公式 (54) 2.2排列组合生成 (54) 2.3生成gray码 (56) 2.4置换(polya) (56) 2.5字典序全排列 (57) 2.6字典序组合 (57) 3、结构58 3.1并查集 (58) 3.2堆 (59) 3.3线段树 (60) 3.4子段和 (65) 3.5子阵和 (65) 4、数论66 4.1阶乘最后非0位 (66) 4.2模线性方程组 (67) 4.3素数 (68) 4.4欧拉函数 (69) 5、数值计算70 5.1定积分计算(Romberg) (70) 5.2多项式求根(牛顿法) (72) 5.3周期性方程(追赶法) (73) 6、图论—NP搜索74 6.1最大团 (74) 6.2最大团(n<64)(faster) (75) 7、图论—连通性77 7.1无向图关键点(dfs邻接阵) (77) 7.2无向图关键边(dfs邻接阵) (78) 7.3无向图的块(bfs邻接阵) (79) 7.4无向图连通分支(dfs/bfs邻接阵) (80) ACM培训大纲基础内容： 数据结构——》搜索 ——》图论 DP 数论 博弈 中级内容 数据结构 网络流 第一章搜索 1.二分搜索 2.三分搜索 3.栈 4.队列 5.深搜 6.广搜 第二章数据结构 1.优先队列 2.并查集 3.二叉搜索树 4.线段树（单点更新） 5.Trie 第三章图论 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.树状数组 2.RMQ 3.KMP 4.AC自动机 5.线段树（区间更新） 第八章图论进阶 1.网络流问题 综述 在很多人眼里，东北大学秦皇岛分校不算是985高校。所以我们要用自己的能力证明我们有985的实力。ACM是计算机界认可度最高的一个比赛，可以说只要区域赛有过奖牌，国内任何IT公司没有理由不要。同时，在高校之中，对一个大学计算机专业的评价，大部分人也会首先看ACM的水平。将ACM打出学校，在国内打出一定成绩，对扩大我校影响力很有帮助。考虑到本校暂时没有进行专题训练的出题能力，专题训练的题目主要从UESTC 2014年集训队专题训练中获取，再加上从别的OJ上找一些题目。训练的平台设置在华中科技大学的vertual judge上面。本人将在毕业之前承担培训任务。在2015学年开始之前，培训计划为每两周一次，中间空闲的时间由大二或者大一熟悉C++的同学给不熟悉C++的同学进行基础的讲解。寒假时间计划每周一次。2015学年开始之后，考虑到本人要进行考研备考，培训的频率定为一个月一次，根据实际情况增加课程，所以将在寒假结束之前尽量完成多的培训任务。培训的目标是在2015年区域赛中能够获得出线的资格，并且在2016年邀请赛中能够有队伍能够拿到银牌的水平。 根据各大高校的培训资料及总校给的资料汇总，将ACM的内容分成以下几章。每章的开始根据本人的认知经验，分成必考题和常考题两类。必考题为每场必出题型，大部分水题在必考题范围之内。想取得成绩必考题必须作对。常考题型有时候会最为水题，有时候会作为拉分题。 培训分为基础部分和中级部分，本人实力有限，没有能力进行高级部分的讲解。高级部分留给学弟学妹们继续努力^_^。 第一章搜索 二分和三分是很基础的一种技术。参考外校的培训教材，没有把二分和三分放入搜索一章。但是实在不知道应该放到哪里去，就在这里讲。反正都是搜索。 二分最基本的应用是求单调函数跟x轴交点的问题使用的方法，有些算法也会使用二分搜索来降低复杂度。一个应用是在最长递增子序列中将DP的O（n2）算法优化为O（nlogn） 三分的应用是求抛物线等在一定区间内有唯一极值的问题中，求极值的方法。 栈和队列本属于数据结构的内容，考虑到这两种数据结构在搜索中应用较多，将其放入搜索一章。 栈是一种先入先出的数据结构。可以用一个数组来保存栈中元素，用一个指针指向栈顶，就实现了一个栈，也可以用STL中提供的栈。 队列是一种先入后出的数据结构。可以用一个数组来保存队列的元素，一个指针指向队列头，一个指针指向队列尾，每次入队列队尾向后一个，出队列队首向后一个。STL也提供了队列。递归转换是一个很常见的优化措施。有些题目可能会卡着让递归形式的算法超时，这个时候就必须改成非递归形式。非递归形式使用栈来实现。典型的例子就是二叉树的后续遍历可以改成非递归形式。 深度优先搜索与广度优先搜索是两种最基本的搜索方式。很多启发式的搜索建立在这两种方式之上。本章只设计深度优先及广度优先。 本章必须掌握的知识有栈和队列的定义，二叉树遍历的递归与非递归形式，深度优先搜索， Time will pierce the surface or youth, will be on the beauty of the ditch dug a shallow groove ; Jane will eat rare!A born beauty, anything to escape his sickle sweep .-- Shakespeare 清华大学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 `WinMain16'”，因为编译器没有找到main函数。 接下来，我们来看一个经典的C++例子（程序1.2） 程序1.2 #include 上海大学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 t o `WinMain@16'”，因为编译器没有找到main函数。 接下来，我们来看一个经典的C++例子（程序1.2） 程序1.2 #include 健行学院ACM协会培训资料 健行学院ACM协会 06年10月 第一章新手入门 1.ACM国际大学生程序设计竞赛简介 1) 背景与历史 1970年在美国TexasA&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道试题，由同队的三名选手使用同一台计算机协作完成。当解决了一道试题之后，将其提交给评委，由评委判断其是否正确。若提交的程序运行不正确，则该程序将被退回给参赛队，参赛队可以进行修改后再一次提交该问题。ACM训练题集一
ACM培训计划
ACM训练指南
ACM培训资料
清华大学ACM集训队培训资料内部使用
清华内部ACM培训资料-各类经典算法
ACM培训大纲
上海大学ACM集训队培训资料全
ACM训练总结
浙江大学ACM编程培训
ACM培训大纲
Dqsscha清华大学ACM集训队企业培训资料全
上海大学ACM集训队培训资料
ACM协会培训资料
相关主题
文本预览