分类 前缀和 下的文章

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 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 1637: [Usaco2007 Mar]Balanced Lineup

题目描述Farmer John 决定给他的奶牛们照一张合影,他让 N (1 ≤ N ≤ 50,000) 头奶牛站成一条直线,每头牛都有它的坐标(范围: 0..1,000,000,000)和种族(0或1)。 一直以来 Farmer John 总是喜欢做一些非凡的事,当然这次照相也不例外。他只给一部分牛照相,并且这一组牛的阵容必须是“平衡的”。平衡的阵容,指的是在一组牛中,种族0和种族1的牛的数量相等。 请算出最广阔的区间,使这个区间内的牛阵容平衡。区间的大小为区间内最右边的牛的坐标减去最做边的牛的坐标。 输入中,每个种族至少有一头牛,没有两头牛的坐标相同。输入行 1: 一个整- 阅读剩余部分 -