当前位置:首页 >> 学科竞赛 >>

USACO习题总结


USACO 习 题 总 结

Chongqing Nankai High School

USACO 习题总结
前 言
USACO 全 称 美国计算机奥林匹克竞赛,其官方网站所开设的训练 系统 USACO Training,是全球知名的信息学在线题库。该题库拥有很高 的题目质量,且难度由浅及深层次清晰,使得不同水平的竞赛

选手均能从 中获益。本文即是笔者历时数月完成 USACO Training 中全部题目后所做 的习题总结,以供日后复习和参考之用。 USACO 题库经过多年的维护与修订, 现共有 6 章 23 节 97 题, 其中 多含历届国际大赛真题,所涉及的算法和数据结构之广,也几乎完整涵盖 了国内分区联赛的所有题型。故而民间向来就有“做完前三章,稳拿一等 奖”的说法,足见该题库在竞赛学习中的价值。然而更为重要的是:许多 学校在开展竞赛教学的过程中,往往过度偏重于知识的讲解与传授,却忽 视了习题的重要性,选手的模型还原能力和算法实现能力无法得到真正的 锻炼,则势必会严重影响其实力的发挥;但若一味地埋头题海,对高级算 法和数据结构缺乏应有的了解,也难以取得理想的竞赛成绩。所以循序渐 进, 在掌握新算法的同时适时巩固练习, 未尝不是最为科学合理学习方法, 而 USACO 题库则正是这样一套优秀的竞赛训练系统。 相信无论是信息竞赛的初学者,还是冲刺奖牌的优胜者,抑或是程序 设计的爱好者,都能在完成这样一套题库之后收获和巩固自己对算法的认 知与感悟。虽然我个人水平相当有限,但假如这套习题总结,能为您在竞 赛学习的过程中提供些许帮助,我必将深感荣幸。 重庆南开中学 万山川 2009 年 12 月

-1-

USACO 习 题 总 结

Chongqing Nankai High School

目 录
一 、 题 目 索 引 … … … … … … … … … … … … … … P03 二 、 简 明 题 解 … … … … … … … … … … … … … … P08
1) Chapter1 2) Chapter2 3) Chapter3 4) Chapter4 5) Chapter5 6) Chapter6 … … … … … … … … … … … … … … … 08 … … … … … … … … … … … … … … … 12 … … … … … … … … … … … … … … … 16 … … … … … … … … … … … … … … … 21 … … … … … … … … … … … … … … … 25 … … … … … … … … … … … … … … … 30

附 : 参 考 资 料 … … … … … … … … … … … … … … P31

-2-

USACO 习 题 总 结

Chongqing Nankai High School

一、题目索引 第一章
Chapter1 1.1.1 1.1.2 1.1.3 1.1.4 1.2.1 1.2.2 1.2.3 1.2.4 1.2.5 1.3.1 1.3.2 1.3.3 1.3.4 1.4.1 1.4.2 1.4.3 1.4.4 1.5.1 1.5.2 1.5.3 1.5.4 Getting started
字符串处理 模拟 模拟 枚举 模拟 模拟 模拟 进制转换 进制转换 贪心 贪心 枚举 枚举 模拟 搜索 枚举 搜索 动态规划 筛法 枚举 搜索

Your Ride Is Here Greedy Gift Givers Friday the Thirteenth Broken Necklace Milking Cows Transformations Name That Number Palindromic Squares Dual Palindromes Mixing Milk Barn Repair Calf Flac Prime Cryptarithm Packing Rectangles The Clocks Arithmetic Progressions Mother's Milk Number Triangles Prime Palindromes SuperPrime Rib Checker Challenge

第一章是为初学者们所开设的章节,只会涉及到一些基础算法,诸如 模拟、枚举、贪心和简单的动态规划。适合初学者们实践从中课本中学到 的语法知识,使选手们更进一步了解到竞赛题目的风格。

-3-

USACO 习 题 总 结

Chongqing Nankai High School

第二章
Chapter2 2.1.1 2.1.2 2.1.3 2.1.4 2.1.5 2.2.1 2.2.2 2.2.3 2.2.4 2.3.1 2.3.2 2.3.3 2.3.4 2.3.5 2.4.1 2.4.2 2.4.3 2.4.4 2.4.5 Bigger Challenges
灌水法 枚举 贪心 搜索 位运算 枚举 动态规划 模拟 搜索 动态规划 动态规划 搜索 动态规划 搜索 模拟 搜索 最短路径 最短路径 模拟

The Castle Ordered Fractions Sorting A Three-Valued Sequence Healthy Holsteins Hamming Codes Preface Numbering Subset Sums Runaround Numbers Party Lamps The Longest Prefix Cow Pedigrees Zero Sum Money Systems Controlling Companies The Tamworth Two Overfencing Cow Tours Bessie Come Home Fractions to Decimals

第二章加入了更多对编程技巧的考验,有些题则会用到与之前相比更 为高级的算法,最为实用的当属最短路径算法和位运算优化。本章中动态 规划和搜索也是考察的重点,尤其体现在第三小节,而这也正是国内联赛 中最热门的题型,应当熟练掌握。

-4-

USACO 习 题 总 结

Chongqing Nankai High School

第三章
Chapter3 3.1.1 3.1.2 3.1.3 3.1.4 3.1.5 3.1.6 3.2.1 3.2.2 3.2.3 3.2.4 3.2.5 3.2.6 3.3.1 3.3.2 3.3.3 3.3.4 3.3.5 3.4.1 3.4.2 3.4.3 3.4.4 Techniques more subtle
最小生成树 动态规划 枚举 矩形切割 字典树 动态规划 高精度 动态规划 模拟 枚举 搜索 最短路径 欧拉路径 动态规划 最短路径 动态规划 博弈动规 计算几何 递归 枚举 动态规划

Agri-Net Score Inflation Humble Numbers Shaping Regions Contact Stamps Factorials Stringsobits Spinning Wheels Feed Ratios Magic Squares Sweet Butter Riding The Fences Shopping Offers Camelot Home on the Range A Game Closed Fences American Heritage Electric Fence Raucous Rockers

第三章中会接触到越来越多的新题型和新算法,诸如欧拉路、最小生 成树、矩形切割、线段树以及计算几何中的一些基本公式。很多题目并不 局限于唯一的标准解法,选手在习题过程中应当勇于尝试以不同或更优的 算法解决相同的问题。

-5-

USACO 习 题 总 结

Chongqing Nankai High School

