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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

信息学奥赛一本通T1298：动态规划经典问题 计算字符串距离

【题目描述】对于两个不同的字符串，我们有一套操作方法来把他们变得相同，具体方法为：        修改一个字符（如把“a”替换为“b”）;    删除一个字符（如把“traveling”变为“travelng”）。比如对于“abcdefg”和“abcdef”两个字符串来说，我们认为可以通过增加/减少一个“g”的方式来达到目的。无论增加还是减少“g”，我们都仅仅需要一次操作。我们把这个操作所需要的次

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

信息学奥赛一本通T1296：背包问题 开餐馆

【题目描述】信息学院的同学小明毕业之后打算创业开餐馆.现在共有n个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这 n个地点排列在同一条直线上。我们用一个整数序列m1,m2,...mn来表示他们的相对位置。由于地段关系,开餐馆的利润会有所不同。我们用pi 表示在mi处开餐馆的利润。为了避免自己的餐馆的内部竞争,餐馆之间的距离必须大于k。请你帮助小明选择一个总利润最大的方案。【输入】输入第一

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

信息学奥赛一本通T1295：背包问题 装箱问题

【题目描述】有一个箱子容量为V（正整数，0≤v≤20000），同时有n个物品（0< n ≤30），每个物品有一个体积（正整数）。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。【输入】第一行是一个整数V，表示箱子容量。第二行是一个整数n，表示物品数。接下来n行，每行一个正整数（不超过10000），分别表示这n个物品的各自体积。【输出】一个整数，表示箱子剩余空间。【输入样例】24【

• 0
• 0
• 轩爸
• 发布于 2020-05-06 10:20
• 阅读 ( 1319 )