信息学奥赛一本通T1443：深搜的剪枝技巧 Addition Chains
【题目描述】已知一个数列a0,a1……am，其中a0=1,am=n; a0<a1<a2<……<am−1<am。对于每个k(1≤k≤m)满足ak=ai+aj(0≤i,j≤k−1),这里i与j可以相等。现给定n的值，要求m的最小值（并不要求输出）及这个数列的值（可能存在多个数列，只输出任意一个满足条件的就可以）。【输入】多组数据，每行给定一个正整数n。输入以0结束。【输出
- 0
- 0
- 轩爸
- 发布于 2020-05-20 16:20
- 阅读 ( 849 )
轩爸
信息学奥赛一本通T1442：深搜的剪枝技巧 小木棍
【题目描述】乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。【输入】第一行为一个单独的整数N表示砍过以后的小木棍的总数，其中N≤60，第二行为N个用空个隔开的正整数，表示N根小木棍的长度。【输出】仅一行，表示要求的原始木棍的最小
- 0
- 1
- 轩爸
- 发布于 2020-05-20 16:20
- 阅读 ( 1496 )
信息学奥赛一本通T1441：深搜的剪枝技巧 生日蛋糕
【题目描述】7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。设从下往上数第i(1≤i≤M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i＜M时，要求Ri>Ri+1且Hi>Hi+1。由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。令Q=Sπ,请编程对给出的N和M，找出蛋糕的制作方案（适当的
- 0
- 0
- 轩爸
- 发布于 2020-05-20 16:20
- 阅读 ( 946 )
信息学奥赛一本通T1440：深搜的剪枝技巧 数的划分
【题目描述】将整数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-20 16:20
- 阅读 ( 1133 )
信息学奥赛一本通T1439：二分与三分 传送带
【题目描述】对于给定的一个长度为N的正整数数列A[i]，现要将其分成M（M≤N）段，并要求每段连续，且每段和的最大值最小。关于最大值最小：例如一数列4 2 4 5 1要分成3段将其如下分段：[4 2][4 5][1]第一段和为6，第2段和为9，第3段和为1，和最大值为9。将其如下分段：[4][2 4][5 1]第一段和为4，第2段和为6，第3段和为6，和最大值为6。并且无论如何分段，最大值不会小于
- 0
- 0
- 轩爸
- 发布于 2020-05-20 16:20
- 阅读 ( 819 )
信息学奥赛一本通T1438：二分与三分 灯泡
【题目描述】相比 Wildleopard 的家，他的弟弟 Mildleopard 比较穷，他的房子是狭窄的，而且在他的房间里只有一个灯泡，每天晚上，他徘徊在自己狭小的房子里，思考如何赚更多的钱。有一天，他发现他的影子的长度随着他在灯泡和墙壁之间走动时会发生变化。一个突然的想法出现在他的脑海里，他想知道在房间里他影子的最大长度【输入】第一行包含一个整数 T（T<=100），表示测试数据的组数对
- 0
- 1
- 轩爸
- 发布于 2020-05-20 10:20
- 阅读 ( 1000 )
信息学奥赛一本通T1436：二分与三分 数列分段II
【题目描述】对于给定的一个长度为N的正整数数列A[i]，现要将其分成M（M≤N）段，并要求每段连续，且每段和的最大值最小。关于最大值最小：例如一数列4 2 4 5 1要分成3段将其如下分段：[4 2][4 5][1]第一段和为6，第2段和为9，第3段和为1，和最大值为9。将其如下分段：[4][2 4][5 1]第一段和为4，第2段和为6，第3段和为6，和最大值为6。并且无论如何分段，最大值不会小于
- 0
- 0
- 轩爸
- 发布于 2020-05-20 10:20
- 阅读 ( 1005 )
信息学奥赛一本通T1437：二分与三分 扩散
【题目描述】一个点每过一个单位时间就会向四个方向扩散一个距离，如图。两个点a、b连通，记作e(a,b),当且仅当a、b的扩散区域有公共部分。连通块的定义是块内的任意两个点u、v都必定存在路径e(u,a0),e(a0,a1),…,e(ak,v)。给定平面上的n给点，问最早什么时刻它们形成一个连通块。【输入】第一行一个数n，以下n行，每行一个点坐标。【输出】一个数，表示最早的时刻所有点形成连通块。【输
- 0
- 1
- 轩爸
- 发布于 2020-05-20 10:20
- 阅读 ( 918 )
信息学奥赛一本通T1435：二分与三分 曲线
【题目描述】明明做作业的时候遇到了n个二次函数Si(x)= ax2 + bx + c，他突发奇想设计了一个新的函数F(x) = max(Si(x)), i = 1...n.明明现在想求这个函数在[0,1000]的最小值，要求精确到小数点后四位四舍五入。【输入】输入包含T 组数据 (T < 10) ，每组第一行一个整数 n(n ≤ 10000) ,之后n行，每行3个整数a (0 ≤ a ≤ 1
- 0
- 0
- 轩爸
- 发布于 2020-05-20 10:20
- 阅读 ( 1125 )
信息学奥赛一本通T1434：二分与三分 Best Cow Fences
【题目描述】给定一个长度为n的正整数序列A。求一个平均数最大的，长度不小于L的子序列。【输入】第一行，n和L；n个正整数，表示A。【输出】一个整数，表示答案的1000倍（不用四舍五入，直接输出）。【输入样例】10 6 【输出样例】6500【源程序】
- 0
- 0
- 轩爸
- 发布于 2020-05-20 10:20
- 阅读 ( 979 )
信息学奥赛一本通T1433：二分与三分 愤怒的牛
【题目描述】农夫 John 建造了一座很长的畜栏，它包括 N(2≤N≤100,000) 个隔间，这些小隔间依次编号为 x1,...,xN(0≤xi≤1,000,000,000). 但是，John 的 C(2≤C≤N) 头牛们并不喜欢这种布局，而且几头牛放在一个隔间里，他们就要发生争斗。为了不让牛互相伤害。John 决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离
- 0
- 1
- 轩爸
- 发布于 2020-05-19 16:20
- 阅读 ( 971 )
信息学奥赛一本通T1432：贪心算法 糖果传递
【题目描述】有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。【输入】第一行一个正整数n≤1000000，表示小朋友的个数．接下来n行，每行一个整数ai，表示第i个小朋友得到的糖果的颗数．【输出】求使所有人获得均等糖果的最小代价。【输入样例】4【输出样例】4【源程序】
- 0
- 0
- 轩爸
- 发布于 2020-05-19 16:20
- 阅读 ( 1138 )
信息学奥赛一本通T1431：贪心算法 钓鱼
【题目描述】在一条水平路边，有 nn 个钓鱼湖，从左到右编号为 1,2,…,n。佳佳有 HH 个小时的空余时间，他希望利用这个时间钓到更多的鱼。他从 1 出发，向右走，有选择的在一些湖边停留一定的时间（是 55 分钟的倍数）钓鱼。最后在某一个湖边结束钓鱼。佳佳从第 i 个湖到第 i+1 个湖需要走 5×Ti分钟路，还测出在第 i 个湖停留，第一个 5 分钟可以钓到 Fi 条鱼，以后每再钓 5
- 0
- 1
- 轩爸
- 发布于 2020-05-19 16:20
- 阅读 ( 967 )
信息学奥赛一本通T1430：贪心算法 家庭作业
【题目描述】老师在开学第一天就把所有作业都布置了，每个作业如果在规定的时间内交上来的话才有学分。每个作业的截止日期和学分可能是不同的。例如如果一个作业学分为10，要求在6天内交，那么要想拿到这10学分，就必须在第6天结束前交。每个作业的完成时间都是只有一天。例如，假设有7次作业的学分和完成时间如下：作业号 1 2 3 4 5 6 7最多可以获得15学分，其
- 0
- 0
- 轩爸
- 发布于 2020-05-19 16:20
- 阅读 ( 1076 )
信息学奥赛一本通T1429：贪心算法 线段
【题目描述】在一个数轴上有n条线段，现选取其中k条线段使得这k条线段两两没有重合部分，问最大的k为多少?【输入】第一行为一个正整数n，下面n行每行2个数字ai，bi,描述每条线段。【输出】输出文件仅包括1个整数，为k的最大值。【输入样例】3【输出样例】2【源程序】
- 0
- 1
- 轩爸
- 发布于 2020-05-19 16:20
- 阅读 ( 1239 )
信息学奥赛一本通T1428：贪心算法 数列分段
【题目描述】对于给定的一个长度为N的正整数数列A[i]，现要将其分成连续的若干段，并且每段和不超过M（可以等于M），问最少能将其分成多少段使得满足要求。【输入】第1行包含两个正整数N，M，表示了数列A[i]的长度与每段和的最大值；第2行包含N个空格隔开的非负整数A[i]，如题目所述。【输出】一个正整数，输出最少划分的段数。【输入样例】5 6 【输出样例】3【源程序】
- 0
- 0
- 轩爸
- 发布于 2020-05-19 10:20
- 阅读 ( 976 )
信息学奥赛一本通T1427：贪心算法 数列极差
【题目描述】在黑板上写了N个正整数作成的一个数列，进行如下操作：每一次擦去其中的两个数a和b，然后在数列中加入一个数a×b+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的max，最小的为min，则该数列的极差定义为M=max−min。【输入】第一行，一个数为N;第二行，N个数。【输出】输出极差。【输入样例】3【输出样例】2【源程序】
- 0
- 0
- 轩爸
- 发布于 2020-05-19 10:20
- 阅读 ( 1066 )
信息学奥赛一本通T1426：贪心算法 智力大冲浪
【题目描述】小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者m元。先不要太高兴！因为这些钱还不一定都是你的。接下来主持人宣布了比赛规则： 首先，比赛时间分为n个时段(n≤500)，它又给出了很多小游戏，每个小游戏都必须在规定期限ti前完成(1≤ti≤n)。如果一个游戏没能在规定期限前完成，则要从奖励费m元中扣去一部分钱wi，wi为自然数
- 0
- 0
- 轩爸
- 发布于 2020-05-19 10:20
- 阅读 ( 918 )
信息学奥赛一本通T1425：贪心算法 加工生产调度
【题目描述】某工厂收到了 n 个产品的订单，这 n 个产品分别在 A、B 两个车间加工，并且必须先在 A 车间加工后才可以到 B 车间加工。某个产品 i 在 A，B 两车间加工的时间分别为Ai,Bi。怎样安排这 n 个产品的加工顺序，才能使总的加工时间最短。这里所说的加工时间是指：从开始加工第一个产品到最后所有的产品都已在 A，B 两车间加工完毕的时间。【输入】第一行仅—个数据 n ，表示产品的数
- 0
- 0
- 轩爸
- 发布于 2020-05-19 10:20
- 阅读 ( 1014 )
信息学奥赛一本通T1424：贪心算法 喷水装置
【题目描述】长L 米，宽 WW 米的草坪里装有 n 个浇灌喷头。每个喷头都装在草坪中心线上（离两边各 W/2 米）。我们知道每个喷头的位置（离草坪中心线左端的距离），以及它能覆盖到的浇灌范围。请问：如果要同时浇灌整块草坪，最少需要打开多少个喷头？【输入】输入包含若干组测试数据。第一行一个整数 T 表示数据组数；每组数据的第一行是整数 n、L 和 W；接下来的 n 行，每行包含两个整数，给出一个喷头
- 0
- 1
- 轩爸
- 发布于 2020-05-19 10:20
- 阅读 ( 863 )
