ACMICPC协会程序设计大赛解题报告.pptx

《ACMICPC协会程序设计大赛解题报告.pptx》由会员分享，可在线阅读，更多相关《ACMICPC协会程序设计大赛解题报告.pptx（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Problem1:ZOJ第1页/共22页Problem1:ZOJDescriptionDescription 读入一个字符串，字符串中包含ZOJ三个字符，个数不一定相等，按ZOJ的顺序输出，当某个字符用完时，剩下的仍然按照ZOJ的顺序输出。第2页/共22页Problem1:ZOJInputInput题目包含多组用例,每组用例占一行，包含ZOJ三个字符，当输入“E”时表示输入结束。1=length=100。OutputOutput对于每组输入,请输出一行，表示按照要求处理后的字符串。具体可见样例。第3页/共22页Problem1:ZOJSample InputZZOOOJJJZZZZOOOOOJ

2、JJZOOOJJESample OutputZOJZOJOJZOJZOJZOJZOOZOJOJO第4页/共22页Problem1:ZOJAnalysisAnalysis 要将字符串按照 ZOJ 的顺序输出，只需要记录字符 Z、O、J 各自在字符串中出现的次数即可。第5页/共22页Problem1:ZOJSolutionSolution1.输入字符串；2.分析字符串，分别记录字符 Z,O,J 出现的次数；3.输出结果。第6页/共22页Problem1:ZOJBeginners Guidel解题格式；lInput 和 Output 的格式；l不管通过何种方式实现，只需输出正确答案。第7页/共22页

3、Problem2:畅通工程第8页/共22页Problem2:畅通工程DescriptionDescription某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？第9页/共22页Problem2:畅通工程InputInput测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目(N 1000)和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起

4、见，城镇从1到N编号。注意:两个城市之间可以有多条道路相通,也就是说3 31 21 22 1这种输入也是合法的当N为0时，输入结束，该用例不被处理。第10页/共22页Problem2:畅通工程OutputOutput对每个测试用例，在1行里输出最少还需要建设的道路数目。第11页/共22页Problem2:畅通工程Sample Input4 21 34 33 31 21 32 35 21 23 5999 00Sample Output102998第12页/共22页Problem2:畅通工程AnalysisAnalysis1234Case 1:第13页/共22页Problem2:畅通工程Analy

5、sisAnalysis123Case 2:第14页/共22页Problem2:畅通工程AnalysisAnalysis12345Case 3:第15页/共22页Problem2:畅通工程Key PointKey Point找出 n 个互不相交的城镇集合，结果就为 n 1。第16页/共22页Problem2:畅通工程Preparation KnowledgePreparation Knowledge表示集合的三种方式（数据结构）：数组，树，图。第17页/共22页Problem2:畅通工程Preparation KnowledgePreparation KnowledgeABCDEF第18页/共22页Problem2:畅通工程SolutionSolution1.假设每个城市都是不相交的；（每个元素都是树根）2.随着道路的连接，将连通的城市合并到同一个集合；（集合中的元素拥有同样的树根）3.统计出一共有多少个集合，输出结果。第19页/共22页Problem2:畅通工程Examples12345第20页/共22页Problem2:畅通工程Examples123451134511343第21页/共22页感谢您的观看！第22页/共22页