BZOJ 2501: [usaco2010 Oct]Soda Machine

Description有N个人要去膜拜JZ,他们不知道JZ会出现在哪里,因此每个人有一个活动范围,只要JZ出现在这个范围内就能被膜拜, 伟大的JZ当然希望膜拜他的人越多越好,但是JZ不能分身,因此只能选择一个位置出现,他最多可以被多少人膜拜呢, 这个简单的问题JZ当然交给你了InputLine 1: A single integer: NLines 2..N+1: Line i+1 contains two space-separated integers: A_i and B_iOutputLine 1: A single integer representing the- 阅读剩余部分 -

BZOJ 2060: [Usaco2010 Nov]Visiting Cows 拜访奶牛

Description经过了几周的辛苦工作,贝茜终于迎来了一个假期.作为奶牛群中最会社交的牛,她希望去拜访N(1<=N<=50000)个朋友.这些朋友被标号为1..N.这些奶牛有一个不同寻常的交通系统,里面有N-1条路,每条路连接了一对编号为C1和C2的奶牛(1 <= C1 <= N; 1 <= C2 <= N; C1<>C2).这样,在每一对奶牛之间都有一条唯一的通路. FJ希望贝茜尽快的回到农场.于是,他就指示贝茜,如果对于一条路直接相连的两个奶牛,贝茜只能拜访其中的一个.当然,贝茜希望她的假期越长越好,所以她想知道她可以- 阅读剩余部分 -

BZOJ 2016: [Usaco2010]Chocolate Eating

Description贝西从大牛那里收到了N块巧克力。她不想把它们马上吃完,而是打算制定一个计划,使得在接下来的D天里,她能够尽量地快乐。贝西的快乐指数可以用一个整数来衡量,一开始的时候是0,当她每天晚上睡觉的时候,快乐指数会减半(奇数时向下取整)。贝西把她的巧克力按照收到的时间排序,并坚持按照这个顺序来吃巧克力。当她吃掉第i块巧克力的时候,她的快乐指数会增加Hj。每天可以吃任意多块巧克力,如何帮助贝西合理安排,使得D天内她的最小快乐指数最大呢?Input第一行:两个用空格分开的整数:N和D,1≤N.D≤50000第二行到第N+1行:第1+1行表示第i块巧克力提供的快乐指数- 阅读剩余部分 -

BZOJ 1828: [Usaco2010 Mar]balloc 农场分配

DescriptionInput第1行:两个用空格隔开的整数:N和M 第2行到N+1行:第i+1行表示一个整数C_i 第N+2到N+M+1行: 第i+N+1行表示2个整数 A_i和B_iOutput第一行: 一个整数表示最多能够被满足的要求数Sample Input5 4 1 3 2 1 3 1 3 2 5 2 3 4 5Sample Output3Solution按照右端点排序,然后以此能放则放,用线段树维护一下区间最小值。Code#include <queue> #include <cmath> #include <cstdio>- 阅读剩余部分 -

BZOJ 1776: [Usaco2010 Hol]cowpol 奶牛政坛

