文章 - 第23页 - 信奥网

信息学奥赛一本通T1261：动态规划的基本模型城市交通路网

【题目描述】下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由A->E。试用动态规划的最优化原理求出A->E的最省费用。如图：求v1到v10的最短路径长度及最短路径。【输入】第一行为城市的数量N;后面是N*N的表示两个城市间费用组成的矩阵。【输出】A->E的最省费用。【输入样例】10【输出样例】minlong=19【源程序】

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

【题目描述】某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少

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

信息学奥赛一本通T1259：动态规划的基本模型求最长不下降序列

【题目描述】设有由n(1≤n≤200)个不相同的整数组成的数列，记为:b(1)、b(2)、……、b(n)且b(i)≠b(j)(i≠j)，若存在i1<i2<i3<…<ie 且有b(i1)<b(i2)<…<b(ie)则称为长度为e的不下降序列。程序要求，当原数列出之后，求出最长的不下降序列。例如13，7，9，16，38，24，37，18，44，19，21，22

0
4
轩爸
发布于 2020-05-02 16:20
阅读 ( 1627 )

信息学奥赛一本通T1258：动态规划的基本模型数字金字塔

【题目描述】观察下面的数字金字塔。写一个程序查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以从当前点走到左下方的点也可以到达右下方的点。在上面的样例中,从13到8到26到15到24的路径产生了最大的和86。【输入】第一个行包含R(1≤ R≤1000)，表示行的数目。后面每行为这个数字金字塔特定行包含的整数。所有的被供应的整数是非负的且不大于100。【输出】单独的一行，包含那个

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

信息学奥赛一本通T1257：广度优先搜索（BFS） Knight Moves

【题目描述】输入n代表有个n×n的棋盘，输入开始位置的坐标和结束位置的坐标，问一个骑士朝棋盘的八个方向走马字步，从开始坐标到结束坐标可以经过多少步。【输入】首先输入一个n,表示测试样例的个数。每个测试样例有三行。第一行是棋盘的大小L(4≤L≤300)；第二行和第三行分别表示马的起始位置和目标位置(0..L−1)。【输出】马移动的最小步数，起始位置和目标位置相同时输出0。【输入样例】3【输出样例】5

0
1
轩爸
发布于 2020-05-02 16:20
阅读 ( 1184 )

信息学奥赛一本通T1256：广度优先搜索（BFS）献给阿尔吉侬的花束

【题目描述】阿尔吉侬是一只聪明又慵懒的小白鼠，它最擅长的就是走各种各样的迷宫。今天它要挑战一个非常大的迷宫，研究员们为了鼓励阿尔吉侬尽快到达终点，就在终点放了一块阿尔吉侬最喜欢的奶酪。现在研究员们想知道，如果阿尔吉侬足够聪明，它最少需要多少时间就能吃到奶酪。迷宫用一个R×C的字符矩阵来表示。字符S表示阿尔吉侬所在的位置，字符E表示奶酪所在的位置，字符#表示墙壁，字符.表示可以通行。阿尔吉侬在1个单

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

信息学奥赛一本通T1255：广度优先搜索（BFS）迷宫问题

【题目描述】定义一个二维数组：int maze[5][5] = {0,1,0,0,0,0,1,0,1,0,0,0,0,0,0,0,1,1,1,0,0,0,0,1,0,};【输入】一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。【输出】左上角到右下角的最短路径，格式如样例所示。【输入样例】0 1 0 0 0【输出样例】(0, 0)【源程序】

0
2
轩爸
发布于 2020-05-02 10:20
阅读 ( 1066 )

信息学奥赛一本通T1254：广度优先搜索（BFS）走出迷宫

【题目描述】当你站在一个迷宫里的时候，往往会被错综复杂的道路弄得失去方向感，如果你能得到迷宫地图，事情就会变得非常简单。假设你已经得到了一个n*m的迷宫的图纸，请你找出从起点到出口的最短路。【输入】第一行是两个整数n和m(1≤n,m≤100)，表示迷宫的行数和列数。接下来n行，每行一个长为m的字符串，表示整个迷宫的布局。字符‘.’表示空地，‘#’表示墙，‘S’表示起点,‘T’表示出口。【输出】输出

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

信息学奥赛一本通T1253：广度优先搜索（BFS）抓住那头牛

【题目描述】农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0≤N≤100000)，牛位于点K(0≤K≤100000)。农夫有两种移动方式：1、从X移动到X-1或X+1，每次移动花费一分钟2、从X移动到2*X，每次移动花费一分钟假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？【输入】两个整数，N和K。【输出】一个整数，农夫抓到牛所要花费的最小分钟

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

信息学奥赛一本通T1252：广度优先搜索（BFS）走迷宫

【题目描述】一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。【输入】第一行是两个整数，Ｒ和Ｃ，代表迷宫的长和宽。（ 1≤ R，C ≤ 40)接下来是Ｒ行，每行Ｃ个字符，代表整个迷宫。空地格子用‘.’表示，有障碍物的格子用‘#’表示。迷宫左上角和右下角都是

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

信息学奥赛一本通T1251：广度优先搜索（BFS）仙岛求药

【题目描述】少年李逍遥的婶婶病了，王小虎介绍他去一趟仙灵岛，向仙女姐姐要仙丹救婶婶。叛逆但孝顺的李逍遥闯进了仙灵岛，克服了千险万难来到岛的中心，发现仙药摆在了迷阵的深处。迷阵由M×N个方格组成，有的方格内有可以瞬秒李逍遥的怪物，而有的方格内则是安全。现在李逍遥想尽快找到仙药，显然他应避开有怪物的方格，并经过最少的方格，而且那里会有神秘人物等待着他。现在要求你来帮助他实现这个目标。下图显示了一个迷

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

