备战ACM资料一:知识点数据结构:1,单,双链表及循环链表2,树的表示与存储,二叉树(概念,遍历)二叉树的应用(二叉排序树,判定树,博弈树,解答树等)3,文件操作(从文本文件中读入数据并输出到文本文件中)4,图(基本概念,存储结构,图的运算)数学知识1,离散数学知识的应用(如排列组合、简单的图论,数理逻辑)2,数论知识3,线性代数4,组合代数5,计算几何二算法1,排序算法(冒抛法,插入排序,合并排序,快速排序,堆排序)2,查找(顺序查找,二分发)3,回溯算法4,递归算法5,分治算法6,模拟法7,贪心法8,简单搜索算法(深度优先,广度优先),搜索中的剪枝,A*算法9,动态规划的思想及基本算法10,高精度运算三、ACM竞赛的题型分析竞赛的程序设计一般只有16种类型,它们分别是:DynamicProgramming(动态规划)Greedy(贪心算法)CompleteSearch(穷举搜索)FloodFill(不知该如何翻译)ShortestPath(最短路径)RecursiveSearchTechniques(回溯搜索技术)MinimumSpanningTree(最小生成树)Knapsack(背包问题)ComputationalGeometry(计算几何学)NetworkFlow(网络流)EulerianPath(欧拉回路)Two-DimensionalConvexHull(不知如何翻译)BigNums(大数问题)HeuristicSearch(启发式搜索)ApproximateSearch(近似搜索)AdHocProblems(杂题)四ACM竞赛参考书《实用算法的分析与程序设计》(吴文虎,王建德著,电子工业出版社,竞赛类的黑宝书)《青少年国际和全国信息学(计算机)奥林匹克竞赛指导)――组合数学的算法和程序设计》(吴文虎,王建德著,清华大学出版社,参加竞赛组合数学必学)《计算机算法设计与分析》(王晓东编著,最好的数据结构教材)《数据结构与算法》(傅清祥,王晓东编著,我所见过的最好的算法教材)《信息学奥林匹克竞赛指导――1997-1998竞赛试题解析》(吴文虎,王建德著,清华大学出版社)《计算机程序设计技巧》D.E.Kruth著,算法书中最著名的《葵花宝典》,大师的作品,难度大)《计算几何》周陪德著《ACM国际大学生程序设计竞赛试题与解析(一)》(吴文虎著,清华大学出版社)《数学建模竞赛培训教材》共三本叶其孝主编《数学模型》第二版姜启源《随机规划》《模糊数学》《数学建模入门》徐全智《计算机算法设计与分析》国防科大五常见的几个网上题库常用网站:1)信息学初学者之家:(2)大榕树编程世界:~drs/program/default.asp(3)中国教育曙光网:(4)福建信息学奥林匹克:(5)第20届全国青少年信息学奥林匹克竞赛:(6)第15届国际青少年信息学奥林匹克竞赛:(7)全美计算机奥林匹克竞赛:(8)美国信息学奥林匹克竞赛官方网站:(9)俄罗斯Ural州立大学:(10)西班牙Valladolid大学:(11)ACM-ICPC:(12)北京大学:(13)浙江大学:(14)IOI:(15)2003年江苏省信息学奥林匹克竞赛夏令营:(16)(17)(18)(19)(20)五如何备战ACM/ICPC1,个人准备(算法书,习题集,网上做题和讨论)2,1000题=亚洲冠军=世界决赛3,做好资料收集和整理工作实验一:递归与分治1.二分查找2.合并排序3.快速排序实验二:回溯1.0-1背包问题2.装载问题3.堡垒问题(ZOJ1002)4.*翻硬币问题5.8皇后问题6.素数环问题7.迷宫问题8.*农场灌溉问题(ZOJ2412)9.*求图像的周长(ZOJ1047)10.*骨牌矩阵11.*字母转换(ZOJ1003)12.*踩气球(ZOJ1004)实验三:搜索1.Floodfill2.电子老鼠闯迷宫3.跳马4.独轮车5.皇宫小偷6.分酒问题7.*找倍数8.*8数码难题实验四:动态规划1.最长公共子序列2.计算矩阵连乘积3.凸多边形的最优三角剖分4.防卫导弹5.*石子合并6.*最小代价子母树7.*旅游预算8.*皇宫看守9.*游戏室问题10.*基因问题11.*田忌赛马实验五:贪心与随机算法1.背包问题2.搬桌子问题3.*照亮的山景4.*用随即算法求解8皇后问题5.素数测试实验一:递归与分治实验目的理解递归算法的思想和递归程序的执行过程,并能熟练编写递归程序。掌握分治算法的思想,对给定的问题能设计出分治算法予以解决。实验预习内容编程实现讲过的例题:二分搜索、合并排序、快速排序。对本实验中的问题,设计出算法并编程实现。试验内容和步骤1.二分查找在对线性表的操作中,经常需要查找某一个元素在线性表中的位置。此问题的输入是待查元素x和线性表L,输出为x在L中的位置或者x不在L中的信息。程序略2.合并排序程序略3.快速排序程序略实验总结及思考合并排序的递归程序执行的过程实验二:回溯算法实验目的:熟练掌握回溯算法实验内容:回溯算法的几种形式a)用回溯算法搜索子集树的一般模式voidsearch(intm){if(mn)//递归结束条件output();//相应的处理(输出结果)else{a[m]=0;//设置状态:0表示不要该物品search(m+1);//递归搜索:继续确定下一个物品a[m]=1;//设置状态:1表示要该物品search(m+1);//递归搜索:继续确定下一个物品}}b)用回溯算法搜索子集树的一般模式voidsearch(intm){if(mn)//递归结束条件output();//相应的处理(输出结果)elsefor(i=m;i=n;i++){swap(m,i);//交换a[m]和a[i]if()if(canplace(m))//如果m处可放置search(m+1);//搜索下一层swpa(m,i);//交换a[m]和a[i](换回来)}}习题1.0-1背包问题在0/1背包问题中,需对容量为c的背包进行装载。从n个物品中选取装入背包的物品,每件物品i的重量为wi,价值为pi。对于可行的背包装载,背包中物品的总重量不能超过背包的容量,最佳装载是指所装入的物品价值最高。程序如下:#includestdio.hvoidreaddata();voidsearch(int);voidcheckmax();voidprintresult();intc=35,n=10;//c:背包容量;n:物品数intw[10],v[10];//w[i]、v[i]:第i件物品的重量和价值inta[10],max;//a数组存放当前解各物品选取情况;max:记录最大价值//a[i]=0表示不选第i件物品,a[i]=1表示选第i件物品intmain(){readdata();//读入数据search(0);//递归搜索printresult();}voidsearch(intm){if(m=n)checkmax();//检查当前解是否是可行解,若是则把它的价值与max比较else{a[m]=0;//不选第m件物品search(m+1);//递归搜索下一件物品a[m]=1;//不选第m件物品search(m+1);//递归搜索下一件物品}}voidcheckmax(){inti,weight=0,value=0;for(i=0;in;i++){if(a[i]==1)//如果选取了该物品{weight=weight+w[i];//累加重量value=value+v[i];//累加价值}}if(weight=c)//若为可行解if(valuemax)//且价值大于maxmax=value;//替换max}voidreaddata(){inti;for(i=0;in;i++)scanf(%d%d,&w[i],&v[i]);//读入第i件物品重量和价值}voidprintresult(){printf(%d,max);}2.装载问题有两艘船,载重量分别是c1、c2,n个集装箱,重量是wi(i=1…n),且所有集装箱的总重量不超过c1+c2。确定是否有可能将所有集装箱全部装入两艘船。提示:求出不超过c1的最大值max,若总重量-maxc2则能装入到两艘船。3.堡垒问题(ZOJ1002)如图城堡是一个4×4的方格,为了保卫城堡,现需要在某些格子里修建一些堡垒。城堡中的某些格子是墙,其余格子都是空格,堡垒只能建在空格里,每个堡垒都可以向上下左右四个方向射击,如果两个堡垒在同一行或同一列,且中间没有墙相隔,则两个堡垒都会把对方打掉。问对于给定的一种状态,最多能够修建几个堡垒。程序主要部分如下:intmain(){readdata();//读入数据search(0);//递归搜索printresult();}voidsearch(intm){introw,col;row=m/n;//求第m个格子的行号col=m%n;//求第m个格子的列号if(m=n*n)checkmax();//检查当前解是否是可行解,若是则把它的价值与max比较else{search(m+1);//该位置不放堡垒递归搜索下一个位置if(canplace(m))//判断第m个格子是否能放堡垒{place(m);//在第m个格子上放置一个堡垒search(m+1);//递归搜索下一个位置takeout(m);//去掉第m个格子上放置的堡垒}}}4.翻硬币问题把硬币摆放成32×9的矩阵,你可以随意翻转矩阵中的某些行和某些列,问正面朝上的硬币最多有多少枚?提示:(1)任意一行或一列,翻两次等于没有翻;(2)对于9列的任何一种翻转的情况,每一行翻与不翻相互独立。5.8皇后问题在一个8×8的棋盘里放置8个皇后,要求这8个皇后两两之间互相都不“冲突”。#includestdio.h#includemath.hvoidsearch(int);voidprintresult();//打印结果intcanplace(int,int);//判断该位置能否放置皇后voidplace(int,int);//在该位置能否放置皇后voidtakeout(int,int);//把该位置放置皇后去掉inta[8];//a[i]存放第i个皇后的位置intmain(){search(0);//递归搜索}voidsearch(intm){inti;if(m=8)//当已经找出一组解时printresult();//输出当前结果else{for(i=0;i8;i++)//对当前行0到7列的每一个位置{if(canplace(m,i))//判断第m个格子是否能放堡垒{place(m,i);//在(m,i)格子上放置一个皇后search(m+1);//递归搜索