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

2011年ACM-ICPC协会程序设计大赛解题报告（part1）PSJay 09计科Problem1:ZOJProblem1:ZOJDescriptionDescription 读入一个字符串，字符串中包含ZOJ三个字符，个数不一定相等，按ZOJ的顺序输出，当某个字符用完时，剩下的仍然按照ZOJ的顺序输出。Problem1:ZOJInputInput题目包含多组用例,每组用例占一行，包含ZOJ三个字符，当输入“E”时表示输入结束。1=length=100。OutputOutput对于每组输入,请输出一行，表示按照要求处理后的字符串。具体可见样例。Problem1:ZOJSample InputZZOOOJJJZZZZOOOOOJJJZOOOJJESample OutputZOJZOJOJZOJZOJZOJZOOZOJOJOProblem1:ZOJAnalysisAnalysis 要将字符串按照 ZOJ 的顺序输出，只需要记录字符 Z、O、J 各自在字符串中出现的次数即可。Problem1:ZOJSolutionSolution1.输入字符串；2.分析字符串，分别记录字符 Z,O,J 出现的次数；3.输出结果。Problem1:ZOJBeginners GuideBeginners Guidel 解题格式；l Input 和 Output 的格式；l 不管通过何种方式实现，只需输出正确答案。Problem2:畅通工程Problem2:畅通工程DescriptionDescription某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？Problem2:畅通工程InputInput测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目(N 1000)和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。注意:两个城市之间可以有多条道路相通,也就是说3 31 21 22 1这种输入也是合法的当N为0时，输入结束，该用例不被处理。Problem2:畅通工程OutputOutput对每个测试用例，在1行里输出最少还需要建设的道路数目。Problem2:畅通工程Sample Input4 21 34 33 31 21 32 35 21 23 5999 00Sample Output102998Problem2:畅通工程AnalysisAnalysis1234Case 1:Problem2:畅通工程AnalysisAnalysis123Case 2:Problem2:畅通工程AnalysisAnalysis12345Case 3:Problem2:畅通工程Key PointKey Point找出 n 个互不相交的城镇集合，结果就为 n 1。Problem2:畅通工程Preparation KnowledgePreparation Knowledge表示集合的三种方式（数据结构）：数组，树，图。Problem2:畅通工程Preparation KnowledgePreparation KnowledgeABCDEFProblem2:畅通工程SolutionSolution1.假设每个城市都是不相交的；（每个元素都是树根）2.随着道路的连接，将连通的城市合并到同一个集合；（集合中的元素拥有同样的树根）3.统计出一共有多少个集合，输出结果。Problem2:畅通工程Examples12345Problem2:畅通工程Examples123451134511343