二分法 - Page 6

「BZOJ2144」跳跳棋
Description跳跳棋是在一条数轴上进行的。棋子只能摆在整点上。每个点不能摆超过一个棋子。我们用跳跳棋来做一个简单的游戏：棋盘上有3颗棋子，分别在a，b，c这三个位置。我们要通过最少的跳动把他们的位置移动成x，y，z。（棋子是没有区别的）跳动的规则很简单，任意选一颗棋子，对一颗中轴棋子跳动。跳动后两颗棋子距离不变。一次只允许跳过1颗棋子。写一个程序，首先判断是否可以完成任务。如果可以，输出最少需要的跳动次数。...
02014年10月22日8,078二分法,最近公共祖先

「BZOJ2016」[Usaco2010] Chocolate Eating
Description贝西从大牛那里收到了N块巧克力。她不想把它们马上吃完，而是打算制定一个计划，使得在接下来的D天里，她能够尽量地快乐。贝西的快乐指数可以用一个整数来衡量，一开始的时候是0，当她每天晚上睡觉的时候，快乐指数会减半（奇数时向下取整）。贝西把她的巧克力按照收到的时间排序，并坚持按照这个顺序来吃巧克力。当她吃掉第i块巧克力的时候，她的快乐指数会增加Hj。每天可以吃任意多块巧克力，如何帮助贝西合理安排...
12014年10月21日3,822贪心,二分法
「codecomb2093」牛宫
DescriptionHzgd神牛准备给自己盖一座很华丽的宫殿。于是，他看中了一块N*M的矩形空地。空地中每个格子都有自己的海拔高度。胡张想让他的宫殿的平均海拔在海平面之上（假设海平面的高度是0，平均数都会算吧？）。而且，胡张希望他的宫殿是个矩形且尽量大，能够容纳更多的人来膜拜他。请问胡张的宫殿最后会有多大？Input Format第一行为N和M。之后N行，每行M个数，描述的空地的海拔。Output Format输出一行,表示宫殿最...
02014年10月15日3,760二分法,单调栈
「NOIP模拟赛」比赛
「问题描述」有两个队伍A和B，每个队伍都有n个人。这两支队伍之间进行n场1对1比赛，每一场都是由A中的一个选手与B中的一个选手对抗。同一个人不会参加多场比赛，每个人的对手都是随机而等概率的。例如A队有A1和A2两个人，B队有B1和B2两个人，那么(A1vsB1,A2vsB2)和(A1vsB2,A2vsB1)的概率都是均等的50%。每个选手都有一个非负的实力值。如果实力值为X和Y的选手对抗，那么实力值较强的选手所在的队伍将会获得(X...
02014年10月6日3,616二分法
「CF475D」CGCDSSQ
Givenasequenceofintegersa1, ..., anandqqueriesx1, ..., xqonit.Foreachqueryxiyouhavetocountthenumberofpairs(l, r)suchthat1 ≤ l ≤ r ≤ nandgcd(al, al + 1, ..., ar) = xi.isagreatestcommondivisorofv1, v2, ..., vn,thatisequaltoalargestpositiveintegerthatdividesallvi.InputThefirstlineoftheinputcontainsintegern,(1 ≤ n ≤ 105),denotingthelengthofthesequence.Thenextlinecont...
02014年10月6日4,578ST表,二分法,线段树
「NOIP模拟赛」大逃亡
给出数字N（1<=N<=10000），X（1<=x<=1000），Y（1<=Y<=1000）,代表有N个敌人分布一个X行Y列的矩阵上，矩形的行号从0到X-1,列号从0到Y-1再给出四个数字x1,y1,x2,y2,代表你要从点(x1,y1)移到(x2,y2)。在移动的过程中你当然希望离敌人的距离的最小值最大化，现在请求出这个值最大可以为多少,以及在这个前提下，你最少要走多少步才可以回到目标点。注意这里距离的定义为两点的曼哈顿距离，即某两个点的坐...
12014年10月4日3,976二分法,广度搜索
「NOIP模拟赛」球的序列
N个编号为1-n的球，每个球都有唯一的编号。这些球被排成两种序列，分别为A、B序列，现在需要重新寻找一个球的序列l，对于这个子序列l中任意的两个球，要求j,k(j<k)，都要求满足lj在A中位置比lk在A中位置靠前，却lj在B中位置比lk在B中位置靠前，请你计算这个子序列l的最大长度。输入:第一行一个整数，表示N。第二行N个整数，表示A序列。第三行N个整数，表示B序列。样例输入51243552341样例输出2样例说明L可以是{2,3...
02014年10月4日3,487递推与动规,二分法
「BZOJ3412」[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行：对与每个询问，在词问的时间内，奶牛敲击的是哪个音阶？SampleInput3521323401SampleOutput23311题解二分[crayon-67448863b14d9215808622/] ...
02014年9月28日2,731二分法
「BZOJ1271」[BJWc2008] 秦腾与教学评估
DescriptionInputOutputSampleInputSampleOutputHINT题解因为只有最多一个位置是奇数在这个位置后前缀和都是奇数可以二分+前缀和找出这个位置[crayon-67448863b182e575655467/] ...
02014年9月14日3,068二分法
「NOIP模拟赛」工资
聪哥在暑假参加了打零工的活动，这个活动分为n个工作日，每个工作日的工资为Vi。有m个结算工钱的时间,聪哥可以自由安排这些时间，也就是说什么时候拿钱，老板说的不算，聪哥才有发言权！（因为聪哥是土豪，他是老板的老板）聪哥不喜欢身上一次性有太多的钱，于是他想安排一下拿钱的时间，使他一次性拿的钱中最大的最小。（最后一天一定要领钱）输入第一行2个数n,m接下来n行，每行一个数，代表Vi.输出最小的最大钱数。样例输入751...
22014年9月6日3,127二分法
「BZOJ3695」「FJ2014集训」滑行
Description 首长NOI惨跪，于是去念文化课了。现在，他面对一道物理题。现在有一个小滑块可以在地面上滑行，地面上被划分成不同的区域，使得小滑块在不同的区域内部有一个不同的速度上限。小滑块在(0，0)点，我们现在要推动小滑块到目标点（x,y）。地面上有N层区域，每层区域都是矩形，现在给你一个序列{Hi}表示每层区域的高度，覆盖的地面横坐标范围是0～X，第i个区域的限速是vi。注：Y=Sigma(Hi)其中i从1到N其它...
02014年9月4日3,153二分法
「BZOJ1014」[JSOI2008] 火星人prefix
Description火星人最近研究了一种操作：求一个字串两个后缀的公共前缀。比方说，有这样一个字符串：madamimadam，我们将这个字符串的各个字符予以标号：序号：1234567891011字符madamimadam现在，火星人定义了一个函数LCQ(x,y)，表示：该字符串中第x个字符开始的字串，与该字符串中第y个字符开始的字串，两个字串的公共前缀的长度。比方说，LCQ(1,7)=5,LCQ(2,10)=1,LCQ(4,7)=0在研究LCQ函数的过程中，火星人发现了...
42014年8月12日10,010splay,二分法,哈希表