下载文档原格式
背包问题译 by 铭（在中国，背包问题一般是这样描述的：设n个重量为（W1,W2,...Wn）的物品和一个载重为S的背包，将物品的一部分xi放进背包中的利润是Pixi，问如何选择物品的种类和数量，使得背包装满而获得最大的利润？另有一简化版本说：设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W1,W2,...Wn。
问能否从这n件物品中选择若干件放入此背包，使得放入的重量之和正好为S。
--译者加，不知道有没有班门弄斧之嫌）前提●贪心法（它是一种多步决策法，它总是作出在当前看来是最好的选择，它的考虑不是从整体出发，而只是某种意义上的局部最优，这样贪心法不能对所有问题达到整体最优解，但是对相当范围的许多问题都能够产生整体最优解。
--译者）●动态规划（它是将问题进行逐步的划分来缩小问题的规模，直到可以求出子问题的解为止。
分划子问题后，对应的子问题中含有大量的重复，这样就将重复地求解；在第一次遇到重复时把它解决，并将解保存起来，以备后面引用。
动态规划法常用来求一个问题在某种意义下的最优解。
--译者）●递归下降示例问题：用录音带录音农场主约翰最喜欢的爱好是制作一个Bessie喜欢的音乐合集磁带以便它在产奶时听。
Bessie的产奶量取决于它产奶时所听的歌曲。
已知一组歌曲（每首歌都由一对整数－－此曲的长度（以秒计），听该首歌时的产奶量来表示）以及给挤奶的总时间。
找到这样一组歌曲的集合，使得歌曲的总长度不超过给Bessie挤奶的总时间且使Bessie的产奶量达到最大。
抽象描述已知一组物品--每个都有其尺寸和值（比如，重量），以及可用的总空间。
找到这样一个集合，使得该集合的值的和最大，且其尺寸的和受某些限制所约束。
集合中任何一个特定的项目的总数目/尺寸不能超过它的可利用率。
解题想法视其为背包问题的一般方法是一个容量受限的背包使得放入其中的物品的值达到最大。
以上述问题为例，Bessie产奶时听的音乐带就是“背包”，而那些歌就是“放入背包中的物品”。
Wizard1.单调队列优化①土地并购(Land Acquisition,2008Mar)②干草塔(Tower of Hay,2009Open)③又买饲料(Buying Feed,2010Nov)④玉米实验(Cornfields,2003Mar)⑤修剪草坪(Mowing the Lawn,2011Open)2.树型①焊接(Soldering,2011Open)②产奶比赛(Milk Team Select,2006Mar)③道路重建(Rebuilding Roads,Feb2002)④手机网络(Cell Phone Network,2008Jan)3.背包问题续①电子游戏(Video Game Troubles,2009Dec)②最少找零(The Fewest Coins,2006Dec)③三个代表(Jersey Politics,2005Feb)④录制唱片(Raucous Rockers,1996Qualifying Round)4.背包问题①股票市场(Stock Market,2009Feb)②奶牛会展(Cow Exhibition,2003Fall)③太空电梯(Space Elevator,2005Mar)④平分子集(Subset Sums,1998Spring)5.区间型①提交作业(Turning in Homework,2004Open)②抢鲜草(Grazing on the Run,2005Nov)③最优回文(Cheapest Palindrome,2007Open)④智取金币(Treasure Chest,2010Dec)6.其他一①打扫食槽(Cleaning Up,2009Mar)②奶牛自行车队(Cow Cycling,Feb2002)③滑雪缆车(Ski Lift,2006Mar)④奶牛飞盘队(Cow Frisbee Team,2009Mar)7.其他二①滑雪比赛(Bobsledding,2009Dec)②滑雪课程(Ski Lessons,2009Open)③方形牛棚(Big Barn,1997Fall)④接住苹果(Apple Catching,2004Nov)⑤公司利润(Profits,2011Jan)土地并购(Land Acquisition,2008Mar)首先我们按长与宽都递减の排序，如果有一个矩形长宽都不如另一个矩形，那么可以忽略它。
在USACO比赛中，数论相关题目一直是考察的热点之一。
数论作为数学的一个重要分支，涉及整数的性质和关系，常常能够运用到算法设计和问题求解中。
本文将从简单到复杂，由浅入深地探讨USACO比赛中的数论相关题目，帮助你更深入地理解这一主题。
1. 简单级别：在USACO比赛的入门级题目中，通常会涉及一些基本的数论知识，比如素数、最大公约数、最小公倍数等。
给定两个整数，要求求它们的最大公约数或最小公倍数；或者判断一个数是否为素数等。
这些题目往往需要运用到基本的数论算法，比如欧几里得算法求最大公约数、筛法求素数等。
2. 中等级别：在中等级别的USACO比赛题目中，数论相关的内容会更加复杂和深刻。
可能涉及到模运算、同余方程、欧拉函数、费马小定理等知识点。
题目可能会要求实现一些高级的数论算法，比如快速幂算法、扩展欧几里得算法等。
这些题目往往需要更深入的数论知识和算法功底，能够更好地理解和运用复杂的数论知识。
3. 高级级别：在USACO比赛的高级题目中，数论相关的内容往往会与其他算法知识结合，考察的角度也更加灵活多样。
题目可能会涉及到数论与图论、动态规划、贪心算法等内容的结合，难度较大。
此时，除了对数论知识的深刻理解外，还需要具备较强的问题建模能力和算法设计能力。
总结回顾：通过以上的分析，我们可以看到，USACO比赛中的数论相关题目，涵盖了不同难度级别的内容，从简单的基本算法到复杂的高级问题解决方案，都需要对数论知识有较为全面、深刻的理解。
在备战USACO比赛时，我们要加强对数论知识的学习和掌握，尤其要注重基础知识的打牢和算法能力的提升。
个人观点和理解：我个人认为，数论是一门非常有趣和有挑战性的数学分支，在USACO 比赛中能够有机会运用数论知识解决实际问题，对于提高自己的数学建模能力和算法设计能力都是非常有益的。
我会在备战USACO比赛的过程中，加强对数论相关知识的学习和实践，努力提高自己的数论解题能力。
通过以上分析和讨论，我们对USACO比赛中的数论相关题目有了更全面、深刻的理解。
USACO 题解Chapter1Section 1.1Your Ride Is Here (ride)这大概是一个容易的问题，一个“ad hoc”问题，不需要特殊的算法和技巧。
Greedy Gift Givers (gift1)这道题的难度相当于联赛第一题。
用数组incom、outcom记录每个人的收入和支出，记录每个人的名字，对于送礼人i，找到他要送给的人j，inc(incom[j],outcom[i] div n)，其中n 是要送的人数，最后inc(incom[i],outcom[i] mod n)，最后输出incom[i]-outcom[i]即可。
（复杂度O(n^3)）。
用Hash表可以进行优化，降复杂度为O(n^2)。
Friday the Thirteenth (friday)按月为单位计算，模拟运算，1900年1月13日是星期六（代号1），下个月的13日就是代号(1+31-1) mod 7+1的星期。
因为数据小，所以不会超时。
当数据比较大时，可以以年为单位计算，每年为365天，mod 7的余数是1，就是说每过一年所有的日和星期错一天，闰年第1、2月错1天，3月以后错2天。
这样，只要先求出第一年的解，错位添加到以后的年即可。
详细分析：因为1900.1.1是星期一，所以1900.1.13就等于(13-1) mod7+1=星期六。
这样讲可能不太清楚。
那么，我来解释一下：每过7天是一个星期。
n天后是星期几怎么算呢？现在假设n是7的倍数，如果n为14，那么刚好就过了两个星期，所以14天后仍然是星期一。
但如果是过了15天，那么推算就得到是星期二。
这样，我们就可以推导出一个公式来计算。
(n天mod 7（一个星期的天数）+ 现在日期的代号) mod 7 就等于现在日期的代号。
当括号内的值为7的倍数时，其代号就为0，那么，此时就应该是星期日这样，我们可以得出题目的算法：int a[13]={0，31，28，31，30，31，30，31，31，30，31，30，31}int b[8]={0}a数组保存一年12个月的天数（因为C语言中数组起始下标为0，所以这里定义为13）。
动态规划练习【题目一览】总分【问题描述】学生在我们USACO的竞赛中的得分越多我们越高兴。
我们试着设计我们的竞赛以便人们能尽可能的多得分，这需要你的帮助。
我们可以从几个种类中选取竞赛的题目，这里的一个“种类”是指一个竞赛题目的集合，解决集合中的题目需要相同多的时间并且能得到相同的分数。
你的任务是写一个程序来告诉USACO的职员，应该从每一个种类中选取多少题目，使得解决题目的总耗时在竞赛规定的时间里并且总分最大。
输入包括竞赛的时间M（1<=M<=10000）（不要担心，你要到了训练营中才会有长时间的比赛）和“种类”的数目N（1<=N<=10000）。
后面的每一行将包括两个整数来描述一个“种类”：第一个整数说明解决这种题目能得的分数（1<=points<=10000），第二整数说明解决这种题目所需的时间（1<=minutes<=10000）。
你的程序应该确定我们应该从每个“种类”中选多少道题目使得能在竞赛的时间中得到最大的分数。
来自任意的“种类”的题目数目可能任何非负数（0或更多）。
计算可能得到的最大分数。
【输入格式】输入文件中的第1行：M，N--竞赛的时间和题目“种类”的数目。
第2～N+1行：两个整数：每个“种类”题目的分数和耗时。
【输出格式】输出文件中仅一行，包括那个在给定的限制里可能得到的最大的分数。
【输入输出样例】输入：300 4100 60250 120120 10035 20输出：605从第2个“种类”中选两题第4个“种类”中选三题。
邮票【问题描述】已知一个N枚邮票的面值集合（如，{1分，3分}）和一个上限K——表示信封上能够贴K张邮票。
计算从1到M的最大连续可贴出的邮资。
例如，假设有1分和3分的邮票；你最多可以贴5张邮票。
很容易贴出1到5分的邮资（用1分邮票贴就行了），接下来的邮资也不难：6 = 3 + 37 = 3 + 3 + 18 = 3 + 3 + 1 + 19 = 3 + 3 + 310 = 3 + 3 + 3 + 111 = 3 + 3 + 3 + 1 + 112 = 3 + 3 + 3 + 313 = 3 + 3 + 3 + 3 + 1然而，使用5枚1分或者3分的邮票根本不可能贴出14分的邮资。
USACO试题精选第一辑第1题利润(Profits, USACO 2011 Jan) (3)第2题购买饲料二(Buying Feed II, USACO 2010 Jan) (4)第3题奶牛杂技(Cow Acrobats, USACO 2006 Nov) (5)第4题抓苹果(Apple Catching, USACO 2004 Nov) (6)第5题抢购干草(Hay For Sale, USACO 2008 Dec) (7)第6题建造栅栏(Building A Fence, USACO 2008 Oct) (8)第7题建造道路(Building Roads, USACO 2007 Dec) (9)第8题青铜莲花池(Bronze Lilypad Pond, USACO 2007 Feb) (10)第9题滑雪课程(Ski Lessons, USACO 2009 Open) (11)第10题奶牛飞盘队(Cow Frisbee Team, USACO 2009 Mar) (12)第11题奶牛博览会(Cow Exhibition, USACO 2003 Fall) (13)第12题最近回文(Cheapest Palindrome, USACO 2007 Open) (14)第13题安慰奶牛(Cheering up the Cows, USACO 2008 Nov) (15)第14题玉米迷宫(Corn Maze, USACO 2011 Open) (16)第15题奶牛集会(MooFest, USACO 2004 Open) (17)第16题奶牛文字(Cowlphabet, USACO 2011 Feb) (18)第17题奶牛跨栏(Cow Hurdles, USACO 2007 Nov) (19)第18题工作安排(Work Scheduling, USACO 2009 Open) (20)第19题手机网络(Cell Phone Network, USACO 2008 Jan) (21)第20题提交作业(Turning in Homework, USACO 2004 Open) (22)第21题滑雪缆车(Ski Lift, USACO 2006 Mar) (23)第22题派发巧克力(Chocolate Giving, USACO 2010 Feb) (24)第23题赞助学费(Financial Aid, USACO 2004 Mar) (25)第24题白银莲花池(Silver Lilypad Pond, USACO 2007 Feb) (26)第25题地震(Earthquake, USACO 2001 Open) (27)第26题股票市场(Stock Market, USACO 2009 Feb) (28)第27题奶牛赛车(Cow Cycling, USACO Feb 2002) (29)第28题奶牛观光(Sightseeing Cows, USACO 2007 Dec) (30)第29题道路重建(Rebuilding Roads, USACO Feb 2002) (31)第30题奶牛接力(Cow Relays, USACO 2007 Nov) (32)第31题猜数游戏(Haybale Guessing, USACO 2008 Jan) (33)第32题混乱奶牛(Mixed Up Cows, USACO 2008 Nov) (34)第33题修剪草坪(Mowing the Lawn, USACO 2011 Open) (35)第34题道路翻新(Revamping Trails, USACO 2009 Feb) (36)第35题安排牧场(Corn Fields, USACO 2006 Nov) (37)第36题叠积木(Cube Stacking, USACO 2004 Open) (38)第37题奶牛抗议(Generic Cow Protests, USACO 2011 Feb) (39)第38题洞穴奶牛第一话(Cave Cow 1, USACO 2004 Open) (40)第39题打扫食槽(Cleaning Up, USACO 2009 Mar) (41)第40题购买饲料(Buying Feed, USACO 2010 Nov) (42)第41题土地并购(Land Acquisition, USACO 2008 Mar) (43)第42题干草塔(Tower of Hay, USACO 2009 Open) (44)第43题明星奶牛(Popular Cows, USACO 2003 Fall) (45)第44题电子游戏(Video Game Troubles, USACO 2009 Dec) (46)第45题产奶比赛(Milk Team Select, USACO 2006 Mar) (47)第46题黄金莲花池(Lilypad Pond, USACO 2007 Feb) (48)第47题逢低吸纳(BUY LOW, BUY LOWER, USACO Feb 2002) (49)第48题焊接(Soldering, USACO 2011 Open) (50)第49题旅馆(Hotel, USACO 2008 Feb) (51)第50题道路和航线(Roads and Planes, USACO 2011 Jan) (52)这一辑从USACO月赛中选择了质量很高的50题，是用来训练算法设计和实现的极好素材，如果初学者希望掌握比较扎实的基本功，我建议将这一辑的题目好好研究一下。
usaco题目集usaco题目集是一系列来自美国计算机奥林匹克竞赛（USACO）的编程题目。
USACO是一项面向中学生的计算机竞赛，旨在培养学生的计算机科学和算法设计能力。
该竞赛涵盖了广泛的主题，包括数据结构、图论、动态规划和搜索等。
usaco题目集的难度分为四个级别：铜牌、银牌、金牌和白金。
每个级别的题目都有一定的难度和要求。
通过完成这些题目，学生们可以提高他们的编程技巧和解决问题的能力。
usaco题目集的题目非常有趣和有挑战性。
每个题目都描述了一个具体的问题，学生需要设计和实现一个程序来解决这个问题。
这些问题有时与现实生活中的情境相关，有时与抽象的数学和逻辑问题相关。
例如，一个题目可能要求学生计算某个数列的前n项之和，另一个题目可能要求学生确定给定图形的面积。
解决这些问题需要学生们运用他们所学的算法和数据结构知识，并且具备良好的编程技巧。
usaco题目集的特点之一是其严格的评判标准。
每个题目都有一组测试数据，用于验证学生程序的正确性和效率。
程序需要在规定的时间内给出正确的输出结果，否则将被判定为错误。
这种评判标准旨在培养学生们高效率和准确性的编程能力。
通过解决usaco题目集中的问题，学生们可以提高他们的计算机科学能力，并为将来的学习和工作做好准备。
这些问题不仅可以让学生们巩固他们所学的知识，还可以培养他们的创造力和解决问题的能力。
此外，usaco题目集还提供了一个平台，让学生们可以与全美范围内的同龄人交流和竞争。
每年，usaco组织全美性的比赛，邀请来自各州的优秀选手进行角逐。
这些比赛不仅考察学生的编程能力，还促进了学生们之间的交流和合作。
总之，usaco题目集是一个很好的学习和提高编程能力的资源。
通过解决这些问题，学生们可以提高他们的计算机科学和算法设计能力，并为将来的学习和工作做好准备。
这些问题的多样性和挑战性，使得usaco题目集成为中学生们学习编程的重要工具。
USACO 2024J ANUARY C ONTEST ,G OLD P ROBLEM 1.W ALKINGINM ANHATTANFarmer John 和他的Q（1≤Q≤2×105）头奶牛在曼哈顿度假，但奶牛们逃跑了，现在正在城市里自由走动！曼哈顿很大——大到它的N（1≤N≤2×105）条道路在x-y 平面上无限延伸，但简单的是，这些道路都完全水平或垂直。
每条水平和垂直道路都可以用形式为y=c i 或x=c i 的方程表示，其中c i 是0到109范围内的整数。
Farmer John 准确地知道每头奶牛从哪里开始行走，以及她们多久之前逃跑的。
奶牛们很容易被预测，因此每头奶牛都是按照以下模式行走：她们只会以每秒一个单位的速度向北（+y）或向东（+x）行走。
如果她们当前在一条道路上，她们会继续沿着道路的方向行走。
如果她们在两条道路的交叉口处，如果她们行走了偶数秒，则向北行走，否则向东行走。
给定曼哈顿的布局以及每头奶牛的信息，帮助Farmer John 求出他的奶牛们现在在哪里！输入格式：输入的第一行包含N 和Q。
以下N 行描述道路。
每条道路由方向（H 或V）和坐标c i 表示。
输入保证道路各不相同。
以下Q 行描述奶牛。
每头奶牛由三个整数(x i ,y i ,d i )表示，意味着她们在d i 秒前从(x i ,y i )开始行走。
输入保证(x i ,y i )位于某条道路上，且0≤x i ,y i ,d i ≤109。
输出格式：输出Q 行，其中第i 行包含第i 头奶牛当前的位置。
输入样例：45V 7H 4H 5V 66310641065106610100410输出样例：7136156161104前两头奶牛经过的路径如下：(6,3)->(6,4)->(7,4)->(7,5)->(8,5)->...->(14,5)(6,4)->(6,5)->(7,5)->(7,6)->...->(7,13)测试点性质：∙测试点2-4：N,Q,c i ,x i ,y i ,d i ≤100。
【usaco2023 12月银组题解】一、题目概况1.1 题目背景12月份的usaco银级比赛是每年一度的重要赛事，题目难度适中，涵盖了很多经典算法和数据结构的应用。
1.2 题目数量本次比赛共包含5道题目，涉及动态规划、贪心算法、图论等多个领域。
二、题目详解2.1 第一题 - 最小差值本题要求给定一个包含n个正整数的数组，求该数组中两个元素的最小差值。
2.1.1 解题思路我们可以先对数组进行排序，然后遍历数组中相邻的两个元素，计算它们之间的差值，并更新最小差值。
2.1.2 代码实现```c++int minDiff(vector<int> nums) {sort(nums.begin(), nums.end());int minDiff = INT_MAX;for (int i = 1; i < nums.size(); i++) {minDiff = min(minDiff, nums[i] - nums[i-1]);}return minDiff;}```2.2 第二题 - 运动员配对本题要求给定一个包含n个正整数的数组，表示n个运动员的实力值，要求找出一种最优的配对方案，使得每对运动员的实力差值最小。
2.2.1 解题思路我们可以先对数组进行排序，然后使用双指针法找出实力差值最小的配对方案。
2.2.2 代码实现```c++int minP本人ring(vector<int> strength) {sort(strength.begin(), strength.end());int minDiff = INT_MAX;int l = 0, r = strength.size()-1;while (l < r) {minDiff = min(minDiff, strength[r] - strength[l]);l++;r--;}return minDiff;}```2.3 第三题 - 最小生成树本题给定一个无向连通图，要求求出该图的最小生成树的权值之和。
U S A C O题解(N O C O W整理版)-CAL-FENGHAI.-(YICAI)-Company One1USACO 题解Chapter1Section 1.1Your Ride Is Here (ride)这大概是一个容易的问题，一个“ad hoc”问题，不需要特殊的算法和技巧。
Greedy Gift Givers (gift1)这道题的难度相当于联赛第一题。
用数组incom、outcom记录每个人的收入和支出，记录每个人的名字，对于送礼人i，找到他要送给的人j，inc(incom[j],outcom[i] div n)，其中n是要送的人数，最后inc(incom[i],outcom[i] mod n)，最后输出incom[i]-outcom[i]即可。
（复杂度O(n^3)）。
用Hash表可以进行优化，降复杂度为O(n^2)。
Friday the Thirteenth (friday)按月为单位计算，模拟运算，1900年1月13日是星期六（代号1），下个月的13日就是代号(1+31-1) mod 7+1的星期。
因为数据小，所以不会超时。
当数据比较大时，可以以年为单位计算，每年为365天，mod 7的余数是1，就是说每过一年所有的日和星期错一天，闰年第1、2月错1天，3月以后错2天。
这样，只要先求出第一年的解，错位添加到以后的年即可。
详细分析：因为1900.1.1是星期一，所以1900.1.13就等于(13-1) mod7+1=星期六。
这样讲可能不太清楚。
那么，我来解释一下：每过7天是一个星期。
n 天后是星期几怎么算呢？现在假设n是7的倍数，如果n为14，那么刚好就过了两个星期，所以14天后仍然是星期一。
但如果是过了15天，那么推算就得到是星期二。
这样，我们就可以推导出一个公式来计算。
(n天 mod 7（一个星期的天数）+ 现在日期的代号) mod 7 就等于现在日期的代号。
当括号内的值为7的倍数时，其代号就为0，那么，此时就应该是星期日这样，我们可以得出题目的算法：int a[13]={0，31，28，31，30，31，30，31，31，30，31，30，31}int b[8]={0}a数组保存一年12个月的天数（因为C语言中数组起始下标为0，所以这里定义为13）。
水题6Barn Repair(Section 1.3)修理牛棚译by tim green在一个暴风雨的夜晚,农民约翰的牛棚的屋顶、门被吹飞了。
好在许多牛正在度假，所以牛棚没有住满。
剩下的牛一个紧挨着另一个被排成一行来过夜。
有些牛棚里有牛，有些没有。
所有的牛棚有相同的宽度。
自门遗失以后,农民约翰很快在牛棚之前竖立起新的木板。
他的新木材供应者将会供应他任何他想要的长度,但是供应者只能提供有限数目的木板。
农民约翰想将他购买的木板总长度减到最少。
给出M(1<= M<=50),可能买到的木板最大的数目;S(1<= S<=200),牛棚的总数;C(1 <= C <=S) 牛棚里牛的数目,和牛所在的牛棚的编号stall_number(1 <= stall_number <= S),计算拦住所有有牛的牛棚所需木板的最小总长度。
输出所需木板的最小总长度作为的答案。
PROGRAM NAME: barn1INPUT FORMATSAMPLE INPUT (file barn1.in)4 50 1834681415161721252627303140414243OUTPUT FORMAT单独的一行包含一个整数表示所需木板的最小总长度。
SAMPLE OUTPUT (file barn1.out)25[ 一种最优的安排是用板拦住牛棚3-8,14-21,25-31,40-43.]Number Triangles(Section 1.5)数字金字塔译by tim green考虑在下面被显示的数字金字塔。
写一个程序来计算从最高点开始在底部任意处结束的路径经过数字的和的最大。
每一步可以走到左下方的点也可以到达右下方的点。
73 88 1 02 7 4 44 5 2 6 5在上面的样例中,从7 到3 到8 到7 到5 的路径产生了最大和:30 PROGRAM NAME: numtriINPUT FORMAT第一个行包含R(1<= R<=1000) ,表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
所有的被供应的整数是非负的且不大于100。
SAMPLE INPUT (file numtri.in)573 88 1 02 7 4 44 5 2 6 5OUTPUT FORMAT单独的一行包含那个可能得到的最大的和。
SAMPLE OUTPUT (file numtri.out)30Subset Sums(Section 2.2)集合对于从1到N的连续整集合合，能划分成两个子集合，且保证每个集合的数字和是相等的。
举个例子，如果N=3，对于{1，2，3}能划分成两个子集合，他们每个的所有数字和是相等的：•{3} and {1,2}这是唯一一种分发（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）如果N=7，有四种方法能划分集合{1，2，3，4，5，6，7}，每一种分发的子集合各数字和是相等的:•{1,6,7} and {2,3,4,5} {注1+6+7=2+3+4+5}•{2,5,7} and {1,3,4,6}•{3,4,7} and {1,2,5,6}•{1,2,4,7} and {3,5,6}给出N，你的程序应该输出划分方案总数，如果不存在这样的划分方案，则输出0。
程序不能预存结果直接输出。
PROGRAM NAME: subsetINPUT FORMAT输入文件只有一行，且只有一个整数NSAMPLE INPUT (file subset.in)7OUTPUT FORMAT输出划分方案总数，如果不存在则输出0。
SAMPLE OUTPUT (file subset.out)4Longest Prefix(Section 2.3)最长前缀IOI'96译by Felicia Crazy在生物学中，一些生物的结构是用包含其要素的大写字母序列来表示的。
生物学家对于把长的序列分解成较短的（称之为元素的）序列很感兴趣。
如果一个集合P 中的元素可以通过串联（允许重复；串联，相当于Pascal 中的“+” 运算符）组成一个序列S ，那么我们认为序列S 可以分解为P 中的元素。
并不是所有的元素都必须出现。
举个例子，序列ABABACABAAB 可以分解为下面集合中的元素：{A, AB, BA, CA, BBC}序列S 的前面K 个字符称作S 中长度为K 的前缀。
设计一个程序，输入一个元素集合以及一个大写字母序列，计算这个序列最长的前缀的长度。
PROGRAM NAME: prefixINPUT FORMAT输入数据的开头包括1..200 个元素（长度为1..10 ）组成的集合，用连续的以空格分开的字符串表示。
字母全部是大写，数据可能不止一行。
元素集合结束的标志是一个只包含一个“.” 的行。
集合中的元素没有重复。
接着是大写字母序列S ，长度为1..200,000 ，用一行或者多行的字符串来表示，每行不超过76 个字符。
换行符并不是序列S 的一部分。
SAMPLE INPUT (file prefix.in)A AB BA CA BBCABABACABAABCOUTPUT FORMAT只有一行，输出一个整数，表示S 能够分解成P 中元素的最长前缀的长度。
SAMPLE OUTPUT (file prefix.out)11Cow Pedigrees(Section 2.3)奶牛家谱Silviu Ganceanu -- 2003译yangzhe1990农民约翰准备购买一群新奶牛。
在这个新的奶牛群中, 每一个母亲奶牛都生两小奶牛。
这些奶牛间的关系可以用二叉树来表示。
这些二叉树总共有N个节点(3 <= N < 200)。
这些二叉树有如下性质:1.每一个节点的度是0或2。
度是这个节点的孩子的数目。
2.树的高度等于K(1 < K < 100)。
高度是从根到任何叶子的最长的路径上的节点的数目; 叶子是指没有孩子的节点。
有多少不同的家谱结构? 如果一个家谱的树结构不同于另一个的, 那么这两个家谱就是不同的。
输出可能的家谱树的个数除以9901的余数。
PROGRAM NAME: nocowsINPUT FORMAT第1行: 两个空格分开的整数, N和K。
SAMPLE INPUT (file nocows.in)5 3OUTPUT FORMAT第 1 行: 一个整数，表示可能的家谱树的个数除以9901的余数。
SAMPLE OUTPUT (file nocows.out)2OUTPUT DETAILS:有5个节点，高为3的两个不同的家谱：@ @/ \ / \@ @ 和@ @/ \ / \@ @ @ @Money Systems(Section 2.3)货币系统译by timgreen母牛们不但创建了他们自己的政府而且选择了建立了自己的货币系统。
[In their own rebellious way],，他们对货币的数值感到好奇。
传统地，一个货币系统是由1,5,10,20 或25,50, 和100的单位面值组成的。
母牛想知道有多少种不同的方法来用货币系统中的货币来构造一个确定的数值。
举例来说, 使用一个货币系统{1,2,5,10,...}产生18单位面值的一些可能的方法是:18x1, 9x2, 8x2+2x1, 3x5+2+1,等等其它。
写一个程序来计算有多少种方法用给定的货币系统来构造一定数量的面值。
保证总数将会适合long long (C/C++) 和Int64 (Free Pascal)。
PROGRAM NAME: moneyINPUT FORMAT货币系统中货币的种类数目是V 。
(1<= V<=25)要构造的数量钱是N 。
(1<= N<=10,000)SAMPLE INPUT (file money.in)3 101 2 5OUTPUT FORMAT单独的一行包含那个可能的构造的方案数。
SAMPLE OUTPUT (file money.out)10Score Inflation(Section 3.1)总分译by timgreen学生在我们USACO的竞赛中的得分越多我们越高兴。
我们试着设计我们的竞赛以便人们能尽可能的多得分,这需要你的帮助。
我们可以从几个种类中选取竞赛的题目,这里的一个"种类"是指一个竞赛题目的集合,解决集合中的题目需要相同多的时间并且能得到相同的分数。
你的任务是写一个程序来告诉USACO的职员,应该从每一个种类中选取多少题目,使得解决题目的总耗时在竞赛规定的时间里并且总分最大。
输入包括竞赛的时间,M(1 <= M <= 10,000)(不要担心,你要到了训练营中才会有长时间的比赛)和N,"种类"的数目1 <= N <= 10,000。
后面的每一行将包括两个整数来描述一个"种类":第一个整数说明解决这种题目能得的分数(1 <= points <= 10000),第二整数说明解决这种题目所需的时间(1 <= minutes <= 10000)。
你的程序应该确定我们应该从每个"种类"中选多少道题目使得能在竞赛的时间中得到最大的分数。
来自任意的"种类"的题目数目可能任何非负数(0或更多)。
计算可能得到的最大分数。
PROGRAM NAME: inflateINPUT FORMATSAMPLE INPUT (file inflate.in)300 4100 60250 120120 10035 20OUTPUT FORMAT单独的一行包括那个在给定的限制里可能得到的最大的分数。
SAMPLE OUTPUT (file inflate.out)605{从第2个"种类"中选两题第4个"种类"中选三题}Stamps(Section 3.1)邮票译by Felicia Crazy已知一个N 枚邮票的面值集合（如，{1 分，3 分}）和一个上限K —— 表示信封上能够贴K 张邮票。
计算从1 到M 的最大连续可贴出的邮资。
例如，假设有1 分和3 分的邮票；你最多可以贴5 张邮票。
很容易贴出1 到5 分的邮资（用1 分邮票贴就行了），接下来的邮资也不难：• 6 = 3 + 3•7 = 3 + 3 + 1•8 = 3 + 3 + 1 + 1•9 = 3 + 3 + 3•10 = 3 + 3 + 3 + 1•11 = 3 + 3 + 3 + 1 + 1•12 = 3 + 3 + 3 + 3•13 = 3 + 3 + 3 + 3 + 1。