第四章
Chapter4 4.1.1 4.1.2 4.1.3 4.1.4 4.2.1 4.2.2 4.2.3 4.2.4 4.3.1 4.3.2 4.3.3 4.3.4 4.4.1 4.4.2 4.4.3 Advanced algorithms and difficult drills
动态规划 迭代加深 最小环 搜索 最大费用流 二分图匹配 贪心 搜索 动态规划 搜索 搜索 枚举 构造法 最小边割 拓扑排序

Beef McNuggets Fence Rails Fence Loops Cryptcowgraphy Drainage Ditches The Perfect Stall Job Processing Cowcycles Buy Low, Buy Lower The Primes Street Race Letter Game Shuttle Puzzle Pollutant Control Frame Up

第四章题目的整体难度明显加强,网络流、二分图等高级算法和数据 结构开始登场,而搜索的优化和剪枝也开始变得越发重要。选手们很难再 找到一道不需要高级算法或进一步优化便能轻松解决的题目,这为我们的 竞赛学习带来了新的挑战和更高的要求。

-6-

USACO 习 题 总 结

Chongqing Nankai High School

第五章、第六章
Chapter5 5.1.1 5.1.2 5.1.3 5.2.1 5.2.2 5.2.3 5.3.1 5.3.2 5.3.3 5.3.4 5.4.1 5.4.2 5.4.3 5.4.4 5.4.5 5.5.1 5.5.2 5.5.3 Serious challenges
二维凸包 搜索 动态规划 搜索 搜索 搜索 迭代加深 矩形切割 强连通分量 动态规划 搜索 动态规划 动态规划 搜索 最小点割 线段树 枚举 记忆化搜索

Fencing the Cows Starry Night Musical Themes Snail Trail Electric Fences Wisconsin Squares Milk Measuring Window Area Network of Schools Big Barn All Latin Squares Canada Tour Character Recognition Betsy's Tour TeleCowmunication Picture Hidden Passwords Two Five

Chapter6 6.1.1 6.1.2 6.1.3

Contest Practice
动态规划 动态规划 位运算

Postal Vans A Rectangular Barn Cow XOR

第五章、第六章拥有与第四章相似的特点和更高的难度,每一道题都 有很高的训练价值,有的甚至还饶有趣味,非常适合联赛级别以上的选手 逐一攻克。
-7-

USACO 习 题 总 结

Chongqing Nankai High School

二、简明题解

Chapter1 Getting started
1.1.1 题目 题型 题解 1.1.2 题目 题型 题解 1.1.3 题目 题型 题解 Your Ride Is Here (ride)
计算并比较两字符串每位字符 ASCII 值的连续乘积。 字符串处理 直接模拟即可。

Greedy Gift Givers (gift1)
已知每人的钱数和好友,将钱均分给好友后,求每人所得结余。 模拟、字符串哈希* 直接模拟即可,检索姓名时可以使用字符串哈希优化。

Friday the Thirteenth (friday)
统计一定年份内每月 13 日在星期一至日出现的次数。 模拟、蔡勒公式* 以月为最小单位模拟计算即可, 也可用蔡勒公式根据日期直接推算 出星期。

1.1.4 题目 题型 题解 1.2.1 题目 题型 题解

Broken Necklace (beads)
计算一串由三种不同字符组成的环中,从任意位置起,向左右两旁 可拓展的最长距离和。 枚举、动态规划* 枚举起始位置并计算扩展距离。

Milking Cows (milk2)
给出 N 个区间,求所有区间并集的补集。 模拟、离散化*、线段树* 用布尔数组模拟即可,但需注意所给数据均为开区间,可将数组范 围展开至 2 倍,将每个点拆为起止两个点。

-8-

USACO 习 题 总 结

Chongqing Nankai High School

1.2.2 题目 题型 题解 1.2.3 题目 题型 题解 1.2.4 题目 题型 题解 1.2.5 题目 题型 题解 1.3.1 题目 题型 题解 1.3.2 题目 题型 题解

Transformations (transform)
给出两幅字串组成的图形和 7 种变换规则,求两图形间变换方法。 模拟 枚举 7 种变换规则,寻找匹配方案。

Name That Number (namenum)
给出一串数字、一份字串表和数字与字母之间的对应规则,求表中 哪些字符串符合对应规则。 模拟 因字串表保证升序排列,可直接一边读入一边判断。

Palindrome Squares (palsquare)
输出 B 进制下 300 以内所有 B 进制二次方结果成回文状的数。 进制转换 模拟转换过程即可。

Dual Palindromes (dualpal)
输出前 N 个大于 S 且在两种及以上进制中均成回文状的数。 进制转换 因数据量允许,可直接枚举 S 以上 10 进制数。

Dual Palindromes (dualpal)
已知同种物品在不同商家处的单价和供应量, 求满足额定需求量所 支出的最小花费。 贪心 尽可能从价廉的厂商处优先买进,直至满足需求。

Barn Repair (barn1)
数轴上有 C 个被标记点,求用 M 个区间覆盖住所有被标记点所需 的最小区间长度。 贪心、动态规划* 最小覆盖长度等同于最大未覆盖长度, 初始时可令一大区间覆盖数 -9-

USACO 习 题 总 结

Chongqing Nankai High School

轴上全部点集,按次截去现有区间中最长未标记子区间,将木板截 为 M 段即可。

1.3.3 题目 题型 题解 1.3.4 题目 题型 题解 1.4.1 题目 题型 题解 1.4.2 题目 题型 题解

Calf Flac (calfflac)
寻找最长回文子串。 枚举、动态规划* 枚举字串起始位置,并验证回文属性。

Prime Cryptarithm (crypt1)
以给定数字填充固定格式的竖式乘法表,求合法的方案数。 枚举、搜索 枚举被乘数和乘数共计 5 个数位上的数,并验证方案合法性。

Packing Rectangles (packrec)
给定 4 个矩形块,找出一个最小的封闭矩形将这 4 个矩形块放入, 但不得相互重叠。 模拟 模拟 6 种可能的摆放方案,求出最小边长。

The Clocks (clocks)
有 9 块时针指向不同的时钟, 以及 9 种不同的调整操作, 求将所有 时钟时针调至 12 点方向的最短操作顺序。 搜索、枚举 经典的宽度优先搜索例题,需使用哈希判重,对于此题深搜与暴力 枚举也同样适用。

1.4.3 题目 题型 题解

Arithmetic Progressions (ariprog)
在双平方数集合(即所有能表示成 p2+q2 的数的集合)中长度为 N 的等差数列。 枚举 枚举所有可能解,适时剪枝即可。

