没有合适的资源?快使用搜索试试~ 我知道了~
首页USACO试题精选.pdf
USACO试题精选.pdf
需积分: 50 24 下载量 6 浏览量
更新于2023-03-16
评论 2
收藏 1.23MB PDF 举报
这个是USACO题库中选出来的一些题,覆盖了多方面的知识点,利于锻炼C++学者的算法,里面还有部分题解
资源详情
资源评论
资源推荐
版权说明:本文档可自由使用,商业目的除外
USACO 试题精选 第一辑
第 1 题 利润 (Profits, 2011 Jan) ........................................................................................ 3
第 2 题 购买饲料 II (Buying Feed II, 2010 Jan) .................................................................. 4
第 3 题 抓苹果 (Apple Catching, 2004 Nov) ..................................................................... 5
第 4 题 抢购干草 (Hay For Sale, 2008 Dec)...................................................................... 6
第 5 题 建造道路 (Building Roads, 2007 Dec) .................................................................. 7
第 6 题 建造栅栏 (Building A Fence, 2008 Oct) ............................................................... 8
第 7 题 青铜莲花池 (Bronze Lilypad Pond, 2007 Feb) ..................................................... 9
第 8 题 奶牛杂技 (Cow Acrobats, 2005 Nov) ................................................................. 10
第 9 题 滑雪课程 (Ski Lessons, 2009 Open) ................................................................... 11
第 10 题 奶牛飞盘队 (Cow Frisbee Team, 2009 Mar)...................................................... 12
第 11 题 最近回文 (Cheapest Palindrome, 2007 Open) .................................................. 13
第 12 题 奶牛集会 (MooFest, 2004 Open) ...................................................................... 14
第 13 题 奶牛博览会 (Cow Exhibition, 2003 Fall) ............................................................ 15
第 14 题 忽悠奶牛 (Cheering up the Cows, 2008 Nov) .................................................... 16
第 15 题 玉米迷宫 (Corn Maze, 2011 Open) ................................................................... 17
第 16 题 奶牛文字 (Cowlphabet, 2011 Feb) .................................................................... 18
第 17 题 奶牛跨栏 (Cow Hurdles, 2007 Nov) ................................................................... 19
第 18 题 工作安排 (Work Scheduling, 2009 Open) ......................................................... 20
第 19 题 滑雪缆车 (Ski Lift, 2006 Mar) ............................................................................ 21
第 20 题 股票市场 (Stock Market, 2009 Feb) .................................................................. 22
第 21 题 提交作业 (Turning in Homework, 2004 Open) .................................................. 23
第 22 题 白银莲花池 (Silver Lilypad Pond, 2007 Feb) ..................................................... 24
第 23 题 赞助学费 (Financial Aid, 2004 Mar) .................................................................. 25
第 24 题 奶牛观光 (Sightseeing Cows, 2007 Dec) ........................................................... 26
第 25 题 地震 (Earthquake, 2001 Open) .......................................................................... 27
第 26 题 手机网络 (Cell Phone Network, 2008 Jan) ........................................................ 28
第 27 题 派发巧克力 (Chocolate Giving, 2010 Feb) ........................................................ 29
第 28 题 奶牛赛车 (Cow Cycling, Feb 2002) .................................................................... 30
第 29 题 叠积木 (Cube Stacking, 2004 Open) .................................................................. 31
第 30 题 奶牛接力 (Cow Relays, 2007 Nov) ..................................................................... 32
第 31 题 猜数游戏 (Haybale Guessing, 2008 Jan) ............................................................ 33
第 32 题 混乱奶牛 (Mixed Up Cows, 2008 Nov) .............................................................. 34
第 33 题 道路重建 (Rebuilding Roads, Feb 2002) ............................................................ 35
第 34 题 修剪草坪 (Mowing the Lawn, 2011 Open) ........................................................ 36
第 35 题 安排牧场 (Corn Fields, 2006 Nov) ..................................................................... 37
第 36 题 洞穴奶牛 I (Cave Cow 1, 2004 Open) ................................................................. 38
第 37 题 奶牛抗议 (Generic Cow Protests, 2011 Feb) ..................................................... 39
第 38 题 打扫食槽 (Cleaning Up, 2009 Mar) ................................................................... 40
第 39 题 道路翻新 (Revamping Trails, 2009 Feb)............................................................. 41
第 40 题 电子游戏 (Video Game Troubles, 2009 Dec) ..................................................... 42
第 41 题 土地并购 (Land Acquisition, 2008 Mar) ............................................................ 43
第 42 题 购买饲料 I (Buying Feed, 2010 Nov) .................................................................. 44
第 43 题 干草塔 (Tower of Hay, 2009 Open) .................................................................... 45
第 44 题 产奶比赛 (Milk Team Select, 2006 Mar) ........................................................... 46
第 45 题 明星奶牛 (Popular Cows, 2003 Fall) .................................................................. 47
第 46 题 黄金莲花池 (Lilypad Pond, 2007 Feb) ............................................................... 48
第 47 题 逢低吸纳 (BUY LOW, BUY LOWER, Feb 2002) ................................................... 49
第 48 题 焊接 (Soldering, 2011 Open) ............................................................................. 50
第 49 题 旅馆 (Hotel, 2008 Feb) ....................................................................................... 51
第 50 题 道路和航线 (Roads and Planes, 2011 Jan) ........................................................ 52
这一辑从 USACO 月赛中选择了质量较高的 50 题,是用来训练算法设计和实现的极好素
材,如果初学者希望掌握比较扎实的基本功,建议将这一辑的题目好好研究一下。可能用到
的知识点有:
动态规划:区间上的动态规划、背包问题、树上的动态规划、集合上的动态规划、
单调队列优化、斜率优化
数据结构:堆、并查集、树状数组、线段树
图论:Prim 和 Kruskal 算法,Dijkstra 算法及其堆优化实现,Bellman-Ford 算法及其
队列优化,Floyd 算法,深度优先遍历,广度优先遍历
算法思想:贪心、枚举、二分、归纳
这只是一个不太完整的列表,希望选手在训练时候不要太依赖于提示,自己思考更有乐
趣。在 题目顺序的编排上,我是按照题目的难度和代码的长度来循序渐进的。翻译基本忠于
原文,可能修改了个别段落,使得描述更加简短清晰。如果有问题,请参考原文。每道题目
的出处已在标题中标出。测试数据和官方解答很容易从网上查得,不做赘述。
做多少题目才能在信息学竞赛上获得好成绩?我不太确定。著名数学教育工作者刘培杰
先生曾撰文指出,正常人从初学到精通一项技能需要一万个小时的训练量。飞行员如此,运
动员如此,竞赛选手仍然如此。我询问了一下上海交通大学 ACM-ICPC 代表队的队员和教练
员,基本上每个人都做了 5000 道以上的题目,如果一道题目以一小时计算,至少在大学一
二年级期间,他们都训练了 5000 小时以上了。我猜想,NOIP 要拿好成绩,100 行的程序写
100 道,应该是要的;NOI 想要拿好成绩,200 行的程序写 200 道,应该也是要的。
接下来我还打算继续挑选 USACO 月赛里的好题目,凑满 50 道就集结成册,希望以后有
时间,连解答一起,写成一本书吧,可能要很久才能完成了,请勿过度期待。
马 融
marong1204@gmail.com
第1题 利润 (Profits, 2011 Jan)
奶牛开了家新公司,这家公司已经连续运作了天,财务报表显示她们在第天获得了
元利润,有些天的利润可能是个负数(负数表示亏损)。约翰想给奶牛的新公司写个新闻,
以吹嘘她们的惊人业绩。为了美化成绩,他打算选出一段连续的日子,使新公司在这段日子
里的利润之和是最大的。这段日子的长度不限,但至少要包括一天。
输入格式
第一行:单个整数,
第二行到 行:第 行有一个整数
,代表第天的利润,
输出格式
单个整数,表示最大的利润和
样例
profits.in
profits.out
7
-3
4
9
-2
-5
8
-3
14
(选择第三天到第六天,一共是
元)
第2题 购买饲料 II (Buying Feed II, 2010 Jan)
约翰在镇上,沿着公路开车回家,顺路准备买吨饲料回家。沿路开了家商店,第家
店距离起点
公里,饲料单价为每吨
元,库存
吨。约翰的家离起点有公里。每家商店
以整数吨起卖,保证所有商店的库存总和不会少于。不过运送饲料回家是要花油钱的,如
果约翰的车上装着吨饲料,行驶一公里会花掉
元,行驶公里就需要
元。那么为了带
吨饲料回家,约翰最少的花费是多少呢?
举个例子,假设有三家商店,情况如下所示:
距离
库存
1
1
1
单价
1
2
2
如果约翰要买吨饲料回家,他家距离起点公里,那么他的最好选择是在离家较近的
两家商店购买饲料,则花在路上的钱是 ,花在商店的钱是 ,一共元。
输入格式
第一行:三个用空格分开的整数:,和, , ,
第二行到 行:第 行有三个整数:
,
和
,
,
,
输出格式
单个整数,表示购买和运送饲料的最小总费用
样例
feed2.in
feed2.out
2 5 3
3 1 2
4 1 2
1 1 1
7
第3题 抓苹果 (Apple Catching, 2004 Nov)
奶牛喜欢吃苹果。约翰有两棵苹果树,每棵树上都结满了苹果,每分钟都会有一只苹果
从一棵树上落下,如果正好站在那棵树下,贝西就能接住苹果。贝西在两棵树之间的移动是
瞬间的,但她的运动能力不足,所以最多只能移动次。假设贝西可以玩分钟,请帮助她
计算一下最多可以接几个苹果。一开始贝西在第一棵树下。
输入格式
第一行:两个用空格分开的整数:和, ,
第二行到第 行:第 行有个整数
,表示第分钟的苹果将从哪棵树上掉落,1
表示从第一棵树,2 表示从第二棵树
输出格式
第一行:表示能抓到的最大苹果数量
样例
bcatch.in
bcatch.out
7 2
2
1
1
2
2
1
1
6
(首先待在第一棵树下抓到两个,再移动到
第二棵树下抓住两个,再返回第一棵树,抓
住最后两个)
剩余51页未读,继续阅读
Ending940
- 粉丝: 0
- 资源: 2
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- ExcelVBA中的Range和Cells用法说明.pdf
- 基于单片机的电梯控制模型设计.doc
- 主成分分析和因子分析.pptx
- 共享笔记服务系统论文.doc
- 基于数据治理体系的数据中台实践分享.pptx
- 变压器的铭牌和额定值.pptx
- 计算机网络课程设计报告--用winsock设计Ping应用程序.doc
- 高电压技术课件:第03章 液体和固体介质的电气特性.pdf
- Oracle商务智能精华介绍.pptx
- 基于单片机的输液滴速控制系统设计文档.doc
- dw考试题 5套.pdf
- 学生档案管理系统详细设计说明书.doc
- 操作系统PPT课件.pptx
- 智慧路边停车管理系统方案.pptx
- 【企业内控系列】企业内部控制之人力资源管理控制(17页).doc
- 温度传感器分类与特点.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0