文章 - 第20页 - 信奥网

信息学奥赛一本通T1317：搜索与回溯算法（DFS）组合的输出

【题目描述】排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r≤n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。现要求你用递归的方法输出所有组合。例如n＝5，r＝3，所有组合为：1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5【输入】一行两

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

信息学奥赛一本通T1316：递归算法数的计数

【题目描述】我们要求找出具有下列性质数的个数（包括输入的自然数n）。先输入一个自然数n（n≤1000），然后对此自然数按照如下方法进行处理：不作任何处理；在它的左边加上一个自然数，但该自然数不能超过原数的一半；加上数后，继续按此规则进行处理，直到不能再加自然数为止。【输入】自然数n（n≤1000）。【输出】满足条件的数。【输入样例】6【输出样例】6提示：满足条件的数为 6、16、26、12

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

【题目描述】设S是一个具有n个元素的集合，S＝⟨a1，a2，……，an⟩，现将S划分成k个满足下列条件的子集合S1，S2，……，Sk且满足：则称S1，S2，……，Sk是集合S的一个划分。它相当于把S集合中的n个元素a1，a2，……，an放入k个(0＜k≤n＜30)无标号的盒子中，使得没有一个盒子为空。请你确定n个元素a1，a2，……，an放入k个无标号盒子中去的划分数S(n,k)。【输入】给出n和

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

信息学奥赛一本通T1314：递推算法过河卒

【题目描述】棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上的某一点有一个对方的马（如C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点，如图3-1中的C点和P1，……，P8，卒不能通过对方马的控制点。棋盘用坐标表示，A点(0,0)、B点(n, m) (n,m为不超过20的整数),同样马的位置坐标是需要给出的，C≠A且C≠B。现在要求你计算出卒从A

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

信息学奥赛一本通T1313：递推算法位数问题

【题目描述】在所有的N位数中，有多少个数中有偶数个数字3?由于结果可能很大，你只需要输出这个答案对12345取余的值。【输入】输入包含一行，一个字符串，长度不超过1000。读入一个数N。【输出】输出有多少个数中有偶数个数字3。【输入样例】2【输出样例】73【源程序】

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

信息学奥赛一本通T1312：递推算法昆虫繁殖

【题目描述】科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过x个月产y对卵，每对卵要过两个月长成成虫。假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵(过X个月产卵)，问过Z个月以后，共有成虫多少对？0≤X≤20,1≤Y≤20,X≤Z≤50。【输入】x,y,z的数值。【输出】过Z个月以后，共有成虫对数。【输入样例】1 2 8【输出样例】37【源程序】

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

信息学奥赛一本通T1311：数据排序求逆序对

【题目描述】给定一个序列a1,a2,…,an，如果存在i<j并且ai>aj，那么我们称之为逆序对，求逆序对的数目。【输入】第一行为n,表示序列长度，接下来的n行，第i+1行表示序列中的第i个数。【输出】所有逆序对总数。【输入样例】4【输出样例】3【源程序】

0
3
轩爸
发布于 2020-05-08 16:20
阅读 ( 2617 )

信息学奥赛一本通T1310：数据排序车厢重组

【题目描述】在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转180度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢按车厢号从小到大排列。他退休后，火车站决定将这一工作自动化，其中一项重要的工作是编一个程序，输入初始的车厢顺序，计算最少用多少步就能将车厢排序。【输入】有两

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

信息学奥赛一本通T1309：高精度计算回文数

【题目描述】若一个数（首位不为零）从左向右读与从右向左读都是一样，我们就将其称之为回文数。例如：给定一个 10进制数 56，将 56加 65（即把56从右向左读），得到 121是一个回文数。又如，对于10进制数87：STEP1： 87＋78= 165 STEP2： 165＋561= 726STEP3： 726＋627＝1353STEP4：1353+3531=4884在这里的一步是指进行了一次N进制

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

信息学奥赛一本通T1307：高精度计算高精度乘法

【题目描述】输入两个高精度正整数M和N（M和N均小于100位）。求这两个高精度数的积。【输入】输入两个高精度正整数M和N。【输出】求这两个高精度数的积。【输入样例】36【输出样例】108【源程序】

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

信息学奥赛一本通T1308：高精度计算高精除

【题目描述】高精除以高精，求它们的商和余数。【输入】输入两个低于300位的正整数。【输出】输出商和余数。【输入样例】1231312318457577687897987642324567864324567876543245671425346756786867867867【输出样例】999999999748590【源程序】

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

信息学奥赛一本通T1306：动态规划经典问题最长公共子上升序列