- 10 -

USACO 习 题 总 结

Chongqing Nankai High School

1.4.4 题目 题型 题解 1.5.1 题目 题型 题解

Mother's Milk (milk3)
ABC 三个杯子相互倒灌,初始时 AB 为空 C 为满,求 C 杯子任意 时刻可能的剩余量。 搜索 宽搜判重,枚举每个时刻可能的 6 种倒灌方案。

Number Triangles (numtri)
现有一个数字金字塔,求一条从最高点到底部任意处结束的路径, 使得所经过的数字之和最大。 动态规划 经典的动态规划, f[i,j]为到达第 j 层第 i 个位置时所取得的最大 令 值,转移方程为 f[i,j]=max{f[i,j-1],f[i-1,j-1]}+a[i,j]。

1.5.2 题目 题型 题解 1.5.3 题目 题型 题解

Prime Palindromes (pprime)
找出一定范围内的所有回文素数。 枚举 先用枚举求出范围内全部回文数,再判断是否为素数。

SuperPrime Rib (sprime)
求出所有 N 位特殊质数,即该数前 1~N 位均为质数。 搜索 深搜构造每一位并判断是否为质数,首位只能由 2,3,5,7 构成,其 余为只可能为 1,3,7,9。

1.5.4 题目 题型 题解

Checker Challenge (checker)
N 皇后问题,输出前三个解的方案和解的总数。 搜索、位运算优化 使用位运算优化的搜索题。 在搜索过程中分别用三个二进制参数记 录竖列和两条对角线的摆放情况,将已放置的位置标记为 1(2)。可 由这三个参数的并集的补集得到所在横行剩余的合法位置, 每次取 右边第一个合法位置递归深入, 当参数中所有二进制数位均被标记 为 1(2) 时即找到了一种合法方案。

- 11 -

USACO 习 题 总 结

Chongqing Nankai High School

Chapter2 Bigger Challenges
2.1.1 题目 题型 题解 The Castle (castle)
平面房间被墙分成多个小区域,求最大的两块相邻的连通区域。 灌水法、位运算、并查集* 输入数据中的数字完全按照二进制规则给出, 从高位向低位依次表 示西北东南四个方向上有无围墙,用灌水法搜出每块连通区域面 积,再枚举相邻区域使面积之和最大即可。

2.1.2 题目 题型 题解 2.1.3 题目 题型 题解

Ordered Fractions (frac1)
找出所有满足条件的最简分数 a/b,使得 1≤b≤N 且 0≤a/b<1。 枚举、排序、递归* 枚举所有符合条件的 a 和 b,并按照 a/b 排序输出。

Sorting A Three-Valued Sequence (sort3)
一个由 1,2,3 组成的数字序列,求排成升序所需的最少交换次数。 贪心 升序序列必按出现次数分三段排列, 每次可将第一段中非 1 数与原 所属段或另一段中的 1 相交换,并依此类推交换所有乱序数字。

2.1.4 题目 题型 题解 2.1.5 题目 题型 题解

Healthy Holsteins (holstein)
每件物品有 V 种附加值,求最少的选择方案,使得 V 种附加值的 需求量均得到满足。 搜索、迭代加深* 深搜每样物品是否被选择,逐次加大搜索深度,并记录最优方案。

Hamming Codes (hamming)
从所有非负数中找出 N 个编码,使得编码两两之间在二进制表示 法中至少有 D 个数位上的数字不相同。 枚举、位运算 从 0 开始枚举, 使得每个新加入输出列表的数, 与之前找出的所有 数比对均符合条件。 - 12 -

USACO 习 题 总 结

Chongqing Nankai High School

2.2.1 题目 题型 题解 2.2.2 题目 题型 题解

Preface Numbering (preface)
统计在用罗马数字表示的前 N 个自然数中 IVXLCDM 的出现次数。 枚举、数学方法* 枚举所有 N 以内的数,将其转为罗马数字后统计字母的出现次数。

Subset Sums (subset)
对于前 N 个自然数组成的集合,可将其划分为两个不相交的子集 合,且保证两个集合内的数字和相等,求划分方案的总数。 动态规划 等同于求物品大小为 1~N 而总容量为(n+1)*n/4 时的背包问题的 方案数,可令 f[ j]表示子集之和为 j 时的方案数,逐一枚举前 N 个 自然数 i 和背包容量 j,f[ j]=∑ (f[ j-i])。

2.2.3 题目

Runaround Numbers (runround)
求第一个大于 M 且具有这样性质的循环数:从第 2 个数开始循环 地数第一个数的大小个数, 以后每次从停止位后开始数停止位上数 的长度的数,在经过每个数字一次后回到起点的就是循环数。

题型 题解 2.2.4 题目 题型 题解

模拟 从 M 开始枚举,找到第一个循环数即可。

Party Lamps (lamps)
有 N 盏灯和 4 种批量开关灯的操作方式,给出经过 C 次以内的操 作之后部分灯的状态,求所有灯最后可能的状态。 搜索、位运算* 搜索即可, 可以用位运算优化, 根据规律只需用前 4 盏灯即可表示 所有灯的状态,并且使用 xor 异或可以很方便地模拟 4 种开关。

2.3.1 题目 题型 题解

The Longest Prefix (prefix)
给出一个字符串 S 和一个由字串组成的集合, S 中可由集合内元 求 素所构成的最长前缀长度。 动态规划、字典树* f[i]表示长度为 i 的前缀能否取得,len[j]表示集合内字串长度, f[i]=f[i-len[j]] and (copy(s,i-len[j]+1,len[j])=a[j])。 - 13 -

USACO 习 题 总 结

Chongqing Nankai High School

2.3.2 题目 题型 题解

Cow Pedigrees (nocows)
求有 N 个结点, 深度为 M 且每个结点的度均为偶数的二叉树个数。 动态规划 令 f[i,j]表示结点数为 i 深度为 j 的二叉树个数,由乘法原理可得, f[i,j]=∑ (f[k,j-1]*f[i-k-1,j-1]) (1≤ k≤ i-2)。

2.3.3 题目 题型 题解 2.3.4 题目 题型 题解 2.3.5 题目 题型 题解 2.4.1 题目 题型 题解 2.4.2 题目 题型 题解

Zero Sum (zerosum)
在 1~N 的序列中插入加减运算符或者空格,使得算式结果为 0。 搜索 深搜枚举运算符,并验证结果是否为零。

Money Systems (money)
给出不同货币的面值,求构成一定数额的方案数。 动态规划 令 f[i]表示钱数为 i 时的方案数,f[i]=∑ (f[i-a[j]])。

