信息学奥赛一本通T1278：动态规划经典问题 复制书稿

【题目描述】现在要把m本有顺序的书分给k个人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三和第四本书给同一个人抄写。现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。【输入】第一行两个整数m，k；（k≤m≤500）第二行m个整数，第i个整数表示第i本书的页数。【输出】共k行，每行两个整数

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

信息学奥赛一本通T1277：动态规划经典问题 方格取数

【题目描述】设有N×N的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字0。如下图所示：某人从图中的左上角A出发，可以向下行走，也可以向右行走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。此人从A点到B点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。【输入】第一行为一个整数N（N≤10），表示N×N的方格图。接下来的每行有三

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

信息学奥赛一本通T1276：动态规划经典问题 编辑距离

【题目描述】设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种：    1、删除一个字符；    2、插入一个字符；    3、将一个字符改为另一个字符。对任意的两个字符串A和B，计算出将字符串A变换为字符串B所用的最少字符操作次数。【输入】第一行为字符串A；第二行为字符串B；字符串A和B的长度均小于2000。【输出】只有一个正整数，为最少字符操

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

信息学奥赛一本通T1275：动态规划经典问题 乘积最大

【题目描述】今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积最大。同时，为了帮助选手能够正确

• 0
• 2
• 轩爸
• 发布于 2020-05-04 10:20
• 阅读 ( 706 )

信息学奥赛一本通T1274：动态规划经典问题 合并石子

【题目描述】在一个操场上一排地摆放着Ｎ堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的２堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。计算出将Ｎ堆石子合并成一堆的最小得分。【输入】第一行为一个正整数N (2≤Ｎ≤100)；以下Ｎ行,每行一个正整数，小于10000，分别表示第i堆石子的个数(1≤i≤N)。【输出】一个正整数，即最小得分。【输入样例】7【输出样例】269【源程序

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

信息学奥赛一本通T1273：背包问题 货币系统

【题目描述】给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。【输入】第一行为n和m。【输出】一行，方案数。【输入样例】3 10        //3种面值组成面值为10的方案【输出样例】10          //有10种方案【源程序】 

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

信息学奥赛一本通T1271：背包问题 潜水员

【题目描述】潜水员为了潜水要使用特殊的装备。他有一个带2种气体的气缸：一个为氧气，一个为氮气。让潜水员下潜的深度需要各种的数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少？例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：3 36 12010 25 1295 50 2501

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

信息学奥赛一本通T1272：背包问题 分组背包

【题目描述】一个旅行者有一个最多能装V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn，它们的价值分别为C1,C2,...,Cn。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。【输入】第一行：三个整数，V(背包容量，V≤200)，N(物品数量，N≤30)和T(最大组号，T≤10)；第2..N

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

信息学奥赛一本通T1270：背包问题 混合背包

