信息学奥赛一本通T1446：深搜的剪枝技巧 素数方阵
【题目描述】CE数码公司开发了一种名为自动涂色机（APM）的产品。它能用预定的颜色给一块由不同尺寸且互不覆盖的矩形构成的平板涂色。为了涂色，APM需要使用一组刷子。每个刷子涂一种不同的颜色C。APM拿起一把有颜色C的刷子，并给所有颜色为C且符合下面限制的矩形涂色：为了避免颜料渗漏使颜色混合，一个矩形只能在所有紧靠它上方的矩形涂色后，才能涂色。例如图中矩形F必须在C和D涂色后才能涂色。注意，每一个矩
- 0
- 0
- 轩爸
- 发布于 2020-05-21 10:20
- 阅读 ( 972 )
轩爸
信息学奥赛一本通T1445：深搜的剪枝技巧 平板涂色
【题目描述】CE数码公司开发了一种名为自动涂色机（APM）的产品。它能用预定的颜色给一块由不同尺寸且互不覆盖的矩形构成的平板涂色。为了涂色，APM需要使用一组刷子。每个刷子涂一种不同的颜色C。APM拿起一把有颜色C的刷子，并给所有颜色为C且符合下面限制的矩形涂色：为了避免颜料渗漏使颜色混合，一个矩形只能在所有紧靠它上方的矩形涂色后，才能涂色。例如图中矩形F必须在C和D涂色后才能涂色。注意，每一个矩
- 0
- 0
- 轩爸
- 发布于 2020-05-21 10:20
- 阅读 ( 579 )
信息学奥赛一本通T1444：深搜的剪枝技巧 埃及分数
【题目描述】在古埃及，人们使用单位分数的和(形如1/a的, a是自然数)表示一切有理数。如：2/3=1/2+1/6,但不允许2/3=1/3+1/3,因为加数中有相同的。对于一个分数a/b,表示方法有很多种，但是哪种最好呢？首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。如：19/45=1/3 + 1/12 + 1/18019/45=1/3 + 1/15 + 1/4519/45
- 0
- 1
- 轩爸
- 发布于 2020-05-21 10:20
- 阅读 ( 1235 )
关于第三场NOI Online能力测试准考证号的说明
第三场NOI Online能力测试准考证号已生成，选手可登陆报名系统进行查看。具体查看方式请参考报名通知内附的使用说明。准考证号是选手登录考试系统和于NOI官网查询测试成绩的依据和凭证，请务必妥善记录和保存。 NOI竞赛办公室2020年5月20日...
- 0
- 0
- 轩爸
- 发布于 2020-05-20 16:20
- 阅读 ( 271 )
信息学奥赛一本通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
- 阅读 ( 624 )
信息学奥赛一本通T1442：深搜的剪枝技巧 小木棍
【题目描述】乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。【输入】第一行为一个单独的整数N表示砍过以后的小木棍的总数，其中N≤60，第二行为N个用空个隔开的正整数，表示N根小木棍的长度。【输出】仅一行，表示要求的原始木棍的最小
- 0
- 1
- 轩爸
- 发布于 2020-05-20 16:20
- 阅读 ( 1326 )
信息学奥赛一本通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
- 阅读 ( 754 )
信息学奥赛一本通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
- 阅读 ( 931 )
信息学奥赛一本通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
- 阅读 ( 682 )
信息学奥赛一本通T1438：二分与三分 灯泡
【题目描述】相比 Wildleopard 的家，他的弟弟 Mildleopard 比较穷，他的房子是狭窄的，而且在他的房间里只有一个灯泡，每天晚上，他徘徊在自己狭小的房子里，思考如何赚更多的钱。有一天，他发现他的影子的长度随着他在灯泡和墙壁之间走动时会发生变化。一个突然的想法出现在他的脑海里，他想知道在房间里他影子的最大长度【输入】第一行包含一个整数 T（T<=100），表示测试数据的组数对
- 0
- 1
- 轩爸
- 发布于 2020-05-20 10:20
- 阅读 ( 887 )
信息学奥赛一本通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
- 阅读 ( 829 )
信息学奥赛一本通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
- 阅读 ( 731 )
信息学奥赛一本通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
- 阅读 ( 896 )
信息学奥赛一本通T1434：二分与三分 Best Cow Fences
【题目描述】给定一个长度为n的正整数序列A。求一个平均数最大的，长度不小于L的子序列。【输入】第一行，n和L；n个正整数，表示A。【输出】一个整数，表示答案的1000倍（不用四舍五入，直接输出）。【输入样例】10 6 【输出样例】6500【源程序】
- 0
- 0
- 轩爸
- 发布于 2020-05-20 10:20
- 阅读 ( 867 )
信息学奥赛一本通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
- 阅读 ( 755 )
信息学奥赛一本通T1432：贪心算法 糖果传递
【题目描述】有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。【输入】第一行一个正整数n≤1000000，表示小朋友的个数．接下来n行，每行一个整数ai，表示第i个小朋友得到的糖果的颗数．【输出】求使所有人获得均等糖果的最小代价。【输入样例】4【输出样例】4【源程序】
- 0
- 0
- 轩爸
- 发布于 2020-05-19 16:20
- 阅读 ( 958 )
信息学奥赛一本通T1431：贪心算法 钓鱼
【题目描述】在一条水平路边，有 nn 个钓鱼湖，从左到右编号为 1,2,…,n。佳佳有 HH 个小时的空余时间，他希望利用这个时间钓到更多的鱼。他从 1 出发，向右走，有选择的在一些湖边停留一定的时间（是 55 分钟的倍数）钓鱼。最后在某一个湖边结束钓鱼。佳佳从第 i 个湖到第 i+1 个湖需要走 5×Ti分钟路，还测出在第 i 个湖停留，第一个 5 分钟可以钓到 Fi 条鱼，以后每再钓 5
- 0
- 1
- 轩爸
- 发布于 2020-05-19 16:20
- 阅读 ( 831 )
信息学奥赛一本通T1430：贪心算法 家庭作业
【题目描述】老师在开学第一天就把所有作业都布置了，每个作业如果在规定的时间内交上来的话才有学分。每个作业的截止日期和学分可能是不同的。例如如果一个作业学分为10，要求在6天内交，那么要想拿到这10学分，就必须在第6天结束前交。每个作业的完成时间都是只有一天。例如，假设有7次作业的学分和完成时间如下：作业号 1 2 3 4 5 6 7最多可以获得15学分，其
- 0
- 0
- 轩爸
- 发布于 2020-05-19 16:20
- 阅读 ( 921 )
信息学奥赛一本通T1429：贪心算法 线段
【题目描述】在一个数轴上有n条线段，现选取其中k条线段使得这k条线段两两没有重合部分，问最大的k为多少?【输入】第一行为一个正整数n，下面n行每行2个数字ai，bi,描述每条线段。【输出】输出文件仅包括1个整数，为k的最大值。【输入样例】3【输出样例】2【源程序】
- 0
- 1
- 轩爸
- 发布于 2020-05-19 16:20
- 阅读 ( 1020 )
信息学奥赛一本通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
- 阅读 ( 830 )