Controlling Companies (concom)
当公司 A 拥有 B 一半以上的股权或 A 的子公司在 B 的股权之和超 过 50%时 A 可以控制 B,给出股权分布情况,求公司间控制情况。 搜索 根据规则循环更新被控制情况,直至更新停止。

The Tamworth Two (ttwo)
F 和 C 均按固定的前进方式在地图里游荡,求最短相遇时间。 模拟 模拟两者前行方式,并用所在位置判重即可。

Overfencing (maze1)
一个有多个出口的迷宫,求从任意一点走出迷宫的最小步数。 搜索 用 dis[i,j]记录从(i,j)走出迷宫所需最小步数,依次从每个入口开 始宽搜,不断更新 dis[i,j],答案即是 dis[i,j] 中 的最大值。 - 14 -

USACO 习 题 总 结

Chongqing Nankai High School

2.4.3 题目 题型 题解

Cow Tours (cowtour)
给出一些独立的无向图, 并定义图的直径为任意两点之间最短路径 的最大值, 现在任意两图中连接一条边, 求连通后新图的最小直径。 枚举、多源最短路 先求出每个图内的最短路径, 并用 di st[i]记录点 i 到相距最远的点 的最短距离,再枚举分属两个不同图内的点 i 和 j,新图的最小直 径即 min(dist[i]+di st[j]+dis(i,j)), 其中 di s(i,j)为两点间距离。

2.4.4 题目 题型 题解

Bessie Come Home (comehome)
求图中一点到其他被标记点最短路径的最小值。 单源最短路 经典的最短路模型,可尝试用尽量多的最短路算法解决此题,并且 因数据范围较小,甚至 O(n3)的 Floyd 算法对此题也同样适用。

2.4.5 题目 题型 题解

Fractions to Decimals (fracdec)
将给出的分数转换为小数形式,可能会出现循环小数。 模拟 模拟长除法过程,当余数不为 0 时,便将其扩大 10 倍作为新的被 除数,重复此过程,直到被除尽或找到循环节。记录下每个余数第 一次出现的位置,若相同的余数重复出现,则当前位置与初次出现 位置之间的部分即是循环节。

- 15 -

USACO 习 题 总 结

Chongqing Nankai High School

Chapter3 Techniques more subtle
3.1.1 题目 题型 题解 Agri-Net (agrinet)
用 N-1 条边将 N 个点连接起来,求边长和最短的方案。 最小生成树 经典的最小生成树例题,常用算法有适用于稠密图的 Prim 和适用 于稀疏图 Kruskal 两种。

3.1.2 题目 题型 题解

Score Inflation (inflate)
在总容量一定的情况下,求物品选择方案使得总价值最大,每种物 品可重复选择。 动态规划 完全背包问题,f[i]表示总容量为 i 时总价值的最大值,状态转移 方程与 0/1 背包相同,只是枚举容量时应从下限向上枚举, f[j]=max(f[j-vol[i]]+val[i])。

3.1.3 题目 题型 题解

Humble Numbers (humble)
现有素数集合 S1,求合数集合 S2,其中所有合数的质因数均为 S1 中素数,并且这样的合数被称为丑数,求 S2 中第 N 个丑数。 枚举 枚举素数与丑数集合间的最小乘积,逐个产生新的丑数。对于每个 素数,可以分别记录上一次与第几个丑数相乘,避免重复求积。

3.1.4 题目 题型 题解

Shaping Regions (rect1)
将 N 个不同颜色的矩形相互重叠地放置在白色平面上,求各种颜 色最后剩余的可见面积。 矩形切割、线段树* 本题坐标范围极大, 普通的灌水法和坐标离散化都会超过空间或时 间限制,可以考虑采用矩形切割算法解决,将新加入的矩形与队中 其他矩形相交的部分切割后放入队中,并更新重叠部分的颜色标 记,最后统计队中各矩形面积即可。

- 16 -

USACO 习 题 总 结

Chongqing Nankai High School

3.1.5 题目 题型 题解

Contact (contact)
给出一串 01 字符,求其中长度在 A 到 B 之间的子串的重复频率。 字典树、散列表 由于字串中只有 0 和 1 并且 B≤12, 可以采用字典树很方便地解决 本题,对于每个的长度在 A~B 之间的子串,对其在树中所在链上 叶子结点的计数累加 1,最后统计所有叶子上的计数结果即可。

3.1.6 题目 题型 题解

Stamps (stamps)
已知一个 N 枚邮票的票面集合和张数使用上限 K,求此集合可组 成的从 1 开始连续的邮资集合。 动态规划 令 f[i]表示组成价值为 i 的邮资所需的最少邮票张数,易得出状态 转移方程 f[i]=min(f[i-val[j]]+1,f[i]),当某一时刻 f[i]的值大 于上限 K 时即求得答案为 i-1。

3.2.1 题目 题型 题解 3.2.2 题目 题型 题解

Factorials (fact4)
求 N!最后一位非零数,N≤4220。 高精度 因数据范围较小,直接用高精度乘法求该数阶乘即可。

Stringsobits (kimbits)
求第 I 个二进制长度为 N 且 1(2)的个数不超过 L 的数。 动态规划、康托展开 令 f[j,k]表示二进制长度为 j 且 1 的个数不超过 k 个的数的总数, f[j,k]=f[j-1,k]+f[j-1,k-1],即在当前位加上 0 和 1 两种状态, 最后再用康托展开求出第 I 个数的二进制表示。

3.2.3 题目 题型 题解

Spinning Wheels (spin)
五个不同转速的轮子,每个轮子上都有一处缺口,求五处缺口初次 重合所需时间。 模拟 模拟轮轴转动过程即可。

- 17 -

USACO 习 题 总 结

Chongqing Nankai High School

3.2.4 题目 题型 题解 3.2.5 题目 题型 题解 3.2.6 题目 题型 题解 3.3.1 题目 题型 题解

Feed Ratios (ratios)
市场上每份饲料由三种原料所构成, 现用三种原料配比不同的饲料 调配理想饲料,求方案。 枚举 枚举每种饲料的份数,记录符合理想配比的最小方案。

Magic Squares (msquare)
给出 2×4 个有序方格和三种基本操作,求转换到目标状态所需的 最少操作序列。 搜索、康托展开 根据三种操作宽度优先搜索,用康托展开判重。

Sweet Butter (butter)
求图中一点,使得该点到其他点的最短路径和最短。 最短路径 枚举集结点,求单源最短路长度和。