信息学奥赛一本通T1250：广度优先搜索（BFS） The Castle

【题目描述】一座城堡被分成ｍ*ｎ个方块（m≤50，n≤50），每个方块可有0～4堵墙（0表示无墙）。下面示出了建筑平面图：图中的加粗黑线代表墙。几个连通的方块组成房间，房间与房间之间一定是用黑线（墙）隔开的。现在要求你编一个程序，解决以下2个问题： 1、该城堡中有多少个房间? 2、最大的房间有多大?【输入】平面图用一个数字表示一个方块(第1个房间用二进制1011表示，0表示无东墙，用十

0
1
轩爸
发布于 2020-05-01 16:20
阅读 ( 1011 )

信息学奥赛一本通T1249：广度优先搜索（BFS） Lake Counting

【题目描述】有一块N×M的土地，雨后积起了水，有水标记为‘W’，干燥为‘.’。八连通的积水被认为是连接在一起的。请求出院子里共有多少水洼？【输入】第一行为N,M(1≤N,M≤110)。下面为N*M的土地示意图。【输出】一行，共有的水洼数。【输入样例】10 12【输出样例】3【源程序】

0
1
轩爸
发布于 2020-05-01 16:20
阅读 ( 1322 )

信息学奥赛一本通T1248：广度优先搜索（BFS） Dungeon Master

【题目描述】这题是一个三维的迷宫题目，其中用‘.’表示空地，‘#’表示障碍物，‘S’表示起点，‘E’表示终点，求从起点到终点的最小移动次数，解法和二维的类似，只是在行动时除了东南西北移动外还多了上下。可以上下左右前后移动，每次都只能移到相邻的空位，每次需要花费一分钟，求从起点到终点最少要多久。【输入】多组测试数据。一组测试测试数据表示一个三维迷宫：前三个数，分别表示层数、一个面的长和宽，后面是每层

0
2
轩爸
发布于 2020-05-01 16:20
阅读 ( 1164 )

信息学奥赛一本通T1247：分治算法河中跳房子

【题目描述】每年奶牛们都要举办各种特殊版本的跳房子比赛，包括在河里从一个岩石跳到另一个岩石。这项激动人心的活动在一条长长的笔直河道中进行，在起点和离起点L远 (1 ≤ L≤ 1,000,000,000) 的终点处均有一个岩石。在起点和终点之间，有N (0 ≤ N ≤ 50,000) 个岩石，每个岩石与起点的距离分别为Di (0 < Di < L)。在比赛过程中，奶牛轮流从起点出发，尝试

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

信息学奥赛一本通T1246：分治算法膨胀的木棍

【题目描述】当长度为L的一根细木棍的温度升高n度，它会膨胀到新的长度L’=(1+n*C)*L，其中C是热膨胀系数。当一根细木棍被嵌在两堵墙之间被加热，它将膨胀形成弓形的弧，而这个弓形的弦恰好是未加热前木棍的原始位置。你的任务是计算木棍中心的偏移距离。【输入】三个非负实数：木棍初始长度（单位：毫米），温度变化（单位：度），以及材料的热膨胀系数。保证木棍不会膨胀到超过原始长度的1.5倍。【输出】木棍中

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

信息学奥赛一本通T1244：分治算法和为给定数

【题目描述】给出若干个整数，询问其中是否有一对数的和等于给定的数。【输入】第一行是整数n(0 < n ≤ 100,000)，表示有n个整数。第二行是n个整数。整数的范围是在0到108之间。第三行是一个整数m（0≤m≤230)，表示需要得到的和。【输出】若存在和为m的数对，输出两个整数，小的在前，大的在后，中间用单个空格隔开。若有多个数对满足条件，选择数对中较小的数更小的。若找不到符合要求的数

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

信息学奥赛一本通T1245：分治算法不重复地输出数

【题目描述】输入n个数，从小到大将它们输出，重复的数只输出一次。保证不同的数不超过500个。【输入】第一行是一个整数n。1 ≤ n ≤ 100000。之后n行，每行一个整数。整数大小在int范围内。【输出】一行，从小到大不重复地输出这些数，相邻两个数之间用单个空格隔开。【输入样例】5【输出样例】1 2 4 5【源程序】

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

信息学奥赛一本通T1243：分治算法月度开销

【题目描述】农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要的开销。约翰打算为连续的M (1 ≤ M ≤ N) 个财政周期创建预算案，他把一个财政周期命名为fajo月。每个fajo月包含一天或连续的多天，每天被恰好包含在一个fajo月里。约翰的目标是合理安排每个fajo月包含的天数，使得开销最

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

信息学奥赛一本通T1242：分治算法网线主管

【题目描述】仙境的居民们决定举办一场程序设计区域赛。裁判委员会完全由自愿组成，他们承诺要组织一次史上最公正的比赛。他们决定将选手的电脑用星形拓扑结构连接在一起，即将它们全部连到一个单一的中心服务器。为了组织这个完全公正的比赛，裁判委员会主席提出要将所有选手的电脑等距离地围绕在服务器周围放置。为购买网线，裁判委员会联系了当地的一个网络解决方案提供商，要求能够提供一定数量的等长网线。裁判委员会希望网线

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