ACM最常用算法-算法讲解-ACM大赛无压力.ppt

常用算法&数据结构2、竞赛中常见的16种题型ACMAssociationforComputingMachinery美国计算机学会ICPCInternationalCollegiateProgrammingContest国际大学生程序设计竞赛ACMICPCICPC竞赛规则ICPClog中国各高校ACM开展情况浙江大学ACM集训队选拔标准如何建立一支强队Leader/Coordinato(协调比赛进程)Reader(发现题目隐讳的涵义)Thinker(逻辑能力强,收集其他队员意见)Programmer/Debugger(反应快/稳,细心)Helper(协助比赛,查错,验证数据等)参考书籍网络资源时空复杂度的分析函数增长和运行时间常见题型常见题型常见题型常见题型20枚举法PizzaAnyone?（ZOJ1219）贪心法(Greedy)栈和队列字符串的输入与输出排序用C++实现排序并查集Parity(ceoi99)Parity(ceoi99)Parity(ceoi99)（肖天）堆(优先队列)例题:积水分析分析哈希表(Hash)Hash表的实现HashKey的选取字符串：二分搜索树树堆(Treap)跳跃表（Skiplists）线段树45Atlantis（ZOJ1128）矩形切割字典树(Trie)给如下几个单词，构造的单词树：An，Ant，All，AllotAlloy，Aloe，Are，AtebeT9（ZOJ1038）动态规划动态规划深度优先搜索(DFS)宽度优先搜索(BFS)PrimeRingProblem（ZOJ1457）while(!deque.empty()){state=deque[0];deque.pop();枚举所有可行状态{tempstate=状态改变(state);deque.push_back(tempstate);}}Winlinez(ZOJ1591)博弈问题局面AMultiplicationGame（ＺＯＪ１８９３）最大公约数最小公倍数筛选法求质数表#defineN100#defineM100intp[M],plist=0;intinit(){memset(p,0,sizeof(p));for(inti=2;i<=N;i++)if(!p[i]){p[plist++]=i;intdel=i*i;while(del<=N)p[del]=1,del+=i;}returnplist;}模算术与方程线性同余方程排列组合全排列的手工生成全排列的手工生成Catalan数Fibonacci数彩票分析数值分析生成树问题最短路问题第n短路径Arbitrage(ZOJ1092)网络流问题网络流模型最大流最小费用最大流网络流算法（金恺）二分图匹配问题二分图的最大匹配二分图的最小覆盖二分图的匹配独立集诱导子图弦图FishingNet(ZOJ1015)计算几何OnlineJudge的简称一种通过网络信息交互在线判题的系统它模拟了ICPC比赛真实的情况当前世界上规模比较大的OJUVAZOJURALUSACOZhejianguniversityonlinejudgeSubmissionError--提交使用了不正确的队名、题号等。NoSuchProblem--检查题号有没有填错？CompileError--程序不能通过编译。RunTimeError--程序运行过程中出现非正常中断。MemoryLimitExceeded--内存使用量超过裁判规定的上限。OutputLimitExceeded--输出数据量过大，多半死循环了……TimeLimitExceeded--运行超过时限还没有得到输出结果。WrongAnswer--答案错误。PresentationError--输出格式不对，可检查空格、回车等等细节。Accepted--恭喜恭喜！OutOfContestTime--比赛已经结束啦！ContestRuleViolation--宣判极刑，参赛资格随即被取消。常见问题ZOJ输入输出ZOJ输入输出ZOJ输入输出ZOJ输入输出ZOJ输入输出ZOJ输入输出SpecialJudgeDebugZOJ上的简单题谢谢！