信息学奥赛一本通T1221：搜索与回溯算法（DFS） 分成互质组

【题目描述】给定n个正整数，将它们分组，使得每组中任意两个数互质。至少要分成多少个组？【输入】第一行是一个正整数n。1 ≤ n ≤ 10。第二行是n个不大于10000的正整数。【输出】一个正整数，即最少需要的组数。【输入样例】6【输出样例】3【源程序】 

• 0
• 1
• 轩爸
• 发布于 2020-04-29 10:20
• 阅读 ( 2250 )

信息学奥赛一本通T1220：搜索与回溯算法（DFS） 单词接龙

【题目描述】单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。【输入】输入的第一行为一个单独的整数n(

• 0
• 0
• 轩爸
• 发布于 2020-04-28 16:20
• 阅读 ( 1559 )

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

信息学奥赛一本通T1217：搜索与回溯算法（DFS） 棋盘问题

【题目描述】在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放 k 个棋子的所有可行的摆放方案 C。【输入】输入含有多组测试数据。每组数据的第一行是两个正整数n,k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 (n≤8,k≤n)当为−1 −1时表示输

• 0
• 0
• 轩爸
• 发布于 2020-04-28 16:20
• 阅读 ( 1075 )

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

信息学奥赛一本通T1216：搜索与回溯算法（DFS） 红与黑

【题目描述】有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。【输入】包括多个数据集合。每个数据集合的第一行是两个整数W和H，分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中，每行包括W个字符。每个字符表示一块瓷砖的颜色，规则如下:1）‘.’：黑色的瓷砖；2）‘#

• 0
• 1
• 轩爸
• 发布于 2020-04-28 16:20
• 阅读 ( 1256 )

信息学奥赛一本通T1215：搜索与回溯算法（DFS） 迷宫

【题目描述】一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * n的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#)，则看成无法办到。【输

• 0
• 1
• 轩爸
• 发布于 2020-04-28 10:20
• 阅读 ( 1288 )

信息学奥赛一本通T1214：搜索与回溯算法（DFS） 八皇后

【题目描述】会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 × 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。对于某个满足要求的8皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2...b8，其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。给出一个数b，要求输出第b个串。

• 0
• 1
• 轩爸
• 发布于 2020-04-28 10:20
• 阅读 ( 2195 )

信息学奥赛一本通T1213：搜索与回溯算法（DFS） 八皇后问题

【题目描述】在国际象棋棋盘上放置八个皇后，要求每两个皇后之间不能直接吃掉对方。【输入】(无)【输出】按给定顺序和格式输出所有八皇后问题的解（见样例）。【输入样例】(无)【输出样例】No. 1【源程序】 

• 0
• 1
• 轩爸
• 发布于 2020-04-28 10:20
• 阅读 ( 2163 )

信息学奥赛一本通T1212：搜索与回溯算法（DFS） LETTERS

【题目描述】给出一个roe×col的大写字母矩阵，一开始的位置为左上角，你可以向上下左右四个方向移动，并且不能移向曾经经过的字母。问最多可以经过几个字母。【输入】第一行，输入字母矩阵行数R和列数S，1≤R,S≤20。接着输出R行S列字母矩阵。【输出】最多能走过的不同字母的个数。【输入样例】3 6【输出样例】6【源程序】 

• 0
• 0
• 轩爸
• 发布于 2020-04-28 10:20
• 阅读 ( 1425 )

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

第二场NOI Online能力测试专题

探索不停止，NOI活动进行中——第二场能力测试举行（点击查看）第二场NOI Online能力测试问题反馈（点击查看）关于第二场NOI Online能力测试相关事项的通知（点击查看）关于获取第二场NOI Online能力测试准考证的说明（点击查看）CCF关于举办第二场能力测试的通知（点击查看）...

• 0
• 0
• 轩爸
• 发布于 2020-04-27 16:20
• 阅读 ( 318 )

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

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

信息学奥赛一本通T1207：递归算法 求最大公约数问题

【题目描述】给定两个正整数，求它们的最大公约数。【输入】输入一行，包含两个正整数(<1,000,000,000)。【输出】输出一个正整数，即这两个正整数的最大公约数。【输入样例】6 9【输出样例】3【源程序】

• 0
• 0
• 轩爸
• 发布于 2020-04-27 16:20
• 阅读 ( 1570 )

信息学奥赛一本通T1208：递归算法 2的幂次方表示

【题目描述】任何一个正整数都可以用2的幂次方表示。例如：137=27+23+20同时约定方次用括号来表示，即ab可表示为a(b)。由此可知，137可表示为：2(7)+2(3)+2(0)进一步：7=22+2+20（21用2表示）3=2+20所以最后137可表示为：2(2(2)+2+2(0))+2(2+2(0))+2(0)又如：1315=210+28+25+2+1所以1315最后可表示为：2(2(2+

• 0
• 2
• 轩爸
• 发布于 2020-04-27 16:20
• 阅读 ( 1886 )

信息学奥赛一本通T1206：递归算法 放苹果

【题目描述】把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
• 0
• 轩爸
• 发布于 2020-04-27 16:20
• 阅读 ( 1505 )

信息学奥赛一本通T1205：递归算法 汉诺塔问题

【题目描述】约19世纪末，在欧州的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到中间的杆上，条件是一次只能移动一个盘，且不允许大盘放在小盘的上面。【输入】输入为一个整数(小于20）后面跟三个单字符字符串。整数为盘子的数目，后三个字符表示三个杆子的编号。【输出】输出每一步移动盘子的记录。一次移动一行。每次移动的

• 0
• 2
• 轩爸
• 发布于 2020-04-27 10:20
• 阅读 ( 2163 )

信息学奥赛一本通T1204：递归算法 爬楼梯

【题目描述】树老师爬楼梯，他可以每次走1级或者2级，输入楼梯的级数，求不同的走法数。【输入】输入包含若干行，每行包含一个正整数N，代表楼梯级数，1≤N≤30。【输出】不同的走法数，每一行输入对应一行输出。【输入样例】​5【输出样例】​8【源程序】 

• 0
• 0
• 轩爸
• 发布于 2020-04-27 10:20
• 阅读 ( 1346 )

信息学奥赛一本通T1203：递归算法 扩号匹配问题

【题目描述】在某个字符串（长度不超过100）中有左括号、右括号和大小写字母；规定（与常见的算数式子一样）任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序，找到无法匹配的左括号和右括号，输出原来字符串，并在下一行标出不能匹配的括号。不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注。【输入】输入包括多组数据，每组数据一行，包含一个字符串，只包含左右括号和大小写字母，字符串

• 0
• 0
• 轩爸
• 发布于 2020-04-27 10:20
• 阅读 ( 1127 )