usaco2007专题

bzoj1690/poj3621[Usaco2007 Dec]奶牛的旅行

题目链接：bzoj poj 题目大意：有N 个景点，参观第i 个景点会给奶牛带来Fi 点欢乐度。景点间有M 条道路，道路都是单行道，第i 条道路从Si 开始通向Ti，长度为Li。奶牛们可以选择从任意一个景点出发，在晚上结束的时候，奶牛必须回到这个起点和约翰汇合。奶牛们想让欢乐度尽量大，但经讨厌走路，所以需要设计一条游览线路。定义一条游览线路的“欢乐指数”为该线路上所有景点的欢乐度之和与路

bzoj1697[Usaco2007 Feb] Cow Sorting牛排序

题目链接：bzoj1697 题目大意： N（1 <= N <= 10,000）头牛排队。农夫想把牛按脾气的大小排序（从小到大）。每一头牛的脾气都是一个在1到100，000之间的整数并且没有两头牛的脾气值相同。在排序过程中，可以交换任意两头牛的位置。需要X+Y秒来交换脾气值为X和Y的两头牛。求把所有牛排好序的最短时间。题解：置换跟bzoj1119差不多 #include<cstdi

bzoj 1690: [Usaco2007 Dec]奶牛的旅行

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1690 思路：0-1分数规划其实0-1分数规划重要的是它的思想，就像最小乘积XXX（生成树，匹配等）一样，知道了思想，再套一个对应的的算法即可一个不错的博客：http://www.cnblogs.com/perseawe/archive/2012/05/03/01fsgh.html

$[Usaco2007 Jan]Running贝茜的晨练计划$

[Usaco2007 Jan]Running贝茜的晨练计划

题目描述奶牛们打算通过锻炼来培养自己的运动细胞，作为其中的一员，贝茜选择的运动方式是每天进行N(1 <= N <= 10,000)分钟的晨跑。在每分钟的开始，贝茜会选择下一分钟是用来跑步还是休息。贝茜的体力限制了她跑步的距离。更具体地，如果贝茜选择在第i分钟内跑步，她可以在这一分钟内跑D_i(1 <= D_i <= 1,000)米，并且她的疲劳度会增加 1。不过，无论何时贝茜的疲劳度都

[Usaco2007 Jan]Qualified Primes合格的素数

[Usaco2007 Jan]Qualified Primes合格的素数时间限制: 1 Sec 内存限制: 128 MB 题目描述求A..B之间包含数字D的素数个数。(1<=A<=B<=4000000,B<=A+1000000) 输入 1行，三个整数A,B,D 输出 1个整数，满足条件的素数个数样例输入 10 15 3 样例输出 1 varv:string;c,d:c

[Poj 3268][Usaco2007 Feb]Cow Party奶牛派对

[Usaco2007 Feb]Cow Party奶牛派对时间限制: 1 Sec 内存限制: 128 MB 题目描述农场有N(1≤N≤1000)个牛棚，每个牛棚都有1只奶牛要参加在X牛棚举行的奶牛派对．共有M(1≤M≤100000)条单向路连接着牛棚，第i条踣需要Ti的时间来通过．牛们都很懒，所以不管是前去X牛棚参加派对还是返回住所，她们都采用了用时最少的路线．那么，用时最多的奶牛需要多少

[BZOJ1699][Usaco2007 Jan]Balanced Lineup排队