Riding The Fences (fence)
从任意点开始遍历图中所有边,求字典序最小的途径顶点序列。 欧拉路径 遍历边的过程即是求一条欧拉路径的过程对于无向图, 如果每个点 的度都是偶数,那么图中存在一条欧拉回路,遍历的起点可以是任 意点; 如果有且仅有 2 个点的度为奇数, 那么图中存在一条欧拉路, 遍历的起点只能是度为奇数的点。

3.3.2 题目 题型 题解

Shopping Offers (shopping)
商店将部分物品捆绑销售并附有价格优惠, 现给出每件物品的需求 量,求刚好满足需求量的最少消费。 动态规划、最短路径 令 f[x1,x2,x3,x4,x5]表示每件物品的分别购买 x1~x5 件时的最低消费 额,f[x1,x2,x3,x4,x5]=min(f[x1-q[1],x2-q[2], x3-q[3],x4-q[4], x5-q[5]]+p[i]),也可将每种状态[x1,x2,x3,x4,x5]都作为一个顶点,每 项优惠则作为一条边,求[0,0,0,0,0]到目标状态的最短路。 - 18 -

USACO 习 题 总 结

Chongqing Nankai High School

3.3.3 题目

Camelot (camelot)
将棋盘中的国王和 N 个骑士移动到同一格,王每次可以走到相邻 的 8 格之内,骑士则按“日”字前进,王可另由骑士护送,从他俩 相遇的那个点开始一起行动,计算一共所需的最小步数。

题型 题解

最短路径 求出任意两个方格之间的最短路径,再枚举集合点,最终结果为骑 士们到集合点的距离和,再加上王走到该点的距离,这里需分三种 情况讨论:⑴王自行走到集合点;⑵骑士护送;⑶王前进一段距离 后,再由骑士护送。

3.3.4 题目 题型 题解

Home on the Range (range)
一个由 0 和 1 组成的矩形,求其中所有由 1 组成的子正方形边长。 动态规划、二维线段树* 令 f[i,j]表示以(i,j)为右下角的可构成的最大的正方形边长,方程 为 f[i,j]:=min(f[i-1,j],f[i,j-1],f[i-1,j-1])+1,由于本题需统计 所有可能的正方形边长,最后应将长度不超过 f[i,j]的方案一并统 计后输出。

3.3.5 题目 题型 题解

A Game (game1)
两人均按最优策略, 轮流从一正整数序列的两端取数, 求最后结果。 博弈论、动态规划 令 f[i,j]表示序列中第 i 至 j 个数所组成的子序列中选手 A 的最优取 值结果,f[i,j]=max(f[i +1,j]+a[i],f[i,j-1]+a[j]),选手 B 的结 果即为 sum[i,j]-f[i,j]。

3.4.1 题目 题型 题解

Closed Fences (fence4)
一个由平面上一些不相交的线段首尾相连而围成闭合栅栏, 给出一 个参考点的坐标,求从参考点上所能看见的栅栏列表。 计算几何 用二分法确定线段上的取样点, 若连接参考点和取样点的线段上没 有其他相交或重叠线段,则该点及所在线段可见,但需注意精度和 几种特殊的相交情况。

- 19 -

USACO 习 题 总 结

Chongqing Nankai High School

3.4.2 题目 题型 题解

American Heritage (heritage)
给出二叉树的先序遍历和中序遍历,求该树的后序遍历。 递归 根据二叉树遍历的性质,先序遍历的第一个结点必为当前子树的 根,而在中序遍历中根的位置之前必为根的左子树,之后必为根的 右子树,再递归建立其左右子树,直至完成整棵二叉树的建立,最 后输出其后序遍历即可。

3.4.3 题目 题型 题解

Electric Fence (fence9)
有一个由三个给定点所围成的三角形,求三角形内所有的整数点。 枚举、皮克定理 枚举三角形内所有整点即可,也可以使用皮克定理:面积 S 等于内 部整点数 a 与边上整点数 b 除 2 的商的和加 1,即 S=a+b/2+1。

3.4.4 题目 题型 题解

Raucous Rockers (rockers)
用 N 首歌灌制 M 张唱片,每张唱片总时长为 T,在保持歌曲顺序 不变的前提下,求最佳方案使得发行的歌曲总数尽量多。 动态规划、记忆化搜索 令 f[i,j,k]表示前 i 首歌装于 j 张唱片且第 j 张唱片剩余时间为 k 时最 多可能的灌制的歌曲数,状态转移方程 f[i,j,k]=max(f[i-1,j,k], f[i-1,j,k+a[i]]+1, f[i-1,j-1,0]+1)。

- 20 -

USACO 习 题 总 结

Chongqing Nankai High School

Chapter4 Advanced algorithms and difficult drills
4.1.1 题目 题型 题解 Beef McNuggets (nuggets)
已知 N 个数,求无法由这些数累加得到的最大正整数。 动态规划、构造法 令 f[i]表示正整数 i 可否由所给数字相加得到,可以证明结果不会 超过最大两个数的最小公倍数,f[i]=f[i] or f[i-a[j]] (1≤j≤n), 也可以尝试使用搜索直接构造。

4.1.2 题目 题型 题解

Fence Rails (fence8)
现有 N 段原木,需切割成 R 块木料,原木和木料的长度均不唯一, 求最佳的切割方案以使木料需求尽可能得到满足。 迭代加深 迭代加深搜索可以切出的木料数,用二分法枚举深度,最终结果即 是最大的合法深度。

4.1.3 题目 题型 题解

Fence Loops (fence6)
从无向图的任一点出发后再回到该点,求所经过的最短路径。 最小环 先需将题目中所给的边转化成点,再由每个顶点 i 开始求单源最短 路,枚举其他所有顶点 j,此时松弛前后的路径(i,j)便构成了一个 环,求出环长的最小值即可。

4.1.4 题目

Cryptcowgraphy (cryptcow)
有一种加密方式,随机地把 C,O,W 三个字母插到原字符串中,通 过交换 C-O 和 O-W 之间的子串实现加密,现给出加密后的信息, 求此信息被加密的次数。

题型 题解

搜索、字符串哈希 通过搜索不断对加密字串进行解密, 最后验证还原信息的合法性即 可,但在搜索过程中需加入大量剪枝优化,其中最关键的有字符串 哈希判重、可行性剪枝和优化搜索顺序。

- 21 -

USACO 习 题 总 结

Chongqing Nankai High School

4.2.1 题目 题型 题解 4.2.2 题目 题型 题解 4.2.3 题目

