5-13 朋友 (30分)

发表于 STL容器 分类,标签:
 【问题描述】同学们应该学会多交一些好朋友。朋友关系是相互的,A是B的好朋友,则B也是A的好朋友。朋友关系是不传递的,A是B的好朋友,B是C的好朋友,但A和C不一定是好朋友。现在给出某小学部分同学之间的朋友关系,请编程统计朋友最多的人有多少个好朋友。【输入数据】输入共m+1行。第1行是两个整数n和m,分别表示同学总人数和朋友关系对数。第2行到第m+1行,描述了m对朋友关系。每行两个用单个空格隔开的同学姓名。每个人的姓名仅由小写字母组成,且1≤姓名的长度≤10。【输出数据】一个整数,表示朋友最多的人有多少个好朋友。【输入输出样例1】43lucylilyjamlilyjampeter2【样例1解释】4个人,3对朋友关系。lucy只有一个朋友lily;jam有两个朋友lily和peter;lily有两个朋友lucy和jam;peter只有一个朋友jam。所以l...

从头到尾彻底理解KMP(转)

发表于 算法模板 分类,标签:
转自:http://blog.csdn.net/v_july_v/article/details/7041827作者:July时间:最初写于2011年12月,2014年7月21日晚10点全部删除重写成此文,随后的半个多月不断反复改进。后收录于新书《编程之法:面试和算法心得》第4.4节中。 1.引言  本KMP原文最初写于2年多前的2011年12月,因当时初次接触KMP,思路混乱导致写也写得混乱。所以一直想找机会重新写下KMP,但苦于一直以来对KMP的理解始终不够,故才迟迟没有修改本文。  然近期因开了个算法班,班上专门讲解数据结构、面试、算法,才再次仔细回顾了这个KMP,在综合了一些网友的理解、以及算法班的两位讲师朋友曹博、邹博的理解之后,写了9张PPT,发在微博上。随后,一不做二不休,索性将PPT上的内容整理到了本文之中(后来...

L3-009. 长城

发表于 数论 分类,标签: 天梯赛
 正如我们所知,中国古代长城的建造是为了抵御外敌入侵。在长城上,建造了许多烽火台。每个烽火台都监视着一个特定的地区范围。一旦某个地区有外敌入侵,值守在对应烽火台上的士兵就会将敌情通报给周围的烽火台,并迅速接力地传递到总部。现在如图1所示,若水平为南北方向、垂直为海拔高度方向,假设长城就是依次相联的一系列线段,而且在此范围内的任一垂直线与这些线段有且仅有唯一的交点。图1进一步地,假设烽火台只能建造在线段的端点处。我们认为烽火台本身是没有高度的,每个烽火台只负责向北方(图1中向左)瞭望,而且一旦有外敌入侵,只要敌人与烽火台之间未被山体遮挡,哨兵就会立即察觉。当然,按照这一军规,对于南侧的敌情各烽火台并不负责任。一旦哨兵发现敌情,他就会立即以狼烟或烽火的形式,向其南方的烽火台传递警报,直到位于最南侧的总部。以图2中的长城为例,负责守卫的四个烽火台用蓝白圆点示意,最南侧的总部用红色圆点...

L3-011. 直捣黄龙(最短路)

wang 发表于 图论 分类,标签: 天梯赛
 本题是一部战争大片——你需要从己方大本营出发,一路攻城略地杀到敌方大本营。首先时间就是生命,所以你必须选择合适的路径,以最快的速度占领敌方大本营。当这样的路径不唯一时,要求选择可以沿途解放最多城镇的路径。若这样的路径也不唯一,则选择可以有效杀伤最多敌军的路径。输入格式:输入第一行给出2个正整数N(2<=N<=200,城镇总数)和K(城镇间道路条数),以及己方大本营和敌方大本营的代号。随后N-1行,每行给出除了己方大本营外的一个城镇的代号和驻守的敌军数量,其间以空格分隔。再后面有K行,每行按格式“城镇1城镇2距离”给出两个城镇之间道路的长度。这里设每个城镇(包括双方大本营)的代号是由3个大写英文字母组成的字符串。输出格式:按照题目要求找到最合适的进攻路径(题目保证速度最快、解放最多、杀伤最强的路径是唯一的),并在第一行按照格式“己方大本营->城镇...

L3-005. 垃圾箱分布

wang 发表于 图论 分类,标签: 天梯赛
 大家倒垃圾的时候,都希望垃圾箱距离自己比较近,但是谁都不愿意守着垃圾箱住。所以垃圾箱的位置必须选在到所有居民点的最短距离最长的地方,同时还要保证每个居民点都在距离它一个不太远的范围内。现给定一个居民区的地图,以及若干垃圾箱的候选地点,请你推荐最合适的地点。如果解不唯一,则输出到所有居民点的平均距离最短的那个解。如果这样的解还是不唯一,则输出编号最小的地点。输入格式:输入第一行给出4个正整数:N(<=103)是居民点的个数;M(<=10)是垃圾箱候选地点的个数;K(<=104)是居民点和垃圾箱候选地点之间的道路的条数;DS是居民点与垃圾箱之间不能超过的最大距离。所有的居民点从1到N编号,所有的垃圾箱候选地点从G1到GM编号。随后K行,每行按下列格式描述一条道路:P1P2Dist其中P1和P2是道路两端点的编号,端点可以是居民点,也可以是垃圾箱候选点。D...

L3-008. 喊山

wang 发表于 图论 分类,标签: 天梯赛
 喊山,是人双手围在嘴边成喇叭状,对着远方高山发出“喂—喂喂—喂喂喂……”的呼唤。呼唤声通过空气的传递,回荡于深谷之间,传送到人们耳中,发出约定俗成的“讯号”,达到声讯传递交流的目的。原来它是彝族先民用来求援呼救的“讯号”,慢慢地人们在生活实践中发现了它的实用价值,便把它作为一种交流工具世代传袭使用。(图文摘自:http://news.xrxxw.com/newsshow-8018.html)一个山头呼喊的声音可以被临近的山头同时听到。题目假设每个山头最多有两个能听到它的临近山头。给定任意一个发出原始信号的山头,本题请你找出这个信号最远能传达到的地方。输入格式:输入第一行给出3个正整数n、m和k,其中n(<=10000)是总的山头数(于是假设每个山头从1到n编号)。接下来的m行,每行给出2个不超过n的正整数,数字间用空格分开,分别代表可以听到彼此的两个山头的编号。这里保证每...

L3-007. 天梯地图

wang 发表于 图论 分类,标签: 天梯赛
 本题要求你实现一个天梯赛专属在线地图,队员输入自己学校所在地和赛场地点后,该地图应该推荐两条路线:一条是最快到达路线;一条是最短距离的路线。题目保证对任意的查询请求,地图上都至少存在一条可达路线。输入格式:输入在第一行给出两个正整数N(2<=N<=500)和M,分别为地图中所有标记地点的个数和连接地点的道路条数。随后M行,每行按如下格式给出一条道路的信息:V1V2one-waylengthtime其中V1和V2是道路的两个端点的编号(从0到N-1);如果该道路是从V1到V2的单行线,则one-way为1,否则为0;length是道路的长度;time是通过该路所需要的时间。最后给出一对起点和终点的编号。输出格式:首先按下列格式输出最快到达的时间T和用节点编号表示的路线:Time=T:起点=>节点1 =>...=>...

L2-016. 愿天下有情人都是失散多年的兄妹

wang 发表于 搜索 分类,标签: 天梯赛
 呵呵。大家都知道五服以内不得通婚,即两个人最近的共同祖先如果在五代以内(即本人、父母、祖父母、曾祖父母、高祖父母)则不可通婚。本题就请你帮助一对有情人判断一下,他们究竟是否可以成婚?输入格式:输入第一行给出一个正整数N(2<=N<=104),随后N行,每行按以下格式给出一个人的信息:本人ID性别父亲ID母亲ID其中ID是5位数字,每人不同;性别M代表男性、F代表女性。如果某人的父亲或母亲已经不可考,则相应的ID位置上标记为-1。接下来给出一个正整数K,随后K行,每行给出一对有情人的ID,其间以空格分隔。注意:题目保证两个人是同辈,每人只有一个性别,并且血缘关系网中没有乱伦或隔辈成婚的情况。输出格式:对每一对有情人,判断他们的关系是否可以通婚:如果两人是同性,输出“NeverMind”;如果是异性并且关系出了五服,输出“Yes”;如果异性关系未出五服,...

L3-002. 堆栈

wang 发表于 分类,标签: 天梯赛
 大家都知道“堆栈”是一种“先进后出”的线性结构,基本操作有“入栈”(将新元素插入栈顶)和“出栈”(将栈顶元素的值返回并从堆栈中将其删除)。现请你实现一种特殊的堆栈,它多了一种操作叫“查中值”,即返回堆栈中所有元素的中值。对于N个元素,若N是偶数,则中值定义为第N/2个最小元;若N是奇数,则中值定义为第(N+1)/2个最小元。输入格式:输入第一行给出正整数N(<=105)。随后N行,每行给出一个操作指令,为下列3种指令之一:Push keyPopPeekMedian其中Push表示入栈,key是不超过105的正整数;Pop表示出栈;PeekMedian表示查中值。输出格式:对每个入栈指令,将key入栈,并不输出任何信息。对每个出栈或查中值的指令,在一行中打印相应的返回结果。若指令非法,就打印“Invalid”。输入样例:17PopPeekMedian...

L2-013. 红色警报

wang 发表于 并查集 分类,标签: 天梯赛
 战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序,当失去一个城市导致国家被分裂为多个无法连通的区域时,就发出红色警报。注意:若该国本来就不完全连通,是分裂的k个区域,而失去一个城市并不改变其他城市之间的连通性,则不要发出警报。输入格式:输入在第一行给出两个整数N(0<N<=500)和M(<=5000),分别为城市个数(于是默认城市从0到N-1编号)和连接两城市的通路条数。随后M行,每行给出一条通路所连接的两个城市的编号,其间以1个空格分隔。在城市信息之后给出被攻占的信息,即一个正整数K和随后的K个被攻占的城市的编号。注意:输入保证给出的被攻占的城市编号都是合法的且无重复,但并不保证给出的通路没有重复。输出格式:对每个被攻占的城市,如果它会改变整个国家的连通性,则输出“RedAlert:Citykislost!”,其中k是该城市的...