【题目描述】一个旅行者有一个最多能装V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn，它们的价值分别为C1,C2,...,Cn。有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。【输入】第一行：二个整数，M(背包容量，M≤200)，N(物品

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

信息学奥赛一本通T1269：背包问题 庆功会

【题目描述】为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。【输入】第一行二个数n(n≤500)，m(m≤6000)，其中n代表希望购买的奖品的种数，m表示拨款金额。接下来n行，每行3个数，v、w、s，分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和能购买的最大数量（买0件到s件均

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

信息学奥赛一本通T1268：背包问题 完全背包问题

【题目描述】设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。【输入】第一行：两个整数，M(背包容量，M≤200)和N(物品数量，N≤30)；第2..N+1行：每行二个整数Wi,Ci，表示每个物品的重量和价值。【输出】仅一行，一个数，表示最大总价值。【输

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

信息学奥赛一本通T1267：背包问题 01背包问题

【题目描述】一个旅行者有一个最多能装 M 公斤的背包，现在有 n 件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn，求旅行者能获得最大总价值。【输入】第一行：两个整数，M(背包容量，M≤200)和N(物品数量，N≤30)；第2..N+1行：每行二个整数Wi，Ci，表示每个物品的重量和价值。【输出】仅一行，一个数，表示最大总价值。【输入样例】10 4【输出样

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

信息学奥赛一本通T1266：动态规划的基本模型 机器分配

【题目描述】总公司拥有高效设备M台，准备分给下属的N个分公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M≤15，N≤10。分配原则：每个公司有权获得任意数目的设备，但总台数不超过设备数M.【输入】第一行有两个数，第一个数是分公司数N，第二个数是设备台数M；接下来是一个N*M的矩阵，表明了第 I个公司分配 J台机器的盈利。

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

CCF Online NOI初创成功——王宏，周苗

CCF分别于2020年3月7日和4月25日举办了两场NOI Online能力测试，两场活动整体顺畅，且第二次比第一次更好。这是疫情期间开展的、也是NOI三十多年来新开创的一种形式，扩宽了NOI的发展空间。其中的经验需要总结，教训需要吸取。一、3月7日第一场测试3月7日的第一场测试受到黑客攻击，可以总结为：虽遇攻击、但不能击倒我们，及时总结快速应变最重要。在最初计划举办online测试时，考虑到我们...

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

关于第二场NOI Online测试成绩查询及证明申请的通知

CCF定于即日起开始受理第二场NOI Online能力测试成绩证明申请。凡排名在第二场NOI Online能力测试入门组/提高组前25%的选手均可申请成绩证明。本次成绩证明仅有电子版。一、成绩查询选手可登陆NOI官网，凭准考证号查看个人成绩和前25%选手名单（点击查看）。二、成绩证明申请时间即日起至2020年5月8日24点截止，逾期申请不予受理。三、成绩证明费用：免费凡符合要求的申请者，请在规定时...

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

CCF关于举办第三场NOI Online能力测试的通知

CCF拟于5月24日举办第三场NOI Online能力测试。测试分为入门组和提高组，任何感兴趣的选手均可参加。每组成功报名选手在同一时间参加线上测试。一、测试时间：熟悉系统环境：5月23日（周六）19:00-20:00正式测试提高组：5月24日（周日）8:30-12:00正式测试入门组：5月24日（周日）14:30-18:00二、测试方式：1.选手报名成功后，根据系统生成的准考证号和密码登陆测试系...

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

信息学奥赛一本通T1265：动态规划的基本模型 最长公共子序列

【题目描述】一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X=<x1,x2,…,xm>，则另一序列Z＝<z1，z2，…，zk>是X的子序列是指存在一个严格递增的下标序列<i1,i2,…,ik>,使得对于所有j=1,2,…,k有：Xij=Zj例如，序列Z=<B,C,D,B>是序列X=<A,B,C,B,D,A,B&g

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

信息学奥赛一本通T1264：动态规划的基本模型 合唱队形

【题目描述】N位同学站成一排，音乐老师要请其中的(N−K)位同学出列，使得剩下的KK位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1,2,…,K，他们的身高分别为T1,T2,…,TK，则他们的身高满足T1<T2<…<Ti,Ti>Ti+1>…>TK(1≤i≤K)。你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩

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

信息学奥赛一本通T1263：动态规划的基本模型 友好城市

【题目描述】Palmia国有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航线不相交的情况下，被批准的申请尽量多。【输入

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

信息学奥赛一本通T1262：动态规划的基本模型 挖地雷

【题目描述】在一个地图上有n个地窖（n≤200）,每个地窖中埋有一定数量的地雷。同时，给出地窖之间的连接路径，并规定路径都是单向的,且保证都是小序号地窖指向在序号地窖，也不存在可以从一个地窖出发经过若干地窖后又回到原来地窖的路径。某人可以从任一处开始挖地雷，然后沿着指出的连接往下挖（仅能选择一条路径），当无连接时挖地雷工作结束。设计一个挖地雷的方案，使他能挖到最多的地雷。【输入】第一行：地窖的个数

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