分类 二分 下的文章

BZOJ 1014: [JSOI2008]火星人prefix

Solution用 Splay 维护区间 hash 值,然后每次二分长度即可。需要注意的就是这道题的哈希方式,如果想要支持合并操作,需要这么哈希:cur->hash = ls->hash + convert(cur->val) * base[ls->size] + base[ls->size+1] * rs->hash;可以发现每次是左儿子的哈希值 + 自身的值乘左儿子的大小 + 右儿子的哈希值乘上(左儿子大小+1)。这么做我们可以发现,每个数最终都会乘上比自己编号小的点数 - 1。所以树的结构不影响哈希值,就可以放心的用 splay 维- 阅读剩余部分 -

BZOJ 1733: [Usaco2005 feb]Secret Milking Machine 神秘的挤奶机

Description约翰正在制造一台新型的挤奶机,但他不希望别人知道.他希望尽可能久地隐藏这个秘密.他把挤奶机藏在他的农场里,使它不被发现.在挤奶机制造的过程中,他需要去挤奶机所在的地方T(1≤T≤200)次.他的农场里有秘密的地道,但约翰只在返回的时候用它.农场被划分成N(2≤N≤200)块区域,用1到200标号.这些区域被P(1≤P≤40000)条道路连接,每条路有一个小于10^6的长度L.两块区域之间可能有多条道路连接.为了减少被发现的可能,约翰不会两次经过农场上的任何一条道路.当然了,他希望走最短的路. 请帮助约翰寻找这T次从仓库走到挤奶机所在地的路线.仓库是区域- 阅读剩余部分 -

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

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

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 2016: [Usaco2010]Chocolate Eating

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

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 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 1614: [Usaco2007 Jan]Telephone Lines架设电话线

题目描述Farmer John打算将电话线引到自己的农场,但电信公司并不打算为他提供免费服务。于是,FJ必须为此向电信公司支付一定的费用。 FJ的农场周围分布着N(1 <= N <= 1,000)根按1..N顺次编号的废弃的电话线杆,任意两根电话线杆间都没有电话线相连。一共P(1 <= P <= 10,000)对电话线杆间可以拉电话线,其余的那些由于隔得太远而无法被连接。 第i对电话线杆的两个端点分别为A_i、B_i,它们间的距离为 L_i (1 <= L_i <= 1,000,000)。数据中保证每对{A_i,B_i}最多只出现1次。编- 阅读剩余部分 -

BZOJ 3343: 教主的魔法

题目描述教主最近学会了一种神奇的魔法,能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起,这次他们排成了一列,被编号为1、2、……、N。每个人的身高一开始都是不超过1000的正整数。教主的魔法每次可以把闭区间[L, R](1≤L≤R≤N)内的英雄的身高全部加上一个整数W。(虽然L=R时并不符合区间的书写规范,但我们可以认为是单独增加第L(R)个英雄的身高)CYZ、光哥和ZJQ等人不信教主的邪,于是他们有时候会问WD闭区间 [L, R] 内有多少英雄身高大于等于C,以验证教主的魔法是否真的有效。WD巨懒,于是他把这个回答的任务交给了你。输- 阅读剩余部分 -