BZOJ 1633: [Usaco2007 Feb]The Cow Lexicon 牛的词典

Description没有几个人知道,奶牛有她们自己的字典,里面的有W (1 ≤ W ≤ 600)个词,每个词的长度不超过25,且由小写字母组成.她们在交流时,由于各种原因,用词总是不那么准确.比如,贝茜听到有人对她说"browndcodw",确切的意思是"browncow",多出了两个"d",这两个"d"大概是身边的噪音. 奶牛们发觉辨认那些奇怪的信息很费劲,所以她们就想让你帮忙辨认一条收到的消息,即一个只包含小写字母且长度为L (2 ≤ L ≤ 300)的字符串.有些时候,这个字符串里会有多余的字母,你的任务就是找出最少去掉几个字母就可以使这个字符串变成准确的"牛语"(- 阅读剩余部分 -

BZOJ 1649: [Usaco2006 Dec]Cow Roller Coaster

Description奶牛们正打算造一条过山车轨道.她们希望你帮忙,找出最有趣,但又符合预算的方案. 过山车的轨道由若干钢轨首尾相连,由x=0处一直延伸到X=L(1≤L≤1000)处.现有N(1≤N≤10000)根钢轨,每根钢轨的起点Xi(0≤Xi≤L- Wi),长度wi(l≤Wi≤L),有趣指数Fi(1≤Fi≤1000000),成本Ci(l≤Ci≤1000)均己知.请确定一种最优方案,使得选用的钢轨的有趣指数之和最大,同时成本之和不超过B(1≤B≤1000).Input第1行输入L,N,B,接下来N行,每行四个整数Xi,wi,Fi,Ci.OutputLine 1: A - 阅读剩余部分 -

BZOJ 1638: [Usaco2007 Mar]Cow Traffic 奶牛交通

Description农场中,由于奶牛数量的迅速增长,通往奶牛宿舍的道路也出现了严重的交通拥堵问题.FJ打算找出最忙碌的道路来重点整治. 这个牧区包括一个由M (1 ≤ M ≤ 50,000)条单行道路(有向)组成的网络,以及 N (1 ≤ N ≤ 5,000)个交叉路口(编号为1..N),每一条道路连接两个不同的交叉路口.奶牛宿舍位于第N个路口.每一条道路都由编号较小的路口通向编号较大的路口.这样就可以避免网络中出现环.显而易见,所有道路都通向奶牛宿舍.而两个交叉路口可能由不止一条边连接. 在准备睡觉的时候,所有奶牛都从他们各自所在的交叉路口走向奶牛宿舍,奶牛只会在入度为- 阅读剩余部分 -

BZOJ 1672: [Usaco2005 Dec]Cleaning Shifts 清理牛棚

Description约翰的奶牛们从小娇生惯养,她们无法容忍牛棚里的任何脏东西.约翰发现,如果要使这群有洁癖的奶牛满意,他不得不雇佣她们中的一些来清扫牛棚, 约翰的奶牛中有N(1≤N≤10000)头愿意通过清扫牛棚来挣一些零花钱.由于在某个时段中奶牛们会在牛棚里随时随地地乱扔垃圾,自然地,她们要求在这段时间里,无论什么时候至少要有一头奶牛正在打扫.需要打扫的时段从某一天的第M秒开始,到第E秒结束f0≤M≤E≤86399).注意这里的秒是指时间段而不是时间点,也就是说,每天需要打扫的总时间是E-M+I秒. 约翰已经从每头牛那里得到了她们愿意接受的工作计划:对于某一头牛,她每天- 阅读剩余部分 -

BZOJ 1635: [Usaco2007 Jan]Tallest Cow 最高的牛

Description有n(1 <= n <= 10000)头牛从1到n线性排列,每头牛的高度为hi,现在告诉你这里面的牛的最大高度为maxH,而且有r组关系,每组关系输入两个数字,假设为a和b,表示第a头牛能看到第b头牛,能看到的条件是a, b之间的其它牛的高度都严格小于min(h[a], h[b]),而h[b] >= h[a]InputLine 1: Four space-separated integers: N, I, H and RLines 2..R+1: Two distinct space-separated integers A and - 阅读剩余部分 -

BZOJ 1615: [Usaco2008 Mar]The Loathesome Hay Baler麻烦的干草打包机

DescriptionFarmer John新买的干草打包机的内部结构大概算世界上最混乱的了,它不象普通的机器一样有明确的内部传动装置,而是,N (2 <= N <= 1050)个齿轮互相作用,每个齿轮都可能驱动着多个齿轮。 FJ记录了对于每个齿轮i,记录了它的3个参数:X_i,Y_i表示齿轮中心的位置坐标(-5000 <= X_i <= 5000; -5000 <= Y_i <= 5000);R_i表示该齿轮的半径(3 <= R_i <= 800)。驱动齿轮的位置为0,0,并且FJ也知道最终的工作齿轮位于X_t,Y_t。 驱- 阅读剩余部分 -

BZOJ 1619: [Usaco2008 Nov]Guarding the Farm 保卫牧场

