文章 - 第11页 - 信奥网

信息学奥赛一本通T1247：分治算法河中跳房子

【题目描述】每年奶牛们都要举办各种特殊版本的跳房子比赛，包括在河里从一个岩石跳到另一个岩石。这项激动人心的活动在一条长长的笔直河道中进行，在起点和离起点L远 (1 ≤ L≤ 1,000,000,000) 的终点处均有一个岩石。在起点和终点之间，有N (0 ≤ N ≤ 50,000) 个岩石，每个岩石与起点的距离分别为Di (0 < Di < L)。在比赛过程中，奶牛轮流从起点出发，尝试

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

【题目描述】当长度为L的一根细木棍的温度升高n度，它会膨胀到新的长度L’=(1+n*C)*L，其中C是热膨胀系数。当一根细木棍被嵌在两堵墙之间被加热，它将膨胀形成弓形的弧，而这个弓形的弦恰好是未加热前木棍的原始位置。你的任务是计算木棍中心的偏移距离。【输入】三个非负实数：木棍初始长度（单位：毫米），温度变化（单位：度），以及材料的热膨胀系数。保证木棍不会膨胀到超过原始长度的1.5倍。【输出】木棍中

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

信息学奥赛一本通T1244：分治算法和为给定数

【题目描述】给出若干个整数，询问其中是否有一对数的和等于给定的数。【输入】第一行是整数n(0 < n ≤ 100,000)，表示有n个整数。第二行是n个整数。整数的范围是在0到108之间。第三行是一个整数m（0≤m≤230)，表示需要得到的和。【输出】若存在和为m的数对，输出两个整数，小的在前，大的在后，中间用单个空格隔开。若有多个数对满足条件，选择数对中较小的数更小的。若找不到符合要求的数

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

信息学奥赛一本通T1245：分治算法不重复地输出数

【题目描述】输入n个数，从小到大将它们输出，重复的数只输出一次。保证不同的数不超过500个。【输入】第一行是一个整数n。1 ≤ n ≤ 100000。之后n行，每行一个整数。整数大小在int范围内。【输出】一行，从小到大不重复地输出这些数，相邻两个数之间用单个空格隔开。【输入样例】5【输出样例】1 2 4 5【源程序】

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

信息学奥赛一本通T1243：分治算法月度开销

【题目描述】农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要的开销。约翰打算为连续的M (1 ≤ M ≤ N) 个财政周期创建预算案，他把一个财政周期命名为fajo月。每个fajo月包含一天或连续的多天，每天被恰好包含在一个fajo月里。约翰的目标是合理安排每个fajo月包含的天数，使得开销最

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

信息学奥赛一本通T1242：分治算法网线主管

【题目描述】仙境的居民们决定举办一场程序设计区域赛。裁判委员会完全由自愿组成，他们承诺要组织一次史上最公正的比赛。他们决定将选手的电脑用星形拓扑结构连接在一起，即将它们全部连到一个单一的中心服务器。为了组织这个完全公正的比赛，裁判委员会主席提出要将所有选手的电脑等距离地围绕在服务器周围放置。为购买网线，裁判委员会联系了当地的一个网络解决方案提供商，要求能够提供一定数量的等长网线。裁判委员会希望网线

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

信息学奥赛一本通T1241：分治算法二分法求函数的零点

【题目描述】有函数：f(x)=x^5−15x^4+85x^3−225x^2+274^x−121已知f(1.5)>0 ,f(2.4)<0 且方程f(x)=0 在区间[1.5,2.4] 有且只有一个根，请用二分法求出该根。【输入】(无)【输出】该方程在区间[1.5,2.4]中的根。要求四舍五入到小数点后6位。【输入样例】(无)【输出样例】(无)【源程序】

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

信息学奥赛一本通T1240：分治算法查找最接近的元素

【题目描述】在一个非降序列中，查找与给定值最接近的元素。【输入】第一行包含一个整数n，为非降序列长度。1 ≤ n ≤ 100000。第二行包含n个整数，为非降序列各元素。所有元素的大小均在0-1,000,000,000之间。第三行包含一个整数m，为要询问的给定值个数。1 ≤ m ≤ 10000。接下来m行，每行一个整数，为要询问最接近元素的给定值。所有给定值的大小均在0-1,000,000,000

0
0
轩爸
发布于 2020-04-30 16:20
阅读 ( 2128 )

信息学奥赛一本通T1239：分治算法统计数字

【题目描述】某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5∗10^9）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。【输入】第一行是整数 n，表示自然数的个数；第2~n+1每行一个自然数。【输出】包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该

0
1
轩爸
发布于 2020-04-30 16:20
阅读 ( 1324 )

信息学奥赛一本通T1238：分治算法一元三次方程求解

【题目描述】形如：ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d均为实数)，并约定该方程存在三个不同实根(根的范围在−100至100之间)，且根与根之差的绝对值≥1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。【输入】一行，包含四个实数a，b，c，d，相邻两个数之间用单个空格隔开。【输出】一行，包含三个实数，为该

0
0
轩爸
发布于 2020-04-30 16:20
阅读 ( 673 )

信息学奥赛一本通T1237：分治算法求排列的逆序数

【题目描述】在Internet上的搜索引擎经常需要对信息进行比较，比如可以通过某个人对一些事物的排名来估计他（或她）对各种不同信息的兴趣，从而实现个性化的服务。对于不同的排名结果可以用逆序来评价它们之间的差异。考虑1,2,…,n的排列i1，i2，…，in，如果其中存在j,k，满足j<k,且ij>ik，那么就称(ij,ik)是这个排列的一个逆序。一个排列含有逆序的个数称为这个排列的逆序数