【题目描述】给定两个整数序列，写一个程序求它们的最长上升公共子序列。当以下条件满足的时候，我们将长度N的序列S1,S2,...,SN 称为长度为M的序列A1,A2,...,AM的上升子序列：存在1≤i1<i2<...<iN≤M，使得对所有1≤j≤N，均有Sj=Aij，且对于所有的1≤j<N，均有Sj<Sj+1。【输入】每个序列用两行表示，第一行是长度M(1≤M≤500

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

信息学奥赛一本通T1305：动态规划经典问题 Maximum sum

【题目描述】对于给定的整数序列A={a1,a2,...,an}，找出两个不重合连续子段，使得两子段中所有数字的和最大。我们如下定义函数 d(A)：我们的目标就是求出d(A)。【输入】第一行是一个整数T(≤30)，代表一共有多少组数据。接下来是T组数据。每组数据的第一行是一个整数，代表数据个数据n(2≤n≤50000) ,第二行是nn个整数a1,a2,...,an(|ai|≤10000)。【输出】输

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

信息学奥赛一本通T1304：动态规划经典问题数的划分

【题目描述】将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。例如：n=7，k=3，下面三种分法被认为是相同的。1，1，5； 1，5，1； 5，1，1；问有多少种不同的分法。输出一个整数，即不同的分法。【输入】两个整数n，k(6<n≤200，2≤k≤6)，中间用单个空格隔开。【输出】一个整数，即不同的分法。【输入样例】7 3【输出样例】4【源程序】

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

信息学奥赛一本通T1303：动态规划经典问题鸣人的影分身

【题目描述】在火影忍者的世界里，令敌人捉摸不透是非常关键的。我们的主角漩涡鸣人所拥有的一个招数——多重影分身之术——就是一个很好的例子。影分身是由鸣人身体的查克拉能量制造的，使用的查克拉越多，制造出的影分身越强。针对不同的作战情况，鸣人可以选择制造出各种强度的影分身，有的用来佯攻，有的用来发起致命一击。那么问题来了，假设鸣人的查克拉能量为M，他影分身的个数最多为N，那么制造影分身时有多少种（用K表

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

信息学奥赛一本通T1301：动态规划经典问题大盗阿福

【题目描述】阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。这条街上一共有 N 家店铺，每家店中都有一些现金。阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？【输入】输入的第一行是一个整数T(T≤50)

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

信息学奥赛一本通T1302：动态规划经典问题股票买卖

【题目描述】最近越来越多的人都投身股市，阿福也有点心动了。谨记着“股市有风险，入市需谨慎”，阿福决定先来研究一下简化版的股票买卖问题。假设阿福已经准确预测出了某只股票在未来N天的价格，他希望买卖两次，使得获得的利润最高。为了计算简单起见，利润的计算方式为卖出的价格减去买入的价格。同一天可以进行多次买卖。但是在第一次买入之后，必须要先卖出，然后才可以第二次买入。现在，阿福想知道他最多可以获得多少利润

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

信息学奥赛一本通T1300：动态规划经典问题鸡蛋的硬度

【题目描述】最近XX公司举办了一个奇怪的比赛：鸡蛋硬度之王争霸赛。参赛者是来自世界各地的母鸡，比赛的内容是看谁下的蛋最硬，更奇怪的是XX公司并不使用什么精密仪器来测量蛋的硬度，他们采用了一种最老土的办法--从高度扔鸡蛋--来测试鸡蛋的硬度，如果一次母鸡下的蛋从高楼的第a层摔下来没摔破，但是从a+1层摔下来时摔破了，那么就说这只母鸡的鸡蛋的硬度是a。你当然可以找出各种理由说明这种方法不科学，比如同一

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

信息学奥赛一本通T1299：动态规划经典问题糖果

【题目描述】由于在维护世界和平的事务中做出巨大贡献，Dzx被赠予糖果公司2010年5月23日当天无限量糖果免费优惠券。在这一天，Dzx可以从糖果公司的N件产品中任意选择若干件带回家享用。糖果公司的N件产品每件都包含数量不同的糖果。Dzx希望他选择的产品包含的糖果总数是K的整数倍，这样他才能平均地将糖果分给帮助他维护世界和平的伙伴们。当然，在满足这一条件的基础上，糖果总数越多越好。Dzx最多能带走多

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

信息学奥赛一本通T1297：动态规划经典问题公共子序列

【题目描述】我们称序列Z=<z1,z2,...,zk>是序列X=<x1,x2,...,xm>的子序列当且仅当存在严格上升的序列<i1,i2,...,ik>，使得对j=1,2,...,k,有xij=zj。比如Z=<a,b,f,c> 是X=<a,b,c,f,b,c>的子序列。现在给出两个序列X和Y，你的任务是找到X和Y的最大公共子序列，也就是

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