Drainage Ditches (ditch)
一套由单一源点向汇点连接的排水系统,求这套系统的最大容量。 最大费用流 经典的网络流模型,常用算法有 Ford-Fulkerson、Dinic 和 SAP。

The Perfect Stall (stall4)
每头奶牛都有一些固定的产奶点, 每个产奶点同时只能容纳一头奶 牛,求最佳的匹配方案使得产奶量尽可能多。 二分图匹配 经典的最大匹配问题,可以使用网络流或匈牙利算法予以解决。

Job Processing (job)
M1 个 A 型机器对工件进行粗加工, 之后再由 M2 个 B 型机器对其 进行精加工,每个机器加工单个工件的时长有所不同,求完成 N 个工件的粗、精加工各自所需最少耗时。

题型 题解

贪心 根据问题的单调性, 使精加工耗时最短前提条件必然是粗加工耗时 同样最短,可分别记录每台机器当前已预订工作时长和总耗时,并 且始终将新的工件分配给预订时长与加工时长之和最小的 Ai 和 Bi。

4.2.4 题目 题型 题解 4.3.1 题目 题型 题解

Cowcycles (cowcycle)
在给定大小范围内找出两组数, 使得前后两组数之商满足最大值超 过最小值的 3 倍,并且排序后相邻两项商的差的方差最小。 搜索 搜索即可,但须根据题目限制予以剪枝。

Buy Low, Buy Lower (buylow)
最长下降子序列问题,计算序列长度和不重复的方案数。 动态规划 在求解最长长度时,可令 f[i]表示截止到第 i 个数的最长下降子序 列长度,f[i]=max(f[i-j])+1 (1≤j≤n, a[j]>a[i]),另设 g[i]表示 到第 i 个数为止的最长序列方案数,g[i]=∑ (g[j]) (1≤j≤i-1), 记录下序列方案中的上一位置 a[j],避免重复统计相同的方案。 - 22 -

USACO 习 题 总 结

Chongqing Nankai High School

4.3.2 题目

The Primes (prime3)
一个 5×5 的素数方阵,每行每列以及两条对角线上从上到下从左 至右均由 5 位素数构成,并且这些素数五个数位上的和必须相等, 现给出左上角的数和素数位数之和,计算所有可能的方案。

题型 题解

搜索优化 因为本题中所有方格相互牵制,故而优化搜索顺序就变得至关重 要,可以枚举两条对角线,接着枚举中间一竖列,再是第一和第五 行,最后枚举第二和第四行,此时第三行已由减法得到。

4.3.3 题目 题型 题解

Street Race (race3)
在一个有向有环图中,从顶点 0 走向顶点 N,求必定经过的顶点和 能够将图分割为前后两个互不连通分量的中间顶点。 搜索 枚举删除非起始点,从起点深搜判断是否仍有通路,若无则该点为 必经点,此时再继续搜索判断是否重复途径已经点,若否则该点为 中间点。

4.3.4 题目

Letter Game (lgame)
已知字母与数值间的对应规则,现给出标准串和一些字符串,每两 个字串之间可以组成字对, 计算所有数值之和与标准串相同的字串 或字对,并且其中每个字母的出现频数不能大于标准串中的频数。

题型 题解

枚举 预先排除掉所有非法字串,再依此生成所有合法字对,最后枚举验 证每个字串和字对的合法性即可。

4.4.1 题目

Shuttle Puzzle (shuttle)
一排各有 N 个的黑白棋子,棋子每步可以移动到相邻或相间一颗 棋子的空格,初始时左起 N 格为白子,右起 N 格为黑子,中间一 格为空,求调换所有黑白棋子位置的步数最少的移动方案。

题型 题解

构造法、搜索 本题可以用宽搜解决,然而通过对较小规模数据的观察,不难在本 题移动方案的前 n+1 个步骤所组成的序列中存在着明显的规律, 而其后 n 个步骤也可由此对称得出。 - 23 -

USACO 习 题 总 结

Chongqing Nankai High School

4.4.2 题目 题型 题解

Pollutant Control (milk6)
一套由单一源点向汇点连通的运输网络, 求代价最小的连边切割方 案,使得源汇点之间不再连通。 最小边割 根据最大流最小割定理,最小边割的容量即等于最大流的流量。在 求割边集时,可以先枚举去掉每条边后再求一次新图的最小割,若 边的容量恰好等于流量的减少量,则该边必在解集内,称之为确定 边。再用迭代加深求出割集内容量未满的边,若这些边连同已确定 边的流量总和与最小割值相等,并且去掉这些边后源汇点不再连 通,则这些边也在解集内。

4.4.3 题目 题型 题解

Frame Up (frameup)
将若干个矩形方框按次放入平面中, 方框之间相互重叠但始终有可 见部分,现给出最终的俯视图像,求方框的叠放顺序。 拓扑排序 由每个方框可见部分的最大和最小横纵坐标得出四个角的坐标, 以 此确定方框 i 的四条边,并在边上寻找覆盖 i 的其他方框 j,对于每 一个覆盖矩形建立一条有向边(i,j),最后求出所有合法的拓扑排序 序列即可。

- 24 -

USACO 习 题 总 结

Chongqing Nankai High School

Chapter5 Serious challenges
5.1.1 题目 题型 题解 5.1.2 题目 Fencing the Cows (fc)
二维平面上有若干个点,求一个周长最小且符合条件的凸多边形, 能够将所给点集完整包含。 二维凸包 典型的二维凸包问题,常用算法有 Graham 扫描法即卷包裹法。

Starry Night (starry)
一个由 0 和 1 组成的二维矩阵,所有相连通的 1 组成一个单位图 形,每个图形有八种形式的翻转变形,现在需要对矩阵中图形进行 标记,相同图形应打上相同标记。

题型 题解

搜索 用灌水法找出单位图形,若之前这种图形没有出现过,则将其八种 变形加入散列表中,否则将打上相同标记。

5.1.3 题目 题型 题解

Musical Themes (theme)
给出 N 个正整数,求其中最长的两个不相交的重复子序列。 动态规划、字符串匹配 先求出 N 个数的两两之差 a[1..n-1],题目实际要求的即是 a[i]的 重复长度, 可令 f[i,j]表示分别以第 i 和 j 个数结尾的重复子序列长 度,方程由最长公共子序列问题变形可得,a[i]≠a[j]时 f[i,j]=0, f[i-1,j-1]+1 ( j - i >f[i-1,j-1]+1) ,但因空间有限, 否则 f [ i , j ] = j -i-1 ( j - i ≤f[i-1,j-1]+1) 最后还需使用滚动数组优化,输出结果为 max(f[i,j])+1。