Description农夫JOHN的农夫上有很多小山丘,他想要在那里布置一些保镖(……)去保卫他的那些相当值钱的奶牛们。 他想知道如果在一座小山丘上布置一名保镖的话,他总共需要招聘多少名保镖。他现在手头有一个用数字矩阵来表示地形的地图。这个矩阵有N行(1 < N < = 100)和M列( 1 < M < = 70) 。矩阵中的每个元素都有一个值H_ij(0 < = H_ij < =10,000)来表示该地区的海拔高度。请你帮助他统计出地图上到底有多少个小山丘。 小山丘的定义是:若地图中一个元素所邻接的所有元素都比这个元素高度要小(或它邻接- 阅读剩余部分 -

BZOJ 1688: [Usaco2005 Open]Disease Manangement 疾病管理

Description唉!一组D(1 .D <= 15)疾病(编号1 . D)在农场里运行。农夫约翰想要尽可能多的牛奶(1 <= N <= 1000)。如果挤奶的奶牛携带超过K(1 <= K <= D)不同的疾病,那么牛奶将被污染得太严重,必须完全丢弃。请帮助确定最大数量的奶牛而不需要丢弃牛奶。Input第一行:三个空格分隔的整数:N、D和K第2行。N+ 1:Line i+ 1 描述了牛i的疾病,列表中有一个或多个空格分隔的整数。第一个整数,d_i,是牛i病的计数;下一个d_i整数列举了实际的疾病。当然,如果d_i为0,列表是空的。Output- 阅读剩余部分 -

BZOJ 1232: [Usaco2008Nov]安慰奶牛cheer

DescriptionFarmer John变得非常懒, 他不想再继续维护供奶牛之间供通行的道路. 道路被用来连接N (5 <= N <= 10,000)个牧场, 牧场被连续地编号为1..N. 每一个牧场都是一个奶牛的家. FJ计划除去P(N-1 <= P <= 100,000)条道路中尽可能多的道路, 但是还要保持牧场之间的连通性. 你首先要决定那些道路是需要保留的N-1条道路. 第j条双向道路连接了牧场S_j和E_j (1 <= S_j <= N; 1 <= E_j <= N; S_j != E_j), 而且走完它需要L_- 阅读剩余部分 -

BZOJ 1230: [Usaco2008 Nov]lites 开关灯

DescriptionFarmer John尝试通过和奶牛们玩益智玩具来保持他的奶牛们思维敏捷. 其中一个大型玩具是牛栏中的灯. N (2 <= N <= 100,000) 头奶牛中的每一头被连续的编号为1..N, 站在一个彩色的灯下面.刚到傍晚的时候, 所有的灯都是关闭的. 奶牛们通过N个按钮来控制灯的开关; 按第i个按钮可以改变第i个灯的状态.奶牛们执行M (1 <= M <= 100,000)条指令, 每个指令都是两个整数中的一个(0 <= 指令号 <= 1). 第1种指令(用0表示)包含两个数字S_i和E_i (1 <= S- 阅读剩余部分 -

BZOJ 1634: [Usaco2007 Jan]Protecting the Flowers 护花

Description约翰留下他的N只奶牛上山采木.他离开的时候,她们像往常一样悠闲地在草场里吃草.可是,当他回来的时候,他看到了一幕惨剧:牛们正躲在他的花园里,啃食着他心爱的美丽花朵!为了使接下来花朵的损失最小,约翰赶紧采取行动,把牛们送回牛棚. 牛们从1到N编号.第i只牛所在的位置距离牛棚Ti(1≤Ti《2000000)分钟的路程,而在约翰开始送她回牛棚之前,她每分钟会啃食Di(1≤Di≤100)朵鲜花.无论多么努力,约翰一次只能送一只牛回棚.而运送第第i只牛事实上需要2Ti分钟,因为来回都需要时间. 写一个程序来决定约翰运送奶牛的顺序,使最终被吞食的花朵数量最小- 阅读剩余部分 -

BZOJ 1679: [Usaco2005 Jan]Moo Volume 牛的呼声

题目描述约翰的邻居鲍勃控告约翰家的牛们太会叫.约翰的N(1≤N≤10000)只牛在一维的草场上的不同地点吃着草.她们都是些爱说闲话的奶牛,每一只同时与其他N-1只牛聊着天.一个对话的进行,需要两只牛都按照和她们间距离等大的音量吼叫,因此草场上存在着N(N-1)/2个声音. 请计算这些音量的和.输入第1行输入N,接下来输入N个整数,表示一只牛所在的位置.输出一个整数,表示总音量.样例输入5 1 5 3 2 4样例输出40题解排个序简单搞一下就好了代码#include <cstdio> #include <algorithm> #define long- 阅读剩余部分 -

BZOJ 1660: [Usaco2006 Nov]Bad Hair Day 乱发节

题目描述输入Line 1: 牛的数量 N。Lines 2..N+1: 第 i+1 是一个整数,表示第i头牛的高度。输出Line 1: 一个整数表示c[1] 至 c[N]的和。样例输入6 10 3 7 4 12 2样例输出5代码#include <cstdio> #include <algorithm> using namespace std; const int N = 90001; int a[N], s[N], tp; int sum[N]; int main() { //freopen("input", "- 阅读剩余部分 -