Description农夫约翰的奶牛住在N (2 <= N <= 200,000)片不同的草地上,标号为1到N。恰好有N-1条单位长度的双向道路,用各种各样的方法连接这些草地。而且从每片草地出发都可以抵达其他所有草地。也就是说,这些草地和道路构成了一种叫做树的图。输入包含一个详细的草地的集合,详细说明了每个草地的父节点P_i (0 <= P_i <= N)。根节点的P_i == 0, 表示它没有父节点。因为奶牛建立了1到K一共K (1 <= K <= N/2)个政党。每只奶牛都要加入某一个政党,其中, 第i只奶牛属于第A_i (1 <- 阅读剩余部分 -

BZOJ 1142: [POI2009]Tab

Description2个n*m矩阵,保证同一个矩阵中元素两两不同。问能否通过若干次交换两行或交换两列把第一个矩阵变成第二个。Input第一行正整数 T (1≤T≤10) 表示数据组数. 每组数据包括:第一行n m (1≤n,m≤1000) 2个n行m列的整数矩阵,元素绝对值均在10^6以内Output每组数据输出“TAK”/“NIE”表示能/不能.Sample Input2 4 3 1 2 3 4 5 6 7 8 9 10 11 12 11 10 12 8 7 9 5 4 6 2 1 3 2 2 1 2 3 4 5 6 7 8Sample OutputTAK NIESol- 阅读剩余部分 -

BZOJ 2086: [Poi2010]Blocks

Description给出N个正整数a[1..N],再给出一个正整数k,现在可以进行如下操作:每次选择一个大于k的正整数a[i],将a[i]减去1,选择a[i-1]或a[i+1]中的一个加上1。经过一定次数的操作后,问最大能够选出多长的一个连续子序列,使得这个子序列的每个数都不小于k。总共给出M次询问,每次询问给出的k不同,你需要分别回答。Input第一行两个正整数N (N <= 1,000,000)和M (M <= 50)。第二行N个正整数,第i个正整数表示a[i] (a[i] <= 10^9)。第三行M个正整数,第i个正整数表示第i次询问的k (k &- 阅读剩余部分 -

BZOJ 1734: [Usaco2005 feb]Aggressive cows 愤怒的牛

DescriptionFarmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,...,xN (0 <= xi <= 1,000,000,000). His C (2 <= C <= N) cows don't like this barn layout and become aggressive towards each oth- 阅读剩余部分 -

BZOJ 1642: [Usaco2007 Nov]Milking Time 挤奶时间

Description贝茜是一只非常努力工作的奶牛,她总是专注于提高自己的产量。为了产更多的奶,她预计好了接下来的N (1 ≤ N ≤ 1,000,000)个小时,标记为0..N-1。 Farmer John 计划好了 M (1 ≤ M ≤ 1,000) 个可以挤奶的时间段。每个时间段有一个开始时间(0 ≤ 开始时间 ≤ N), 和一个结束时间 (开始时间 < 结束时间 ≤ N), 和一个产量 (1 ≤ 产量 ≤ 1,000,000) 表示可以从贝茜挤奶的数量。Farmer John 从分别从开始时间挤奶,到结束时间为止。每次挤奶必须使用整个时间段。 但即使是贝茜也有- 阅读剩余部分 -

BZOJ 1668: [Usaco2006 Oct]Cow Pie Treasures 馅饼里的财富

Description最近,奶牛们热衷于把金币包在面粉里,然后把它们烤成馅饼。第i块馅饼中含有Ni(1<=Ni<=25)块金币,并且,这个数字被醒目地标记在馅饼表面。 奶牛们把所有烤好的馅饼在草地上排成了一个R行(1<=R<=100)C列(1<=C<=100)的矩阵。你现在站在坐标为(1,1)的馅饼边上,当然,你可以拿到那块馅饼里的所有金币。你必须从现在的位置,走到草地的另一边,在坐标为(R,C)的馅饼旁边停止走动。每做一次移动,你必须走到下一列的某块馅饼旁边,并且,行数的变动不能超过1(也就是说,如果现在你站在坐标为(r,c)的馅饼边上- 阅读剩余部分 -

BZOJ 594: [Usaco2008 Jan]猜数游戏

Description为了提高自己低得可怜的智商,奶牛们设计了一个新的猜数游戏,来锻炼她们的逻辑推理能力。 游戏开始前,一头指定的奶牛会在牛棚后面摆N(1 <= N<= 1,000,000)堆干草,每堆有若干捆,并且没有哪两堆中的草一样多。所有草堆排成一条直线,从左到右依次按1..N编号,每堆中草的捆数在1..1,000,000,000之间。 然后,游戏开始。另一头参与游戏的奶牛会问那头摆干草的奶牛 Q(1 <= Q <= 25,000)个问题,问题的格式如下: 编号为Ql..Qh(1 <= Ql <= Qh <= N)的草堆中,最- 阅读剩余部分 -

BZOJ 1593: [Usaco2008 Feb]Hotel 旅馆

Description奶牛们最近的旅游计划,是到苏必利尔湖畔,享受那里的湖光山色,以及明媚的阳光。作为整个旅游的策划者和负责人,贝茜选择在湖边的一家著名的旅馆住宿。这个巨大的旅馆一共有N (1 <= N <= 50,000)间客房,它们在同一层楼中顺次一字排开,在任何一个房间里,只需要拉开窗帘,就能见到波光粼粼的湖面。 贝茜一行,以及其他慕名而来的旅游者,都是一批批地来到旅馆的服务台,希望能订到D_i (1 <= D_i <= N)间连续的房间。服务台的接待工作也很简单:如果存在r满足编号为r..r+D_i-1的房间均空着,他就将这一批顾客安排到这些- 阅读剩余部分 -

BZOJ 1598: [Usaco2008 Mar]牛跑步

DescriptionBESSIE准备用从牛棚跑到池塘的方法来锻炼. 但是因为她懒,她只准备沿着下坡的路跑到池塘, 然后走回牛棚. BESSIE也不想跑得太远,所以她想走最短的路经. 农场上一共有M (1 <= M <= 10,000)条路, 每条路连接两个用1..N(1 <= N <= 1000)标号的地点. 更方便的是,如果X>Y,则地点X的高度大于地点Y的高度. 地点N是BESSIE的牛棚;地点1是池塘. 很快, BESSIE厌倦了一直走同一条路.所以她想走不同的路,更明确地讲,她想找出K (1 <= K <= 100)条不同- 阅读剩余部分 -