文章 - 第16页 - 信奥网

信息学奥赛一本通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
阅读 ( 1217 )

【题目描述】童年的我们，将和朋友分享美好的事物作为自己的快乐。这天，C小朋友得到了Plenty of candies，将要把这些糖果分给要好的朋友们。已知糖果从一个人传给另一个人需要1 秒的时间，同一个小朋友不会重复接受糖果。由于糖果足够多，如果某时刻某小朋友接受了糖果，他会将糖果分成若干份，分给那些在他身旁且还没有得到糖果的小朋友们，而且自己会吃一些糖果。由于嘴馋，小朋友们等不及将糖果发完，会在

0
0
轩爸
发布于 2020-05-15 10:20
阅读 ( 1001 )

信息学奥赛一本通T1379：最短路径算法热浪

【题目描述】德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪！！！他们的德克萨斯长角牛吃起来不错，可是他们并不是很擅长生產富含奶油的乳製品。Farmer John此时以先天下之忧而忧，后天下之乐而乐的精神，身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。FJ已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过T (1 ≤

0
0
轩爸
发布于 2020-05-15 10:20
阅读 ( 681 )

信息学奥赛一本通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
阅读 ( 833 )

信息学奥赛一本通T1377：最短路径算法最优乘车

【题目描述】H城是一个旅游胜地，每年都有成千上万的人前来观光。为方便游客，巴士公司在各个旅游景点及宾馆，饭店等地都设置了巴士站并开通了一些单程巴士线路。每条单程巴士线路从某个巴士站出发，依次途经若干个巴士站，最终到达终点巴士站。一名旅客最近到H城旅游，他很想去S公园游玩，但如果从他所在的饭店没有一路巴士可以直接到达S公园，则他可能要先乘某一路巴士坐几站，再下来换乘同一站台的另一路巴士, 这样换乘几

0
0
轩爸
发布于 2020-05-15 10:20
阅读 ( 784 )

信息学奥赛一本通T1376：最短路径算法信使

【题目描述】战争时期，前线有n个哨所，每个哨所可能会与其他若干个哨所之间有通信联系。信使负责在哨所之间传递信息，当然，这是要花费一定时间的（以天为单位）。指挥部设在第一个哨所。当指挥部下达一个命令后，指挥部就派出若干个信使向与指挥部相连的哨所送信。当一个哨所接到信后，这个哨所内的信使们也以同样的方式向其他哨所送信。直至所有n个哨所全部接到命令后，送信才算成功。因为准备充足，每个哨所内都安排了足够的

0
0
轩爸
发布于 2020-05-15 10:20
阅读 ( 745 )

信息学奥赛一本通T1375：图的遍历骑马修栅栏

【题目描述】农民John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。John是一个与其他农民一样懒的人。他讨厌骑马，因此从来不两次经过一个一个栅栏。你必须编一个程序，读入栅栏网络的描述，并计算出一条修栅栏的路径，使每个栅栏都恰好被经过一次。John能从任何一个顶点(即两个栅栏的交点)开始骑马，在任意一个顶点结束。每一个栅栏连接两个顶点，顶点用1到500标号(虽然有的农场并没

0
0
轩爸
发布于 2020-05-14 16:20
阅读 ( 639 )

信息学奥赛一本通T1374：图的遍历铲雪车

【题目描述】随着白天越来越短夜晚越来越长，我们不得不考虑铲雪问题了。整个城市所有的道路都是双车道，因为城市预算的削减，整个城市只有1辆铲雪车。铲雪车只能把它开过的地方（车道）的雪铲干净，无论哪儿有雪，铲雪车都得从停放的地方出发，游历整个城市的街道。现在的问题是：最少要花多少时间去铲掉所有道路上的雪呢？【输入】输入数据的第1行表示铲雪车的停放坐标（x,y），x，y为整数，单位为米。下面最多有100行

0
0
轩爸
发布于 2020-05-14 16:20
阅读 ( 1036 )

信息学奥赛一本通T1372：堆及其应用小明的账单

【题目描述】小明在一次聚会中，不慎遗失了自己的钱包，在接下来的日子，面对小明的将是一系列的补卡手续和堆积的账单… 在小明的百般恳求下，老板最终同意延缓账单的支付时间。可老板又提出，必须从目前还没有支付的所有账单中选出面额最大和最小的两张，并把他们付清。还没有支付的账单会被保留到下一天。请你帮他计算出支付的顺序。【输入】第1行：一个正整数N(N≤15,000)，表示小明补办银联卡总共的天数。第2行

0
0
轩爸
发布于 2020-05-14 16:20
阅读 ( 1193 )

信息学奥赛一本通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
阅读 ( 754 )

信息学奥赛一本通T1371：堆及其应用看病

【题目描述】有个朋友在医院工作，想请BSNY帮忙做个登记系统。具体是这样的，最近来医院看病的人越来越多了，因此很多人要排队，只有当空闲时放一批病人看病。但医院的排队不同其他排队，因为多数情况下，需要病情严重的人优先看病，所以希望BSNY设计系统时，以病情的严重情况作为优先级，判断接下来谁可以去看病。【输入】第一行输入n，表示有n个操作。对于每个操作，首先输入push或pop。push的情况，之后会

0
0
轩爸
发布于 2020-05-14 16:20
阅读 ( 648 )

预告：近期NOI Online培训日历

继NOI Online测试后，CCF于5月开启培训，邀请NOI钻石和NOI金牌教师担任主讲人，每周二在NOI网站准时上新。NOI Online培训上线以来，播放量持续增加，被称为“最正规的信奥培训”，为广大Oier带来一波又一波福利。为便于大家第一时间了解培训动态，现发布5月培训日历，请做好笔记，记得准时收看。序号主讲人内容标题状态第1期朱全民程序的顺序结构请查看第2期宋新波顺序结构的应用请查看第...

0
0
轩爸
发布于 2020-05-14 10:21
阅读 ( 521 )

预告：NOI钻石教练叶国平开讲

在上期培训中，我们跟随NOI金牌教师蔺洋学习了选择结构（上）的相关知识，不知大家是否意犹未尽？不要紧！第三期培训将于5月19日如期而至。本次主讲人为NOI钻石教师、安徽师范大学附属中学叶国平，他将继续就选择结构（下）的相关问题进行讲解。培训视频将于5月19日16点在NOI官网更新，敬请期待！讲师介绍叶国平，CCF会员。NOI钻石教师，CCF杰出演讲者，安徽师大附中信息学竞赛教练。指导3位同学获国...

0
0
轩爸
发布于 2020-05-14 10:21
阅读 ( 671 )

信息学奥赛一本通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
阅读 ( 806 )

信息学奥赛一本通T1369：堆及其应用合并果子

【题目描述】在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重

0
0
轩爸
发布于 2020-05-14 10:20
阅读 ( 646 )

信息学奥赛一本通T1368：树与二叉树对称二叉树

【题目描述】如果二叉树的左右子树的结构是对称的，即两棵子树皆为空，或者皆不空，则称该二叉树是对称的。编程判断给定的二叉树是否对称.例：如下图中的二叉树T1是对称的，T2是不对称的。二叉树用顺序结构给出，若读到#则为空，二叉树T1=ABCDE，T2=ABCD#E，如果二叉树是对称的，输出“Yes”,反之输出“No”。【输入】二叉树用顺序结构给出，若读到#则为空。【输出】如果二叉树是对称的，输出“Ye

0
1
轩爸
发布于 2020-05-14 10:20
阅读 ( 987 )

信息学奥赛一本通T1367：树与二叉树查找二叉树

【题目描述】已知一棵二叉树用邻接表结构存储，中序查找二叉树中值为x的结点，并指出是第几个结点。例：如图二叉树的数据文件的数据格式如下:【输入】第一行n为二叉树的结点个树，n≤100；第二行x表示要查找的结点的值；以下第一列数据是各结点的值，第二列数据是左儿子结点编号，第三列数据是右儿子结点编号。【输出】一个数即查找的结点编号。【输入样例】7【输出样例】4【源程序】

0
0
轩爸
发布于 2020-05-14 10:20
阅读 ( 932 )

信息学奥赛一本通T1366：树与二叉树二叉树输出

【题目描述】树的凹入表示法主要用于树的屏幕或打印输出，其表示的基本思想是兄弟间等长，一个结点的长度要不小于其子结点的长度。二叉树也可以这样表示，假设叶结点的长度为1，一个非叶结点的长度等于它的左右子树的长度之和。一棵二叉树的一个结点用一个字母表示（无重复），输出时从根结点开始：每行输出若干个结点字符（相同字符的个数等于该结点长度），如果该结点有左子树就递归输出左子树；如果该结点有右子树就递归输出右

0
1
轩爸
发布于 2020-05-14 10:20
阅读 ( 807 )

信息学奥赛一本通T1364：树与二叉树二叉树遍历

【题目描述】树和二叉树基本上都有先序、中序、后序、按层遍历等遍历顺序，给定中序和其它一种遍历的序列就可以确定一棵二叉树的结构。假定一棵二叉树一个结点用一个字符描述，现在给出中序和按层遍历的字符串，求该树的先序遍历字符串。【输入】两行，每行是由字母组成的字符串（一行的每个字符都是唯一的），分别表示二叉树的中序遍历和按层遍历的序列。【输出】一行，表示二叉树的先序序列。【输入样例】DBEAC【输出样例】

0
0
轩爸
发布于 2020-05-13 16:20
阅读 ( 1047 )

信息学奥赛一本通T1365：树与二叉树 FBI树

【题目描述】我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。FBI树是一种二叉树，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：T的根结点为R，其类型与串S的类型相同；若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1

0
0
轩爸
发布于 2020-05-13 16:20
阅读 ( 717 )