信息学奥赛一本通T1226：贪心算法 装箱问题
【题目描述】一个工厂制造的产品形状都是长方体，它们的高度都是h，长和宽都相等，一共有六个型号，他们的长宽分别为1*1,2*2,3*3,4*4,5*5,6*6。这些产品通常使用一个6*6*h的长方体包裹包装然后邮寄给客户。因为邮费很贵，所以工厂要想方设法的减小每个订单运送时的包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省费用。现在这个程序由你来设计。【输入】输入文件包括几行，每一行代表
- 0
- 0
- 轩爸
- 发布于 2020-04-29 16:20
- 阅读 ( 888 )
轩爸
信息学奥赛一本通T1227：贪心算法 Ride to Office
【题目描述】起点与终点相隔4500米。现Charley 需要从起点骑车到终点。但是，他有个习惯，沿途需要有人陪伴，即以相同的速度， 与另外一个人一起骑。而当他遇到以更快的速度骑车的人时，他会以相应的速度跟上这个更快的人。先给定所有与Charley 同路的人各自的速度与出发时间，问Charley 以这种方式跟人，骑完4500米需要多少时间。得出的结果若是小数，则向上取整。【输入】输入若干组数据，每组
- 0
- 0
- 轩爸
- 发布于 2020-04-29 16:20
- 阅读 ( 648 )
信息学奥赛一本通T1225：贪心算法 金银岛
【题目描述】某天KID利用飞行器飞到了一个金银岛上，上面有许多珍贵的金属，KID虽然更喜欢各种宝石的艺术品，可是也不拒绝这样珍贵的金属。但是他只带着一个口袋，口袋至多只能装重量为w的物品。岛上金属有s个种类, 每种金属重量不同，分别为n1,n2,...,ns，同时每个种类的金属总的价值也不同，分别为v1,v2,...,vs。KID想一次带走价值尽可能多的金属，问他最多能带走价值多少的金属。注意到金
- 0
- 0
- 轩爸
- 发布于 2020-04-29 10:20
- 阅读 ( 1034 )
信息学奥赛一本通T1224：贪心算法 最大子矩阵
【题目描述】已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1×11×1)子矩阵。比如，如下4×4的矩阵 0 -2 -7 0 9 2 -6 2 -4 1 -4 1-1 8 0 -2的最大子矩阵是 9 2-4 1-1 8这个子矩阵的大小是15。【输入】输入是一个N×N的矩阵。输入的第一行给出
- 0
- 0
- 轩爸
- 发布于 2020-04-29 10:20
- 阅读 ( 998 )
信息学奥赛一本通T1223：贪心算法 An Easy Problem
【题目描述】给定一个正整数N，求最小的、比N大的正整数M，使得M与N的二进制表示中有相同数目的1。举个例子，假如给定的N为78，其二进制表示为1001110，包含4个1，那么最小的比N大的并且二进制表示中只包含4个1的数是83，其二进制是1010011，因此83就是答案。【输入】输入若干行，每行一个数n(1≤n≤1000000)，输入"0"结束。【输出】输出若干行对应的值。【输入样例】1【输出样例
- 0
- 0
- 轩爸
- 发布于 2020-04-29 10:20
- 阅读 ( 929 )
信息学奥赛一本通T1222：搜索与回溯算法（DFS） 放苹果
【题目描述】把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。【输入】第一行是测试数据的数目t（0 ≤ t ≤ 20）。以下每行均包含二个整数M和N，以空格分开。1≤M，N≤10。【输出】对输入的每组数据M和N，用一行输出相应的K。【输入样例】1【输出样例】8【源程序】
- 0
- 1
- 轩爸
- 发布于 2020-04-29 10:20
- 阅读 ( 1044 )
信息学奥赛一本通T1221：搜索与回溯算法（DFS） 分成互质组
【题目描述】给定n个正整数，将它们分组，使得每组中任意两个数互质。至少要分成多少个组？【输入】第一行是一个正整数n。1 ≤ n ≤ 10。第二行是n个不大于10000的正整数。【输出】一个正整数，即最少需要的组数。【输入样例】6【输出样例】3【源程序】
- 0
- 1
- 轩爸
- 发布于 2020-04-29 10:20
- 阅读 ( 1780 )
信息学奥赛一本通T1220：搜索与回溯算法（DFS） 单词接龙
【题目描述】单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。【输入】输入的第一行为一个单独的整数n(
- 0
- 0
- 轩爸
- 发布于 2020-04-28 16:20
- 阅读 ( 1302 )
信息学奥赛一本通T1219：搜索与回溯算法（DFS） 马走日
【题目描述】马在中国象棋以日字形规则移动。请编写一段程序，给定n×m大小的棋盘，以及马的初始位置(x，y)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。【输入】第一行为整数T(T < 10)，表示测试数据组数。每一组测试数据包含一行，为四个整数，分别为棋盘的大小以及初始位置坐标n,m,x,y。(0≤x≤n-1,0≤y≤m-1, m < 10, n <
- 0
- 1
- 轩爸
- 发布于 2020-04-28 16:20
- 阅读 ( 1134 )
信息学奥赛一本通T1217：搜索与回溯算法（DFS） 棋盘问题
【题目描述】在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放 k 个棋子的所有可行的摆放方案 C。【输入】输入含有多组测试数据。每组数据的第一行是两个正整数n,k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 (n≤8,k≤n)当为−1 −1时表示输
- 0
- 0
- 轩爸
- 发布于 2020-04-28 16:20
- 阅读 ( 777 )
信息学奥赛一本通T1218：搜索与回溯算法（DFS） 取石子游戏
【题目描述】有两堆石子,两个人轮流去取。每次取的时候,只能从较多的那堆石子里取,并且取的数目必须是较少的那堆石子数目的整数倍，最后谁能够把一堆石子取空谁就算赢。比如初始的时候两堆石子的数目是25和7。25 7 --> 11 7 --> 4 7 --> 4 3 --> 1 3 --> 1 0最后选手1（先取的）获胜，在取的过程中选手2都只有唯一的一种取法。给定初始时石子
- 0
- 0
- 轩爸
- 发布于 2020-04-28 16:20
- 阅读 ( 789 )
信息学奥赛一本通T1216：搜索与回溯算法（DFS） 红与黑
【题目描述】有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。【输入】包括多个数据集合。每个数据集合的第一行是两个整数W和H，分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中，每行包括W个字符。每个字符表示一块瓷砖的颜色，规则如下:1）‘.’：黑色的瓷砖；2）‘#
- 0
- 1
- 轩爸
- 发布于 2020-04-28 16:20
- 阅读 ( 1014 )
信息学奥赛一本通T1215：搜索与回溯算法（DFS） 迷宫
【题目描述】一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * n的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#)，则看成无法办到。【输
- 0
- 1
- 轩爸
- 发布于 2020-04-28 10:20
- 阅读 ( 985 )
信息学奥赛一本通T1214：搜索与回溯算法（DFS） 八皇后
【题目描述】会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 × 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2...b8，其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。给出一个数b，要求输出第b个串。
- 0
- 1
- 轩爸
- 发布于 2020-04-28 10:20
- 阅读 ( 1855 )
信息学奥赛一本通T1213：搜索与回溯算法（DFS） 八皇后问题
【题目描述】在国际象棋棋盘上放置八个皇后，要求每两个皇后之间不能直接吃掉对方。【输入】(无)【输出】按给定顺序和格式输出所有八皇后问题的解（见样例）。【输入样例】(无)【输出样例】No. 1【源程序】
- 0
- 1
- 轩爸
- 发布于 2020-04-28 10:20
- 阅读 ( 1625 )
信息学奥赛一本通T1212：搜索与回溯算法（DFS） LETTERS
【题目描述】给出一个roe×col的大写字母矩阵，一开始的位置为左上角，你可以向上下左右四个方向移动，并且不能移向曾经经过的字母。问最多可以经过几个字母。【输入】第一行，输入字母矩阵行数R和列数S，1≤R,S≤20。接着输出R行S列字母矩阵。【输出】最多能走过的不同字母的个数。【输入样例】3 6【输出样例】6【源程序】
- 0
- 0
- 轩爸
- 发布于 2020-04-28 10:20
- 阅读 ( 1261 )
信息学奥赛一本通T1211：递归算法 判断元素是否存在
【题目描述】有一个集合M是这样生成的：(1) 已知k是集合M的元素； (2) 如果y是M的元素，那么，2y+1和3y+1都是M的元素；(3) 除了上述二种情况外，没有别的数能够成为M的一个元素。【输入】输入整数 k 和 x, 逗号间隔。【输出】如果是，则输出 YES，否则，输出NO。【输入样例】0,22【输出样例】YES【源程序】
- 0
- 2
- 轩爸
- 发布于 2020-04-28 10:20
- 阅读 ( 1931 )
信息学奥赛一本通T1210：递归算法 因子分解
【题目描述】输入一个数，输出其素因子分解表达式。【输入】输入一个整数 n (2≤n<100)。【输出】输出该整数的因子分解表达式。表达式中各个素数从小到大排列。如果该整数可以分解出因子a的b次方，当b大于1时，写做 a^b ；当b等于1时，则直接写成a。【输入样例】60【输出样例】2^2*3*5【源程序】
- 0
- 0
- 轩爸
- 发布于 2020-04-27 16:20
- 阅读 ( 993 )
信息学奥赛一本通T1209：递归算法 分数求和
【题目描述】输入n个分数并对他们求和，并用最简形式表示。所谓最简形式是指：分子分母的最大公约数为1/1；若最终结果的分母为1，则直接用整数表示。【输入】第一行是一个整数n，表示分数个数，1≤n≤10；接下来n行，每行一个分数，用"p/q"的形式表示，不含空格，p，q均不超过10。【输出】输出只有一行，即最终结果的最简形式。若为分数，用"p/q"的形式表示。【输入样例】2【输出样例】5/6【源程序】
- 0
- 2
- 轩爸
- 发布于 2020-04-27 16:20
- 阅读 ( 1869 )
信息学奥赛一本通T1207：递归算法 求最大公约数问题
【题目描述】给定两个正整数，求它们的最大公约数。【输入】输入一行，包含两个正整数(<1,000,000,000)。【输出】输出一个正整数，即这两个正整数的最大公约数。【输入样例】6 9【输出样例】3【源程序】
- 0
- 0
- 轩爸
- 发布于 2020-04-27 16:20
- 阅读 ( 1169 )
