BZOJ 2097: [Usaco2010 Dec]Exercise 奶牛健美操

DescriptionFarmer John为了保持奶牛们的健康,让可怜的奶牛们不停在牧场之间 的小路上奔跑。这些奶牛的路径集合可以被表示成一个点集和一些连接 两个顶点的双向路,使得每对点之间恰好有一条简单路径。简单的说来, 这些点的布局就是一棵树,且每条边等长,都为1。 对于给定的一个奶牛路径集合,精明的奶牛们会计算出任意点对路径的最大值, 我们称之为这个路径集合的直径。如果直径太大,奶牛们就会拒绝锻炼。 Farmer John把每个点标记为1..V (2 <= V <= 100,000)。为了获得更加短 的直径,他可以选择封锁一些已经存在的道路,这样就可以得- 阅读剩余部分 -

BZOJ 3018: [Usaco2012 Nov]Distant Pastures

Description给定一个n×n的一个网格,每个格子有一个字符,要么是’(‘,要么是’)’。每个格子和它的上下左右的四个格子相邻,对于相邻的两个格子x和y,从x走到y的过程中,如果x和y中的字符相同,消耗A单位时间,如果x和y中字符不同,消耗B单位时间。定义点S到点T的时间为D(S,T),现在想请你求出网格中最大的D(S,T)。Input第一行三个整数n,A,B;接下来n行描述这个n×n的网格。1 <= n <= 30,1 <= A <= 1,000,000,1 <= B <= 1,000,000。Output一个整数,最大的D(S,- 阅读剩余部分 -

BZOJ 1673: [Usaco2005 Dec]Scales 天平

Description约翰有一架用来称牛的体重的天平.与之配套的是N(1≤N≤1000)个已知质量的砝码(所有砝码质量的数值都在31位二进制内).每次称牛时,他都把某头奶牛安置在天平的某一边,然后往天平另一边加砝码,直到天平平衡,于是此时砝码的总质量就是牛的质量(约翰不能把砝码放到奶牛的那边,因为奶牛不喜欢称体重,每当约翰把砝码放到她的蹄子底下,她就会尝试把砝码踢到约翰脸上).天平能承受的物体的质量不是无限的,当天平某一边物体的质量大于C(1≤C<230)时,天平就会被损坏. 砝码按照它们质量的大小被排成一行.并且,这一行中从第3个砝码开始,每个砝码的质量至少等- 阅读剩余部分 -

BZOJ 1774: [Usaco2009 Dec]Toll 过路费

Description跟所有人一样,农夫约翰以着宁教我负天下牛,休叫天下牛负我的伟大精神,日日夜夜苦思生 财之道。为了发财,他设置了一系列的规章制度,使得任何一只奶牛在农场中的道路行走,都 要向农夫约翰上交过路费。 农场中由N(1 <= N <= 250)片草地(标号为1到N),并且有M(1 <= M <= 10000)条 双向道路连接草地A_j和B_j(1 <= A_j <= N; 1 <= B_j <= N)。奶牛们从任意一片草 地出发可以抵达任意一片的草地。FJ已经在连接A_j和B_j的双向道路上设置一个过路费L_j (- 阅读剩余部分 -

BZOJ 3016: [Usaco2012 Nov]Clumsy Cows

Description给定长度为n的一个括号序列,每次修改可以修改一个位置的括号,若这个括号为’(‘,则修改为’)’,若这个括号为’)’,则修改为’(‘,问最少修改多少个使得原括号序列合法。其中:① ()是合法的;② 若A是合法的,则(A)是合法的;③ 若A,B都是合法的,则AB是合法的。Input一个长度为n个括号序列。Output最少的修改次数。Sample Input())(Sample Output2Solution维护一个栈,可以用计数器模拟。一个序列合法的话每个括号的前面所有括号,左括号要大于等于有括号。Code#include <- 阅读剩余部分 -

BZOJ 3433: [Usaco2014 Jan]Recording the Moolympics

Description给出n个区间[a,b).有2个记录器.每个记录器中存放的区间不能重叠.求2个记录器中最多可放多少个区间.InputLine 1: The integer N.Lines 2..1+N: Each line contains the start and end time of a single program (integers in the range 0..1,000,000,000).OutputLine 1: The maximum number of programs FJ can record.Sample Input6 0 3 6 7 3- 阅读剩余部分 -

BZOJ 3432: [Usaco2014 Jan]Cross Country Skiing

DescriptionN*M的格子,每个格子都有一个分值v,有的格子一定要经过.两个格子i,j可以互相到达,当且仅当它们有一条边重复(即上下左右方向),且abs(vi-vj)<=D.现在请求出最小的D的值。InputLine 1: The integers M and N.Lines 2..1+M: Each of these M lines contains N integer elevations.Lines 2+M..1+2M: Each of these M lines contains N values that are either 0 or 1, wit- 阅读剩余部分 -

BZOJ 3412: [Usaco2009 Dec]Music Notes乐谱

DescriptionInput第1行:两个整数N,Q.第2到N+1行:第i+l行只有一个整数Bi.第N+2到N+Q+I行:第N+i+l行只有一个整数Ti.Output第1到Q行:对与每个询问,在词问的时间内,奶牛敲击的是哪个音阶?Sample Input3 5 2 1 3 2 3 4 0 1Sample Output2 3 3 1 1Solution离线答案排下序,然后模拟一遍记录答案就可以了。Code#include <bits/stdc++.h> #define long long long using namespace std; inline void- 阅读剩余部分 -

BZOJ 3400: [Usaco2009 Mar]Cow Frisbee Team 奶牛沙盘队

Description农夫顿因开始玩飞盘之后,约翰也打算让奶牛们享受飞盘的乐趣.他要组建一只奶牛飞盘队.他的N(1≤N≤2000)只奶牛,每只部有一个飞盘水准指数Ri(1≤Ri≤100000).约翰要选出1只或多于1只奶牛来参加他的飞盘队.由于约翰的幸运数字是F(1≤F≤1000),他希望所有奶牛的飞盘水准指数之和是幸运数字的倍数.帮约翰算算一共有多少种组队方式.Input第1行输入N和F,之后N行输入Ri.Output组队方式数模10^8取余的结果.Sample Input4 5 1 2 8 2Sample Output3HINT组队方式有(2,3),(3,4),(1,2- 阅读剩余部分 -

BZOJ 4102: [Usaco2015 Open]Bessie

Description为了庆祝贝茜的生日,FJ给她吃草的自由. N块草地,标号1到N(1<=N<=1000),草地有营养价值.当贝茜走到这个草地,可以获得等于这块草地的营养价值的能量. 每块草地最多有10条双向边,每走一条边,贝茜花费E的能量. 贝茜拿可以从任何地方出发,当她不能获得更多的能量的时候她就会停止. 然而因为贝茜挑食,她每次不会吃低于或等于上次的营养价值的草地,所以她获得的能量是严格上升的,当然她可以选择只是经过一块草地而不吃草.算出贝茜能够获得的最大能量.Input第一排两个数 N和E剩下N排,每排包含Q,D两个数字,Q代表这个草地的营养价值,D代- 阅读剩余部分 -

BZOJ 3445: [Usaco2014 Feb] Roadblock

Description有一个无向图,共N个节点,编号1至N,共M条边。FJ在节点1,它想到达节点N。FJ总是会选择最短路径到达节点N。作为捣蛋的奶牛Bessie,它想尽量延迟FJ到达节点N的时间,于是Bessie决定从M条边之中选择某一条边,使得改边的长度变成原来的两倍,由于智商的问题,Bessie不知道选择加倍哪条边的长度才能使得FJ到达N号节点的时间最迟。注意:不管Bessie选择加倍哪条边的长度,FJ总是会从1号节点开始走最短路径到达N号点。Input第一行,两个整数N和M. 1 <=N<=250, 1<=M<=250000。 接下来有M行,每- 阅读剩余部分 -

BZOJ 3892: [Usaco2014 Dec]Marathon

Description在二维平面上有N个点,从(x1,y1)到(x2,y2)的代价为|x1-x2|+|y1-y2|。求从1号点出发,按从1到N的顺序依次到达每个点的最小总代价。你有K次机会可以跳过某个点,不允许跳过1号点或N号点。InputThe first line gives the values of N and K. The next N lines each contain two space-separated integers, x and y, representing a checkpoint (-1000 <= x <= 1000, -100- 阅读剩余部分 -