5.2.1 题目

Snail Trail (snail)
在 N×N 的棋盘中有若干的障碍点,现从左上角开始沿直线前进, 遇到障碍点或棋盘边缘则 90°转向,直到遇到已经点才停止,求 经过的最多格子数。

题型 题解

搜索 因障碍物总数不超过 26 个,直接深搜即可,每次沿直线前进,直 至碰到障碍点、棋盘边缘或已经点。 - 25 -

USACO 习 题 总 结

Chongqing Nankai High School

5.2.2 题目 题型 题解

Electric Fences (fence3)
二维平面上有若干条平行于坐标轴的线段, 求解平面内到所有线段 两端或垂足的距离总和最短的点。 搜索 题目要求精确到小数点后一位,可将坐标轴整体放大 10 倍,从几 何中心开始搜索,每次选择相邻四个方向上距离总和最更短的点, 可以迅速得到局部最优解,再多次搜索随机起点,重复上述操作即 可求出全局最优解。

5.2.3 题目

Wisconsin Squares (wissqu)
牧场和仓库里分别有固定数目的 5 种奶牛, 同种奶牛不能处于相邻 位置,给出牧场上奶牛的分布情况,现需将在牧场和仓库的奶牛进 行交换,求字典序最小的交换方案和总方案数。

题型 题解

搜索 直接深搜即可,预处理 f[i,j,k]表示与(i, j)相邻的第 K 种奶牛数, 若 f[i,j,k]=0 则表明当前位置可以放置该种奶牛。

5.3.1 题目 题型 题解

Milk Measuring (milk4)
商店里有 P 种容量不同的容器, 同种容器可以重复购买, 求一套购 买种类数最少的方案,使得这些容器容积之和恰好为 Q。 迭代加深、动态规划 迭代加深搜索购买方案,逐次加大购买种类数,注意重复购买同种 容器,容量总和超过 Q 则跳出。本题也可使用动态规划求解,令 f[i,j]表示前 i 个容器容量和为 j 的最少种类数,[i,j]=min(f[i-1,j], f f[i-1,j-a[i]*k]+1)。

5.3.2 题目

Window Area (window)
对二维平面中的矩形进行若干次放置、 移除、 调整叠放顺序等操作, 所有矩形均平行于两坐标轴且带有标记, 动态求解拥有同种标记的 矩形的面积可见率。

题型 题解

矩形切割 本题矩形数目和坐标范围都很大,可以使用矩形切割进行求解,并 用双向链表记录叠放顺序,模拟五种操作即可。 - 26 -

USACO 习 题 总 结

Chongqing Nankai High School

5.3.3 题目 题型 题解

Network of Schools (schlnet)
一个连通的有向无环图,求遍历全图所需最少的起点数,以及最优 的连边方案使得全图强连通。 强连通分量 求出图中所有极大强连通分量,将每个分量都缩为一个点,遍历起 点即为入度为 0 的顶点,再在所有入度为 0 和出度为 0 的顶点间 连接新边即可使全图强连通。

5.3.4 题目 题型 题解

Big Barn (bigbrn)
一个有若干损坏区域的矩形,求其中最大的完整子正方形的边长。 动态规划 状态转移方程同 3.3.4 range 一题,可令 f[i,j]表示以(i,j)为右下 角的可构成的最大的正方形边长,f[i,j]:=min(f[i-1,j],f[i,j-1], f[i-1,j-1])+1。

5.4.1 题目 题型 题解

All Latin Squares (latin)
在 N×N 的数字棋盘中,前 N 个自然数在每行每列均出现且只出 现一次,第一横行已经确定,求合法的摆放方案总数。 搜索 搜索构造合法方案, 因第一行已经确定, 故只需从(2,2)开始搜索剩 下边长为 n-1 的矩形, 实际上此过程中第一列剩余 n-1 个数也被确 定, 总方案数即当前结果乘以(n-1)!,但本题还需使用置换思想优 化,若出现相同置换圈,顺序交换后情况等价,则不必深入搜索, 只需累加方案数即可。

5.4.2 题目

Canada Tour (tour)
在一个顶点有序的无向图中, 按单调顺序从第一个顶点出发到达最 后一个顶点后再返回起始点,除起始点外其他顶点不可重复经过, 求一套最佳的访问方案使得经过的顶点尽可能多。

题型 题解

动态规划、网络流 问题等同于甲乙两人同时从起点出发,经过不同的顶点后到达终 点, 可令 f[i,j]表示甲乙分别到达顶点 i 和 j 时所经过的最多的顶点 数,方程 f[i,j]=max(f[i,1..j-1]+1)。 - 27 -

USACO 习 题 总 结

Chongqing Nankai High School

5.4.3 题目

Character Recognition (charrec)
26 个英文字母和空格的字体模型,分别用 27 个 20×20 的 01 点 阵表示,现给出一段已损坏的字符图案,可能会有 01 点阵错误, 也可能丢失或多余一行,求对应的原字符信息。

题型 题解

动态规划 每段图案必有差异率最小的标准字体与之对应,可用 g[i,j,k]统计 图案中第 i 行与 j 号字体模型的第 k 行的误差率, 再令 f[i,j]表示图 案中第 i 行及其后 j 行的最小误差之和, j=1 9~21 三种情况枚举 按 丢失或多余的行序,最后全图误差总和即为 dp[i]=min(dp[i-19], dp[i-20],dp[i-21]),转移的同时记录输出方案便可。

5.4.4 题目 题型 题解

Betsy's Tour (betsy)
在 N×N 的棋盘中,从左上角开始到左下角为止遍历整个棋盘,求 可能的方案总数。 搜索、动态规划 可以使用基于连通性状态压缩的动态规划或搜索剪枝解决, 主要依 靠可行性剪枝,若某点周围只有一个未经点则该点为必经点,若当 前点周围有两个及以上非终点的必经点,则势必会形成死胡同。

5.4.5 题目 题型 题解

TeleCowmunication (telecow)
一套由单一源点向汇点有向连通的电脑网络, 求代价最小的顶点切 割方案,使得源汇点之间不再连通。 最小点割 可以用拆点法将最小点割转化为最小边割问题, 使得最小点割的割 值即为新构造的流网络中的最大流流值,最后依次枚举删除顶点, 若删去后最大流流值比原流值少 1,则该点必为割点。

5.5.1 题目 题型 题解

