信息学奥赛一本通T1388：并查集 家谱
【题目描述】现代的人对于本家族血统越来越感兴趣，现在给出充足的父子关系，请你编写程序找到某个人的最早的祖先。【输入】由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系由二行组成，用#name的形式描写一组父子关系中的父亲的名字，用+name的形式描写一组父子关系中的儿子的名字；接下来用?name的形式表示要求该人的最早的祖先；最后用单独的一个$表示文件结束。规定每个人的名字都有且只有6
- 0
- 0
- 轩爸
- 发布于 2020-05-16 10:20
- 阅读 ( 769 )
轩爸
信息学奥赛一本通T1386：并查集 打击犯罪
【题目描述】某个地区有n(n≤1000)个犯罪团伙，当地警方按照他们的危险程度由高到低给他们编号为1-n，他们有些团伙之间有直接联系，但是任意两个团伙都可以通过直接或间接的方式联系，这样这里就形成了一个庞大的犯罪集团，犯罪集团的危险程度由集团内的犯罪团伙数量唯一确定，而与单个犯罪团伙的危险程度无关（该犯罪集团的危险程度为n）。现在当地警方希望花尽量少的时间（即打击掉尽量少的团伙），使得庞大的犯罪集
- 0
- 0
- 轩爸
- 发布于 2020-05-16 10:20
- 阅读 ( 1057 )
信息学奥赛一本通T1385：并查集 团伙
【题目描述】在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足：1、我朋友的朋友是我的朋友；2、我敌人的敌人是我的朋友；所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？【输入】第1行为n和m，1<n<1000,1≤m≤100 000；以下m行，每行为p x y，p的值为0
- 0
- 0
- 轩爸
- 发布于 2020-05-15 16:20
- 阅读 ( 790 )
信息学奥赛一本通T1384：图的连通性问题 珍珠
【题目描述】有n颗形状和大小都一致的珍珠，它们的重量都不相同。n为整数，所有的珍珠从1到n编号。你的任务是发现哪颗珍珠的重量刚好处于正中间，即在所有珍珠的重量中，该珍珠的重量列(n+1)/2位。下面给出将一对珍珠进行比较的办法：给你一架天平用来比较珍珠的重量，我们可以比出两个珍珠哪个更重一些，在作出一系列的比较后，我们可以将某些肯定不具备中间重量的珍珠拿走。例如，下列给出对5颗珍珠进行四次比较的情
- 0
- 0
- 轩爸
- 发布于 2020-05-15 16:20
- 阅读 ( 768 )
信息学奥赛一本通T1382：最短路径算法 最短路
【题目描述】给定 M 条边， N 个点的带权无向图。求 1 到 N 的最短路。【输入】第一行：N,M(N≤100000，M≤500000)接下来M行3个正整数：ai,bi,ci表示ai,bi之间有一条长度为ci的路，ci≤1000。【输出】一个整数，表示 1 到 N 的最短距离。【输入样例】4 4【输出样例】2【源程序】
- 0
- 0
- 轩爸
- 发布于 2020-05-15 16:20
- 阅读 ( 1197 )
信息学奥赛一本通T1383：图的连通性问题 刻录光盘
【题目描述】在FJOI2010夏令营快要结束的时候，很多营员提出来要把整个夏令营期间的资料刻录成一张光盘给大家，以便大家回去后继续学习。组委会觉得这个主意不错！可是组委会一时没有足够的空光盘，没法保证每个人都能拿到刻录上资料的光盘，怎么办呢？！DYJ分析了一下所有营员的地域关系，发现有些营员是一个城市的，其实他们只需要一张就可以了，因为一个人拿到光盘后，其他人可以带着U盘之类的东西去拷贝啊！他们愿
- 0
- 0
- 轩爸
- 发布于 2020-05-15 16:20
- 阅读 ( 632 )
信息学奥赛一本通T1381：最短路径算法 城市路
【题目描述】罗老师被邀请参加一个舞会，是在城市n，而罗老师当前所处的城市为1,附近还有很多城市2~n-1，有些城市之间没有直接相连的路，有些城市之间有直接相连的路，这些路都是双向的，当然也可能有多条。现在给出直接相邻城市的路长度，罗老师想知道从城市1到城市n，最短多少距离。【输入】输入n, m，表示n个城市和m条路;接下来m行，每行a b c， 表示城市a与城市b有长度为c的路。【输出】输出1到n
- 0
- 0
- 轩爸
- 发布于 2020-05-15 16:20
- 阅读 ( 1216 )
信息学奥赛一本通T1380：最短路径算法 分糖果
【题目描述】童年的我们，将和朋友分享美好的事物作为自己的快乐。这天，C小朋友得到了Plenty of candies，将要把这些糖果分给要好的朋友们。已知糖果从一个人传给另一个人需要1 秒的时间，同一个小朋友不会重复接受糖果。由于糖果足够多，如果某时刻某小朋友接受了糖果，他会将糖果分成若干份，分给那些在他身旁且还没有得到糖果的小朋友们，而且自己会吃一些糖果。由于嘴馋，小朋友们等不及将糖果发完，会在
- 0
- 0
- 轩爸
- 发布于 2020-05-15 10:20
- 阅读 ( 1000 )
信息学奥赛一本通T1379：最短路径算法 热浪
【题目描述】德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪！！！他们的德克萨斯长角牛吃起来不错，可是他们并不是很擅长生產富含奶油的乳製品。Farmer John此时以先天下之忧而忧，后天下之乐而乐的精神，身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。FJ已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过T (1 ≤
- 0
- 0
- 轩爸
- 发布于 2020-05-15 10:20
- 阅读 ( 680 )
信息学奥赛一本通T1378：最短路径算法 最短路径
【题目描述】给出一个有向图G=(V, E)，和一个源点v0∈V，请写一个程序输出v0和图G中其它顶点的最短路径。只要所有的有向环权值和都是正的，我们就允许图的边有负值。顶点的标号从1到n（n为图G的顶点数）。【输入】第1行：一个正数n（2≤n≤80），表示图G的顶点总数。第2行：一个整数，表示源点v0（v0∈V，v0可以是图G中任意一个顶点）。第3至第n+2行，用一个邻接矩阵W给出了这个图。【输出
- 0
- 0
- 轩爸
- 发布于 2020-05-15 10:20
- 阅读 ( 832 )
信息学奥赛一本通T1377：最短路径算法 最优乘车
【题目描述】H城是一个旅游胜地，每年都有成千上万的人前来观光。为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴士线路。每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。一名旅客最近到H城旅游，他很想去S公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达S公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士, 这样换乘几
- 0
- 0
- 轩爸
- 发布于 2020-05-15 10:20
- 阅读 ( 783 )
信息学奥赛一本通T1376：最短路径算法 信使
【题目描述】战争时期，前线有n个哨所，每个哨所可能会与其他若干个哨所之间有通信联系。信使负责在哨所之间传递信息，当然，这是要花费一定时间的（以天为单位）。指挥部设在第一个哨所。当指挥部下达一个命令后，指挥部就派出若干个信使向与指挥部相连的哨所送信。当一个哨所接到信后，这个哨所内的信使们也以同样的方式向其他哨所送信。直至所有n个哨所全部接到命令后，送信才算成功。因为准备充足，每个哨所内都安排了足够的
- 0
- 0
- 轩爸
- 发布于 2020-05-15 10:20
- 阅读 ( 744 )
信息学奥赛一本通T1375：图的遍历 骑马修栅栏
【题目描述】农民John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。John是一个与其他农民一样懒的人。他讨厌骑马，因此从来不两次经过一个一个栅栏。你必须编一个程序，读入栅栏网络的描述，并计算出一条修栅栏的路径，使每个栅栏都恰好被经过一次。John能从任何一个顶点(即两个栅栏的交点)开始骑马，在任意一个顶点结束。每一个栅栏连接两个顶点，顶点用1到500标号(虽然有的农场并没
- 0
- 0
- 轩爸
- 发布于 2020-05-14 16:20
- 阅读 ( 638 )
信息学奥赛一本通T1374：图的遍历 铲雪车
【题目描述】随着白天越来越短夜晚越来越长，我们不得不考虑铲雪问题了。整个城市所有的道路都是双车道，因为城市预算的削减，整个城市只有1辆铲雪车。铲雪车只能把它开过的地方（车道）的雪铲干净，无论哪儿有雪，铲雪车都得从停放的地方出发，游历整个城市的街道。现在的问题是：最少要花多少时间去铲掉所有道路上的雪呢？【输入】输入数据的第1行表示铲雪车的停放坐标（x,y），x，y为整数，单位为米。下面最多有100行
- 0
- 0
- 轩爸
- 发布于 2020-05-14 16:20
- 阅读 ( 1035 )
信息学奥赛一本通T1372：堆及其应用 小明的账单
【题目描述】小明在一次聚会中，不慎遗失了自己的钱包，在接下来的日子，面对小明的将是一系列的补卡手续和堆积的账单… 在小明的百般恳求下，老板最终同意延缓账单的支付时间。可老板又提出，必须从目前还没有支付的所有账单中选出面额最大和最小的两张，并把他们付清。还没有支付的账单会被保留到下一天。 请你帮他计算出支付的顺序。【输入】第1行：一个正整数N(N≤15,000)，表示小明补办银联卡总共的天数。第2行
- 0
- 0
- 轩爸
- 发布于 2020-05-14 16:20
- 阅读 ( 1192 )
信息学奥赛一本通T1373：堆及其应用 鱼塘钓鱼
【题目描述】有N个鱼塘排成一排（N<100），每个鱼塘中有一定数量的鱼，例如：N=5时，如下表：即：在第1个鱼塘中钓鱼第1分钟内可钓到10条鱼，第2分钟内只能钓到8条鱼，……，第5分钟以后再也钓不到鱼了。从第1个鱼塘到第2个鱼塘需要3分钟，从第2个鱼塘到第3个鱼塘需要5分钟，……给出一个截止时间T(T<1000)，设计一个钓鱼方案，从第1个鱼塘出发，希望能钓到最多的鱼。假设能钓到鱼的数
- 0
- 0
- 轩爸
- 发布于 2020-05-14 16:20
- 阅读 ( 749 )
信息学奥赛一本通T1371：堆及其应用 看病
【题目描述】有个朋友在医院工作，想请BSNY帮忙做个登记系统。具体是这样的，最近来医院看病的人越来越多了，因此很多人要排队，只有当空闲时放一批病人看病。但医院的排队不同其他排队，因为多数情况下，需要病情严重的人优先看病，所以希望BSNY设计系统时，以病情的严重情况作为优先级，判断接下来谁可以去看病。【输入】第一行输入n，表示有n个操作。对于每个操作，首先输入push或pop。push的情况，之后会
- 0
- 0
- 轩爸
- 发布于 2020-05-14 16:20
- 阅读 ( 648 )
信息学奥赛一本通T1370：堆及其应用 最小函数值
【题目描述】有n个函数，分别为F1,F2,...,Fn。定义Fi(x)=Aix2+Bix+Ci(x∈N∗)。给定这些Ai、Bi和Ci，请求出所有函数的所有函数值中最小的m个（如有重复的要输出多个）。【输入】第一行输入两个正整数n和m。以下n行每行三个正整数，其中第ii行的三个数分别位Ai、Bi和Ci。输入数据保证Ai≤10，Bi≤100，Ci≤10000。【输出】将这n个函数所有可以生成的函数值排
- 0
- 0
- 轩爸
- 发布于 2020-05-14 10:20
- 阅读 ( 805 )
信息学奥赛一本通T1369：堆及其应用 合并果子
【题目描述】在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重
- 0
- 0
- 轩爸
- 发布于 2020-05-14 10:20
- 阅读 ( 645 )
信息学奥赛一本通T1368：树与二叉树 对称二叉树
【题目描述】如果二叉树的左右子树的结构是对称的，即两棵子树皆为空，或者皆不空，则称该二叉树是对称的。编程判断给定的二叉树是否对称.例：如下图中的二叉树T1是对称的，T2是不对称的。二叉树用顺序结构给出，若读到#则为空，二叉树T1=ABCDE，T2=ABCD#E，如果二叉树是对称的，输出“Yes”,反之输出“No”。【输入】二叉树用顺序结构给出，若读到#则为空。【输出】如果二叉树是对称的，输出“Ye
- 0
- 1
- 轩爸
- 发布于 2020-05-14 10:20
- 阅读 ( 986 )