0
0
轩爸
发布于 2020-04-30 16:20
阅读 ( 784 )

信息学奥赛一本通T1236：分治算法区间合并

【题目描述】给定 n 个闭区间 [ai; bi]，其中i=1,2,...,n。任意两个相邻或相交的闭区间可以合并为一个闭区间。例如，[1;2] 和 [2;3] 可以合并为 [1;3]，[1;3] 和 [2;4] 可以合并为 [1;4]，但是[1;2] 和 [3;4] 不可以合并。我们的任务是判断这些区间是否可以最终合并为一个闭区间，如果可以，将这个闭区间输出，否则输出no。【输入】第一行为一个整数

0
0
轩爸
发布于 2020-04-30 16:20
阅读 ( 756 )

信息学奥赛一本通T1234：分治算法 2011

【题目描述】已知长度最大为200位的正整数n，请求出2011n的后四位。【输入】第一行为一个正整数k，代表有k组数据（k≤200），接下来的k行，每行都有一个正整数n，n的位数≤200。【输出】每一个n的结果为一个整数占一行，若不足4位，去除高位多余的0。【输入样例】3【输出样例】1051【源程序】

0
1
轩爸
发布于 2020-04-30 10:20
阅读 ( 1312 )

信息学奥赛一本通T1235：分治算法输出前k大的数

【题目描述】给定一个数组，统计前k大的数并且把这k个数从大到小输出。【输入】第一行包含一个整数n，表示数组的大小。n < 100000。第二行包含n个整数，表示数组的元素，整数之间以一个空格分开。每个整数的绝对值不超过100000000。第三行包含一个整数k，k < n。【输出】从大到小输出前k大的数，每个数一行。【输入样例】10【输出样例】9【源程序】

0
1
轩爸
发布于 2020-04-30 10:20
阅读 ( 1407 )

信息学奥赛一本通T1233：贪心算法接水问题

【题目描述】学校里有一个水房，水房里一共装有m个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为1。现在有n名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从1到n编号，i号同学的接水量为wi。接水开始时，1到m号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学j完成其接水量要求wj后，下一名排队等候接水的同学k马上接替j同学的位置开始接水。这个换人的过程是瞬间完成的

0
0
轩爸
发布于 2020-04-30 10:20
阅读 ( 1473 )

信息学奥赛一本通T1232：贪心算法 Crossing River

【题目描述】几个人过河，每次过两人一人回，速度由慢者决定，问过河所需最短时间。【输入】输入t组数据，每组数据第1行输入n，第2行输入n个数，表示每个人过河的时间。【输出】输出t行数据，每行1个数，表示每组过河最少时间。【输入样例】1【输出样例】17【源程序】

0
0
轩爸
发布于 2020-04-30 10:20
阅读 ( 1317 )

信息学奥赛一本通T1231：贪心算法最小新整数

【题目描述】给定一个十进制正整数n(0<n<1000000000)，每个数位上数字均不为0。n的位数为m。现在从m位中删除k位(0<k<m)，求生成的新整数最小为多少？例如: n=9128456,k=2,则生成的新整数最小为12456。【输入】第一行t, 表示有t组数据；接下来t行，每一行表示一组测试数据，每组测试数据包含两个数字n,k。【输出】t行，每行一个数字，表示从n

0
0
轩爸
发布于 2020-04-30 10:20
阅读 ( 1056 )

信息学奥赛一本通T1230：贪心算法寻找平面上的极大点

【题目描述】在一个平面上，如果有两个点(x,y),(a,b),如果说(x,y)支配了(a,b)，这是指x≥a,y≥b;用图形来看就是(a,b)坐落在以(x,y)为右上角的一个无限的区域内。给定n个点的集合，一定存在若干个点，它们不会被集合中的任何一点所支配，这些点叫做极大值点。编程找出所有的极大点，按照x坐标由小到大，输出极大点的坐标。本题规定：n不超过100，并且不考虑点的坐标为负数的情况。【输

0
0
轩爸
发布于 2020-04-29 16:20
阅读 ( 682 )

信息学奥赛一本通T1229：贪心算法电池的寿命

【题目描述】小S新买了一个掌上游戏机，这个游戏机由两节5号电池供电。为了保证能够长时间玩游戏，他买了很多5号电池，这些电池的生产商不同，质量也有差异，因而使用寿命也有所不同，有的能使用5个小时，有的可能就只能使用3个小时。显然如果他只有两个电池一个能用5小时一个能用3小时，那么他只能玩3个小时的游戏，有一个电池剩下的电量无法使用，但是如果他有更多的电池，就可以更加充分地利用它们，比如他有三个电池分

0
1
轩爸
发布于 2020-04-29 16:20
阅读 ( 638 )

信息学奥赛一本通T1228：贪心算法书架

【题目描述】John最近买了一个书架用来存放奶牛养殖书籍，但书架很快被存满了，只剩最顶层有空余。John共有N头奶牛(1≤N≤20,000)，每头奶牛有自己的高度Hi(1≤Hi≤10,000)，N头奶牛的总高度为S。书架高度为B(1≤B≤S<2,000,000,007)。为了到达书架顶层，奶牛可以踩着其他奶牛的背，像叠罗汉一样，直到他们的总高度不低于书架高度。当然若奶牛越多则危险性越大。为了

0
0
轩爸
发布于 2020-04-29 16:20
阅读 ( 825 )