usaco2008专题

BZOJ 1601 [Usaco2008 Oct]灌水题解与分析

1601: [Usaco2008 Oct]灌水 Time Limit: 5 Sec Memory Limit: 162 MB Description Farmer John已经决定把水灌到他的n(1<=n<=300)块农田，农田被数字1到n标记。把一块土地进行灌水有两种方法，从其他农田饮水，或者这块土地建造水库。建造一个水库需要花费wi(1<=wi<=10

bzoj1593[Usaco2008 Feb]Hotel旅馆

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1593 题目大意：有一家著名旅馆，这家旅馆一共有N 间客房，都在同一楼层，一字顺序排开。旅店前台的工作是忙碌的，他们需要处理订房请求和退房请求。有订房请求的游客会要求预定一段连续的房间。如果能够满足客户的要求，前台总会尽量满足，如果有多处连续的空房可供预定，前台会挑选编号最靠前的优先

bzoj1594[Usaco2008 Jan]Haybale Guessing猜数游戏

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1594 题目大意： N个数排成一列，有q个询问。每个询问告诉你区间[l,r]的最小值是多少(这N个数各不相同)。问你这q个询问有没有矛盾，有的话从哪里开始有矛盾。题解：二分+线段树有人用神奇姿势の并查集来代替线段树来搞..但是我不懂QwQ 于是我就打了线段树。。代码迷の长&

bzoj1601[Usaco2008 Oct]灌水(最小生成树）

展开题目背景 John的农场缺水了！！！题目描述 Farmer John has decided to bring water to his N (1 <= N <= 300) pastures which are conveniently numbered 1…N. He may bring water to a pasture either by building a well in t

BZOJ1231: [Usaco2008 Nov]mixup2 混乱的奶牛（状压DP）

Description 混乱的奶牛 [Don Piele, 2007] Farmer John的N(4 <= N <= 16)头奶牛中的每一头都有一个唯一的编号S_i (1 <= S_i <= 25,000). 奶牛为她们的编号感到骄傲, 所以每一头奶牛都把她的编号刻在一个金牌上, 并且把金牌挂在她们宽大的脖子上. 奶牛们对在挤奶的时候被排成一支"混乱"的队伍非常反感. 如果一个队伍里任意两头相邻

1624: [Usaco2008 Open] Clear And Present Danger 寻宝之路

floyd跑出最短路后按a顺序相加即可 #include<bits/stdc++.h>#define rep(i,x,y) for(register int i =x ;i <= y; ++ i)#define repd(i,x,y) for(register int i = x; i >= y ; -- i)using namespace std;template<typename T

【bzoj1624】【Usaco2008 Open】【 Clear And Present Danger 寻宝之路】【最短路】

Description 农夫约翰正驾驶一条小艇在牛勒比海上航行．海上有N(1≤N≤100)个岛屿，用1到N编号．约翰从1号小岛出发，最后到达N号小岛．一张藏宝图上说，如果他的路程上经过的小岛依次出现了Ai，A2，…，AM(2≤M≤10000)这样的序列（不一定相邻），那他最终就能找到古老的宝藏．但是，由于牛勒比海有海盗出没．约翰知道任意两个岛屿之间的航线上海盗

bzoj1597: [Usaco2008 Mar]土地购买

1597: [Usaco2008 Mar]土地购买 Time Limit: 10 Sec Memory Limit: 162 MB Description 农夫John准备扩大他的农场,他正在考虑N (1 <= N <= 50,000) 块长方形的土地. 每块土地的长宽满足(1 <= 宽 <= 1,000,000; 1 <= 长 <= 1,000,000). 每块土地的价格是它的面积,但FJ

[BZOJ 1597][Usaco2008 Mar]土地购买：DP斜率优化

点击这里查看原题按X坐标排序，若有某个点X,Y坐标均小于另一个点，则删去该点。首先可以写出DP方程： f[i]=min{f[j]+x[i]*y[j+1]} 这个方程可以用斜率优化，由此维护一个下凸壳即可得解，注意，不等式移负数项时要变号： (f[j]-f[k])/(y[k+1]-y[j+1]) /*User:SmallLanguage:C++Problem No.

[BZOJ 1231][Usaco2008 Nov]mixup2 混乱的奶牛：状压DP

点击这里查看原题 f[i][j]表示状态为i，以奶牛j结尾的情况数 /*User:SmallLanguage:C++Problem No.:1231*/#include<bits/stdc++.h>#define ll long long#define inf 999999999using namespace std;const int M=(1<<16)+5;int a[

[BZOJ1622] [Usaco2008 Open]Word Power 名字的能量

[Usaco2008 Open]Word Power 名字的能量 Description 约翰想要计算他那N(1≤N≤1000)只奶牛的名字的能量．每只奶牛的名字由不超过1000个字待构成，没有一个名字是空字体串，约翰有一张“能量字符串表”，上面有M(1≤M≤100)个代表能量的字符串．每个字符串由不超过30个字体构成，同样不存在空字符串．一个奶牛的名字蕴含多少个能量字符串，这个名字就有多少

[BZOJ1607] [Usaco2008 Dec]Patting Heads 轻拍牛头

[Usaco2008 Dec]Patting Heads 轻拍牛头 Description 今天是贝茜的生日，为了庆祝自己的生日，贝茜邀你来玩一个游戏．贝茜让N(1≤N≤100000)头奶牛坐成一个圈．除了1号与N号奶牛外，i号奶牛与i-l号和i+l号奶牛相邻．N号奶牛与1号奶牛相邻．农夫约翰用很多纸条装满了一个桶，每一张包含了一个独一无二的1到1,000,000的数字．接着每一头奶牛

[Usaco2008 Nov]mixup2 混乱的奶牛简单状压DP

混乱的奶牛 [Don Piele, 2007] Farmer John的N(4 <= N <= 16)头奶牛中的每一头都有一个唯一的编号S_i (1 <= S_i <= 25,000). 奶牛为她们的编号感到骄傲, 所以每一头奶牛都把她的编号刻在一个金牌上, 并且把金牌挂在她们宽大的脖子上. 奶牛们对在挤奶的时候被排成一支"混乱"的队伍非常反感. 如果一个队伍里任意两头相邻的奶牛的编号相差超过

[Usaco2008 Mar]River Crossing渡河问题简单DP

Farmer John以及他的N(1 <= N <= 2,500)头奶牛打算过一条河，但他们所有的渡河工具，仅仅是一个木筏。由于奶牛不会划船，在整个渡河过程中，FJ必须始终在木筏上。在这个基础上，木筏上的奶牛数目每增加1，FJ把木筏划到对岸就得花更多的时间。当FJ一个人坐在木筏上，他把木筏划到对岸需要M(1 <= M <= 1000)分钟。当木筏搭载的奶牛数目从i-1增加到i时，FJ得多

[Usaco2008 Nov]lites 开关灯线段树区间异或及求和操作

Farmer John尝试通过和奶牛们玩益智玩具来保持他的奶牛们思维敏捷. 其中一个大型玩具是牛栏中的灯. N (2 <= N <= 100,000) 头奶牛中的每一头被连续的编号为1..N, 站在一个彩色的灯下面.刚到傍晚的时候, 所有的灯都是关闭的. 奶牛们通过N个按钮来控制灯的开关; 按第i个按钮可以改变第i个灯的状态.奶牛们执行M (1 <= M <= 100,000)条指令, 每个

[Usaco2008 Oct]笨重的石子 DP

贝西喜欢棋盘游戏和角色扮演类游戏所以她说服Farmer John把她带到玩具店，在那里，她购买了三个不同的骰子，这三个质量均匀的骰子，分别有S1,S2,S3个面。(2 <= S1 <= 20; 2 <= S2 <= 20; 2 <= S3 <= 40). 贝西掷啊掷啊掷啊，想要知道出现几率最大的和是多少。问题给出三个骰子的面数，让你求出出现几率最大的和是多少。如果有很多种和出现的几率相同，那么就

[Usaco2008 Oct]灌水最小生成树

Farmer John已经决定把水灌到他的n(1<=n<=300)块农田，农田被数字1到n标记。把一块土地进行灌水有两种方法，从其他农田饮水，或者这块土地建造水库。建造一个水库需要花费wi(1<=wi<=100000),连接两块土地需要花费Pij(1<=pij<=100000,pij=pji,pii=0). 计算Farmer John所需的最少代价。看起来挺难？其实稍微有点变

[Usaco2008 Mar]土地购买斜率优化的DP

农夫John准备扩大他的农场,他正在考虑N (1 <= N <= 50,000) 块长方形的土地. 每块土地的长宽满足(1 <= 宽 <= 1,000,000; 1 <= 长 <= 1,000,000). 每块土地的价格是它的面积,但FJ可以同时购买多快土地. 这些土地的价格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换. 如果FJ买一块3x5的地和一块5x3的地,则他需要付5x5

筛-BZOJ-1607-[Usaco2008 Dec]Patting Heads 轻拍牛头

Description 今天是贝茜的生日，为了庆祝自己的生日，贝茜邀你来玩一个游戏．贝茜让N(1≤N≤100000)头奶牛坐成一个圈．除了1号与N号奶牛外，i号奶牛与i-l号和i+l号奶牛相邻．N号奶牛与1号奶牛相邻．农夫约翰用很多纸条装满了一个桶，每一张包含了一个独一无二的1到1,000,000的数字．接着每一头奶牛i从柄中取出一张纸条Ai．每头奶牛轮流走上一圈，同时拍打所有编号能整除

BFS-BZOJ-1602-[Usaco2008 Oct]牧场行走

Description N头牛（2<=n<=1000）别人被标记为1到n，在同样被标记1到n的n块土地上吃草，第i头牛在第i块牧场吃草。这n块土地被n-1条边连接。奶牛可以在边上行走，第i条边连接第Ai，Bi块牧场，第i条边的长度是Li（1<=Li<=10000）。这些边被安排成任意两头奶牛都可以通过这些边到达的情况，所以说这是一棵树。这些奶牛是非常喜欢交际的，经常会去互相访问,他们想让

Kruskal-BZOJ-1601- [Usaco2008 Oct]灌水

Description Farmer John已经决定把水灌到他的n(1<=n<=300)块农田，农田被数字1到n标记。把一块土地进行灌水有两种方法，从其他农田饮水，或者这块土地建造水库。建造一个水库需要花费wi(1<=wi<=100000),连接两块土地需要花费Pij(1<=pij<=100000,pij=pji,pii=0). 计算Farmer John所需的最少代价。 Input *

DP-BZOJ-1600- [Usaco2008 Oct]建造栅栏

Description 勤奋的Farmer John想要建造一个四面的栅栏来关住牛们。他有一块长为n（4<=n<=2500）的木板，他想把这块本板切成4块。这四块小木板可以是任何一个长度只要Farmer John能够把它们围成一个合理的四边形。他能够切出多少种不同的合理方案。注意：只要大木板的切割点不同就当成是不同的方案（像全排列那样），不要担心另外的特殊情况，go ahead。栅栏的面积要