[Usaco2007 Jan]Balanced Lineup排队时间限制: 1 Sec 内存限制: 128 MB 题目描述每天,农夫 John 的N(1 <= N <= 50,000)头牛总是按同一序列排队. 有一天, John 决定让一些牛们玩一场飞盘比赛. 他准备找一群在对列中为置连续的牛来进行比赛. 但是为了避免水平悬殊,牛的身高不应该相差太大. John 准备了Q (1 <= Q

[BZOJ1634] [Usaco2007 Jan]Protecting the Flowers 护花

[Usaco2007 Jan]Protecting the Flowers 护花 Description Farmer John went to cut some wood and left N (2 <= N <= 100,000) cows eating the grass, as usual. When he returned, he found to his horror that t

[BZOJ1646] [Usaco2007 Open]Catch That Cow 抓住那只牛

传送门 http://www.lydsy.com/JudgeOnline/problem.php?id=1646 题目大意给定两个点,从一个点走到另一个点的最小时间每秒可以从x走到2*x,x-1或x+1 题解裸的BFS,注意位置可以在0 varx,t:array[0..100005]of longint;i,j,k:longint;n,m,head,tail,v:longint

1641: [Usaco2007 Nov]Cow Hurdles 奶牛跨栏

Description Farmer John 想让她的奶牛准备郡级跳跃比赛，贝茜和她的伙伴们正在练习跨栏。她们很累，所以她们想消耗最少的能量来跨栏。显然，对于一头奶牛跳过几个矮栏是很容易的，但是高栏却很难。于是，奶牛们总是关心路径上最高的栏的高度。奶牛的训练场中有 N (1 ≤ N ≤ 300) 个站台，分别标记为1..N。所有站台之间有M (1 ≤ M ≤ 25,000)条单向路径，第

【BZOJ1713】[Usaco2007 China]The Bovine Accordion and Banjo Orchestra 音乐会斜率优化

【BZOJ1713】[Usaco2007 China]The Bovine Accordion and Banjo Orchestra 音乐会 Description Input 第1行输入N，之后N行输入Ai，之后N行输入Bi． Output 输出最大收益． Sample Input 3 1 1 5 5 1 1 INPUT DETAILS: There a

[Usaco2007 Jan]Running贝茜的晨练计划

奶牛们打算通过锻炼来培养自己的运动细胞，作为其中的一员，贝茜选择的运动方式是每天进行N(1 <= N <= 10,000)分钟的晨跑。在每分钟的开始，贝茜会选择下一分钟是用来跑步还是休息。贝茜的体力限制了她跑步的距离。更具体地，如果贝茜选择在第i分钟内跑步，她可以在这一分钟内跑D_i(1 <= D_i <= 1,000)米，并且她的疲劳度会增加 1。不过，无论何时贝茜的疲劳度都不能超过M(

BZOJ1696: [Usaco2007 Feb]Building A New Barn新牛舍

n<=10000个点(xi,yi)，找到一个不同于给出的所有点的点，使得该点到所有点的曼哈顿距离最小并找出这样的点的个数。第一眼看上去这不是中位数嘛，奇数一个点偶数一片，然后找一下这篇区域有几个不符合的点即可。不过要找出“不同于给出的点”的点，那万一中位数那个点被占了，就找它四周四个点即可。错误！明知道会有中位数那一个点被占了，那怎么就不考虑四周都被占了的情况？不过可以肯定的是，离中位数越

bzoj 1696: [Usaco2007 Feb]Building A New Barn新牛舍 ——中位数排序

Description 经过多年的积蓄，农夫JOHN决定造一个新的牛舍。他知道所有N(2 <= N <= 10,000)头牛的吃草位置，所以他想把牛舍造在最方便的地方。每一头牛吃草的位置是一个整数点(X_i, Y_i) (-10,000 <= X_i <= 10,000; -10,000 <= Y_i <= 10,000)。没有两头牛的吃草位置是相邻的。 JOHN决定把牛舍造在一个没有牛吃

Bzoj 1696: [Usaco2007 Feb]Building A New Barn新牛舍中位数,数学

1696: [Usaco2007 Feb]Building A New Barn新牛舍 Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 394 Solved: 181[Submit][Status][Discuss] Description 经过多年的积蓄，农夫JOHN决定造一个新的牛舍。他知道所有N(2 <= N <= 10,000)头牛的吃

BZOJ 1691 [Usaco2007 Dec]挑剔的美食家

Description 与很多奶牛一样，Farmer John那群养尊处优的奶牛们对食物越来越挑剔，随便拿堆草就能打发她们午饭的日子自然是一去不返了。现在，Farmer John不得不去牧草专供商那里购买大量美味多汁的牧草，来满足他那N(1 <= N <= 100,000)头挑剔的奶牛。所有奶牛都对FJ提出了她对牧草的要求：第i头奶牛要求她的食物每份的价钱不低于A_i(1 <= A_i <=