ACM-ICPC协会程序设计大赛解题报告.ppt

2011年ACM-ICPC协会程序设计大赛解题报告（part1）,PSJay09计科,Problem1:ZOJ,Problem1:ZOJ,Description读入一个字符串，字符串中包含ZOJ三个字符，个数不一定相等，按ZOJ的顺序输出，当某个字符用完时，剩下的仍然按照ZOJ的顺序输出。,Problem1:ZOJ,Input题目包含多组用例,每组用例占一行，包含ZOJ三个字符，当输入“E”时表示输入结束。1=length=100。Output对于每组输入,请输出一行，表示按照要求处理后的字符串。具体可见样例。,Problem1:ZOJ,Problem1:ZOJ,Analysis要将字符串按照ZOJ的顺序输出，只需要记录字符Z、O、J各自在字符串中出现的次数即可。,Problem1:ZOJ,Solution输入字符串；分析字符串，分别记录字符Z,O,J出现的次数；输出结果。,Problem1:ZOJ,BeginnersGuide解题格式；Input和Output的格式；不管通过何种方式实现，只需输出正确答案。,Problem2:畅通工程,Problem2:畅通工程,Description某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？,Problem2:畅通工程,Input测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目(N1000)和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。注意:两个城市之间可以有多条道路相通,也就是说33121221这种输入也是合法的当N为0时，输入结束，该用例不被处理。,Problem2:畅通工程,Output对每个测试用例，在1行里输出最少还需要建设的道路数目。,Problem2:畅通工程,Problem2:畅通工程,Analysis,1,2,3,4,Case1:,Problem2:畅通工程,Analysis,1,2,3,Case2:,Problem2:畅通工程,Analysis,1,2,3,4,5,Case3:,Problem2:畅通工程,KeyPoint,找出n个互不相交的城镇集合，结果就为n1。,Problem2:畅通工程,PreparationKnowledge,表示集合的三种方式（数据结构）：数组，树，图。,Problem2:畅通工程,PreparationKnowledge,Problem2:畅通工程,Solution假设每个城市都是不相交的；（每个元素都是树根）随着道路的连接，将连通的城市合并到同一个集合；（集合中的元素拥有同样的树根）统计出一共有多少个集合，输出结果。,Problem2:畅通工程,Examples,1,2,3,4,5,Problem2:畅通工程,Examples,