Picture (picture)
N 个矩形相互平行地重叠摆放在二维平面中,求重叠图形的周长。 线段树 将横纵边分别排序,坐标相同时始边较终边靠前,再按序枚举横纵 边, 遇始边时将其在坐标轴上投影部分的附加值加 1, 遇终边减 1, 若某一时刻附加值增至 1 或减至 0,则将该段投影长度计入周长。 - 28 -

USACO 习 题 总 结

Chongqing Nankai High School

5.5.2 题目 题型 题解

Hidden Passwords (hidden)
在 L 个字符组成的字串中,字串头尾可循环衔接,现需找出其中长 度为 L 且字典序最小的子串。 枚举 用 min 和 now 两个指针进行比较,分别初始化为 1 和 2,令 now 指针向后循环推进,每次分别枚举两指针其后 L-1 个字符,若 s[now+i]<s[min+i]则两指针均跳至 now+i-1,若 s[now+i]>s[min+i] 则 now 指针跳至 now+i-1,以此避免相同前缀的重复比较。

5.5.3 题目 题型 题解

Two Five (twofive)
在 5×5 的棋盘中放入前 25 个字母,每行每列都严格递增,现给 出摆放方案求方案序号,或给出方案序号求摆放方案。 记忆化搜索、康拓展开 记忆化搜索, 可令 f[a,b,c,d,e]表示将前 a+b+c+d+e 个字母放入 棋盘中且第 1 至 5 行分别摆放 a 至 e 个字母时的方案总数,累加 所有序号更小的方案数即可求出已知方案的序号, 类似地逐位累计 方案数便可求出已知序号的对应方案。

- 29 -

USACO 习 题 总 结

Chongqing Nankai High School

Chapter6 Contest Practice
6.1.1 题目 题型 题解 Postal Vans (vans)
在 N×4 的棋盘中,从左上角出发沿棋盘线遍历所有顶点后再返回 起点,计算合法方案的总数。 动态规划、递推 由于答案范围过大,需使用高精度运算,当 n≥5 时存在如下递推 关系 f[n]=2f[n-1]+2f[n-2]-2f[n-3]+f[n-4]。

6.1.2 题目 题型 题解

A Rectangular Barn (rectbarn)
一个有若干块损坏区域的矩形,求其中最大的完整子矩形的边长。 动态规划 令 h[i,j]、 l[i,j]、 r[i,j]分别表示(i,j)位置向上左右三个方向最多可延伸 的距离,每行状态只与上一行有关,可以使用滚动数组优化空间。 h[i,j]= l [i,j]= r [i,j]= h[i,j-1]+1 0 min(l[i,j-1],tl) +∞
未损坏 已损坏 未损坏 已损坏

min(r[i,j-1],tr) 未损坏 已损坏 +∞ 其中 tl、tr 为当前点到左右两侧最近一处坏点或棋盘边缘的距离。

6.1.3 题目 题型 题解

Cow XOR (cowxor)
一串二进制长度不超过 21 的自然数,令 sum[i]表示前 i 个数连续 异或的结果, sum[i]异或 sum[j]的最大值和 i,j 的位置(1≤i,j≤n)。 求 位运算 枚举所有的 sum 数,用 f[0.. 4194303]记录到目前为止所有出现过 的二进制前缀, 由此求出当前数与之前所有数所能取得的最大异或 结果,同时记录所有数中最优结果的位置 t,向前逆向枚举 sum[j], 当 sum[t]异或 sum[j]结果最优时即可得到答案。

- 30 -

USACO 习 题 总 结

Chongqing Nankai High School

附:参考资料
多 年 来 USACO 题 库 在 国内诸多前辈的不断研习精深下,留下了 大量的解题报告和丰富的经验总结,成为了我们今天竞赛学习时的一笔不 可多得的财富。笔者在解题和总结过程中也屡有参考网络资料,以下予以 简单列述,未能详尽标明题解出处者还望见谅。

原创题解 Leokan 北极天南星 cuitianyi billylinux http://hi.baidu.com/leokan http://starforever.blog.hexun.com http://cuitianyi.com http://billylinux.blog.hexun.com

中文译题 NOCOW WZOI http://www.nocow.cn http://www.wzoi.org/usaco

- 31 -


相关文章:
bzoj刷题总结列表
! 1691: [Usaco2007 Dec]挑剔的美食家贪心,平衡树。 商品按照价格排序后贪心...大题总结版 暂无评价 6页 免费 习题归纳总结:统计表与... 20页 免费 大...
程序练习题一
程序设计练习题 1.描述:对键盘输入的两个字符串进行连接。 输入:两个字符串,...城堡 描述:以我们憨厚的 USACO 主人公农夫约翰(Farmer John) 无法想象的运气, ...
poj题目总结1
(USACO) 1245 1329 1550(考的是读题和理解能力) 1649(dp) 2200(字符串处理...的习题:1000 1003 1004 1005 2013 2017 需要根据情景稍微动下脑筋的习题:1922 ...
动态规划练习题(含答案)
动态规划练习题 USACO 2.2 Subset Sums 题目如下: 对于从 1 到 N 的连续整集合合,能划分成两个子集合,且保证每个集合的数字和 是相等的。 举个例子,如果 ...
USACO Chapter 1 解题总结
USACO Chapter 1 解题总结_学科竞赛_高中教育_教育专区。USACO 解题报告 Chapter USACO Chapter 1 解题总结 1.1.1 Your Ride Is Here 基本字符串操作,无压力。...
动态规划讲解大全(含例题及答案)
让我们通过对前面的例子再分析来具体说明这一点:从 A 到 D,我们知道,最短路 径是 A 动态规划练习题 USACO 2.2 Subset Sums 题目如下: 对于从 1 到 N ...
字符串习题
字符串习题 隐藏>> Your Ride Is Here 你要乘坐的飞碟在这里一个众所周知的...举例来说,团体 "USACO" 会是 21*19*1*3*15=17955 。 如果团体的数字 mod...
递归基础练习题
递归基础练习题_教育学_高等教育_教育专区。递归基础练习题 1. 求 1+2+3+...以下是 USACO contest 上的题目,全是递归 ---***...
动态规划习题精讲
动态规划习题精讲_数学_高中教育_教育专区。信息学竞赛...id=1441 【题目描述】 学生在我们 USACO 的竞赛中...推理型题分析与总结 78份文档 一起来学广场舞 广...
usaco第一章试题
usaco第一章试题_计算机软件及应用_IT/计算机_专业资料。USACO是美国著名的在线程序测评平台,本文档列出了其第一章的较好的练习题编号。Chapter...
更多相关标签: