畅通工程 题目链接：http://acm.ocrosoft.com/problem.php?cid=1672&pid=6 题目描述 某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？  输入 测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起...

题目链接：http://acm.ocrosoft.com/problem.php?cid=1615&pid=15 题目描述： John打算驾驶一辆汽车周游一个环形公路。公路上总共有n车站，每站都有若干升汽油（有的站可能油量为0），每升油可以让汽车行驶一千米。John必须从某个车站出发，一直按顺时针（或逆时针）方向走遍所有的车站，并回到起点。在一开始的时候，汽车内油量为0，John每到一个车站就把该站所有的油都带上（起点站亦是如此），行驶过程中不能出现没有油的情况。 任务：判断以每个车站为起点能否按条件成功周游一周。 输入 第一行是一个整数n(3<=n<=10000...

悠闲的漫步 题目链接：http://acm.ocrosoft.com/problem.php?cid=1616&pid=9 题目描述： Bessie looks out the barn door at the beautiful spring day and thinks to herself, 'I'd really like to enjoy my walk out to the pastures for the tender spring grass.' She knows that once she leaves the barn, she will traverse ...

题目链接：http://acm.ocrosoft.com/problem.php?cid=1629&pid=51 题目描述： 小红很喜欢玩一个叫打砖块的游戏，这个游戏的规则如下：         在刚开始的时候，有n行*m列的砖块，小红有k发子弹。小红每次可以用一发子弹，打碎某一列当前处于这一列最下面的那块砖，并且得到相应的得分。         如图所示：    某些砖块在打碎以后，还可能将得到一发子弹的奖励。最后当所有的砖块都打碎了，或者小红没有子弹了，游戏结束。         小红在游戏开始之前，就已经知道每一块砖在打碎以后的得分，并且知道能不能得到一发奖励的子弹。小...

题目链接：http://acm.ocrosoft.com/problem.php?cid=1630&pid=16 题目描述： 太平王世子事件后，陆小凤成了皇上特聘的御前一品侍卫。     皇宫以午门为起点，直到后宫嫔妃们的寝宫，呈一棵树的形状；有边直接相连的宫殿可以互相望见。大内保卫森严，三步一岗，五步一哨，每个宫殿都要有人全天候看守，在不同的宫殿安排看守所需的费用不同。      可是陆小凤手上的经费不足，无论如何也没法在每个宫殿都安置留守侍卫。     编程任务：帮助陆小凤布置侍卫，在看守全部宫殿的前提下，使得花费的经费最少。 输入     输入文件中数据表示一棵树，...

题目链接：http://acm.ocrosoft.com/problem.php?cid=1629&pid=52 题目描述： 追踪每头奶牛的去向是一件棘手的任务，为此农夫约翰安装了一套自动系统。他在每头牛身上安装了一个电子身份标签，当奶牛通过扫描器的时候，系统可以读取奶牛的身份信息。目前，每个身份都是由一个字符串组成的，长度为M (1≤M≤2000)，所有的字符都取自小写的罗马字母。 奶牛们都是顽皮的动物，有时她们会在通过扫描器的时候倒着走，这样一个原来身份为abcb的奶牛就可能有两个不同的身份了（abcb和bcba），而如果身份是abcba的话就不会有这个问题了。 约翰想改变...

题目链接： http://acm.ocrosoft.com/problem.php?id=3820&csrf=tjfBLvtdhbKaa1ah9Far89NIeKl3bTTa 题目描述 某人读完《聊斋志异》，编出这样一道题。题目为：现有男鬼(b)、女鬼(r)、小鬼(w)共n人(n<400)，围站成一环（小鬼可以算是男的也可以算是女的）。从某人开始分别在两边数连续相同性别数（两边的性别可不同），直到第一次发现不同性别为止。当前数的这个人至少要同左右两边中的一方具有相同性别，并算到总数中去。 输入 第1行为人的数目n，第2行为n个字符（只有b，r，w三个情况）。 输出 ...

题目链接：http://acm.ocrosoft.com/problem.php?cid=1629&pid=53 题目描述： Er-pang又跟生哥去网吧打LOL（英雄联盟），er-pang还是用他最爱的爆破鬼才-吉格斯，生哥还是用他花重金买下的冰晶凤凰-艾尼维亚。每次生哥都被虐的很惨。 生哥终于忍不住了，他居然开挂了！ 开了挂后的凤凰越飞越高，居然还出现了n-1个幻象（逆天了），加上本尊一共n个凤凰在天上乱飞。由于爆破鬼才的视力极好，可以在瞬间扔出炸弹并炸死凤凰或是幻象。所以我们可以看做三维立体空间中有n个不动的凤凰，每个凤凰有一个坐标（x，y，z）。爆破鬼才的炸弹爆炸后不会...

题目链接：http://acm.ocrosoft.com/problem.php?id=1246 题目描述： 下图为5个放置在9x8 的点阵中的方框图:若将他们按顺序叠放起来.则会有某些框的一部分盖住了另外一个框,遮住一些部分. 下图是这5个框叠放起来的图形:那么这些方框从下至上叠放的顺序是什么呢?答案是: EDABC.你的任务是对于一个给定的方框叠放以后的图形, 找出他们从下至上的叠放顺序.下面是一些规则: (1). 方框的边宽度为一个字符,边长不少于3个字符; (2). 每个方框的4条边都有一部分可见, 一个角代表两条边; (3). 方框用大写字母了表示, 没有两个方框用相同的字符来表...

题目链接: http://acm.ocrosoft.com/problem.php?cid=1629&pid=54 题目描述： 花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。 具体而言，栋栋的花的高度可以看成一列整数ℎ1, ℎ2, … , ℎn。设当一部分花被移走后，剩下的花的高度依次为g1, g2, … , gm，则栋栋希望下面两个条件中至少有一个满足： 条件 A：对于所有的1 ≤ i ≤ m/2，g2i > g2i−1，且g2i &g...

题目链接：http://acm.ocrosoft.com/problem.php?cid=1634&pid=4 题目描述 自从到了南蛮之地，孔明不仅把孟获收拾的服服帖帖，而且还发现了不少少数民族的智慧，他发现少数民族的图腾往往有着一种分形的效果(看Hint)，在得到了酋长的传授后，孔明掌握了不少绘图技术，但唯独不会画他们的图腾，于是他找上了你的爷爷的爷爷的爷爷的爷爷……帮忙，作为一个好孙子的孙子的孙子的孙子……你能做到吗？ 输入 每个数据一个数字，表示图腾的大小（此大小非彼大小）  n< =10 输出 这个大小的图腾 样例输入 2 样例输出    /\ ...

题目链接：http://acm.ocrosoft.com/problem.php?cid=1629&pid=55 题目描述： 一家软件开发公司有两个项目，并且这两个项目都由相同数量的m个子项目组成，对于同一个项目，每个子项目都是相互独立且工作量相当的。由于时效性，两个项目必须同时被完成，如果其中一个完成的早了，那么这两个项目都会无效。 这家公司有n名程序员分配给这两个项目，每个子项目必须由一名程序员一次完成，多名程序员可以同时做同一个项目中的不同子项目。 求公司完成两个项目的最少时间。 输入 第一行两个正整数n，m（1<=n<=100,1<=m<=1...

题目链接：http://acm.ocrosoft.com/problem.php?cid=1634&pid=3 题目描述 设有字符串X，我们称在X的头尾及中间插入任意多个空格后构成的新字符串为X的扩展串，如字符串X为“abcbcd”，则字符串“abcb□cd”，“□a□bcbcd□”和“abcb□cd□”都是X的扩展串，这里“□”代表空格字符。 如果A1是字符串A的扩展串，B1是字符串B的扩展串，A1与B1具有相同的长度，那么我们定义字符串A1与B1的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的ASCII码的差的绝对值，而空格字符与其它任意字符之间的距离为已...

题目链接：http://acm.ocrosoft.com/problem.php?cid=1627&pid=13 题目描述： 图书馆中每本书都有一个图书编码，可以用于快速检索图书，这个图书编码是一个 正整数。 每位借书的读者手中有一个需求码，这个需求码也是一个正整数。如果一本书的图 书编码恰好以读者的需求码结尾，那么这本书就是这位读者所需要的。 小 D 刚刚当上图书馆的管理员，她知道图书馆里所有书的图书编码，她请你帮她写 一个程序，对于每一位读者，求出他所需要的书中图书编码最小的那本书，如果没有他 需要的书，请输出-1。   说明 【数据规模与约定】 对于 20%的数据，1...