文章 - 第19页 - 信奥网

信息学奥赛一本通T1325：分治算法循环比赛日程表

【题目描述】设有N个选手进行循环比赛，其中N=2M，要求每名选手要与其他N-1名选手都赛一次，每名选手每天比赛一次，循环赛共进行N-1天，要求每天没有选手轮空。【输入】输入：M。【输出】输出：表格形式的比赛安排表。一行各数据间用一个空格隔开。【输入样例】3【输出样例】1 2 3 4 5 6 7 8【源程序】

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

【题目描述】请编程完成以下任务：1.从文件中读取闭区间的个数及它们的描述；2.找到一个含元素个数最少的集合,使得对于每一个区间,都至少有一个整数属于该集合，输出该集合的元素个数。【输入】首行包括区间的数目n,1≤n≤10000,接下来的n行,每行包括两个整数a,b,被一空格隔开,0≤a≤b≤10000,它们是某一个区间的开始值和结束值。【输出】第一行集合元素的个数,对于每一个区间都至少有一个整数属

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

信息学奥赛一本通T1323：贪心算法活动选择

【题目描述】学校在最近几天有n个活动，这些活动都需要使用学校的大礼堂，在同一时间，礼堂只能被一个活动使用。由于有些活动时间上有冲突，学校办公室人员只好让一些活动放弃使用礼堂而使用其他教室。【输入】第一行一个整数n(n≤1000)；接下来的n行，每行两个整数，第一个begini，第二个是endi(begini<endi≤32767)。【输出】输出最多能安排的活动个数。【输入样例】11【输出样例

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

信息学奥赛一本通T1322：贪心算法拦截导弹问题

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

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

信息学奥赛一本通T1321：贪心算法删数问题

【题目描述】输入一个高精度的正整数n，去掉其中任意s个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的n和s，寻找一种方案使得剩下的数字组成的新数最小。输出新的正整数。（n不超过240位）输入数据均不需判错。【输入】n 和 s【输出】一个正整数，即最少需要的组数。【输入样例】175438【输出样例】13【源程序】

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

信息学奥赛一本通T1320：贪心算法均分纸牌

【题目描述】有n堆纸牌，编号分别为 1，2，…, n。每堆上有若干张，但纸牌总数必为n的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为1的堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 n 的堆上取的纸牌，只能移到编号为n-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如 n=4，4堆纸牌数分别为

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

信息学奥赛一本通T1318：搜索与回溯算法（DFS）自然数的拆分

【题目描述】任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。当n=7共14种拆分方法：7=1+1+1+1+1+1+1【输入】输入n。【输出】按字典序输出具体的方案。【输入样例】7【输出样例】7=1+1+1+1+1+1+1【源程序】

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

信息学奥赛一本通T1319：贪心算法排队接水

【题目描述】有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。【输入】共两行，第一行为n(1≤n≤1000)；第二行分别表示第1个人到第n个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。【输出】有两行，第一行为一种排队顺序，即1到n的一种排列；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)

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

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

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

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

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

信息学奥赛一本通T1315：递归算法集合的划分

【题目描述】设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
阅读 ( 1247 )

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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