ACM

51nod 1105 第K大的数(二分答案+二分查找)

51nod 1105 第K大的数(二分答案+二分查找)
题目:数组A和数组B,里面都有n个整数。数组C共有n^2个整数,分别是A[0] * B[0],A[0] * B[1] ......A[1] * B[0],A[1] * B[1]......A[n - 1] * B[n - 1](数组A同数组B的组合)。求数组C中第K大的数。例如:A:1 2 3,B:2 3 4。A与B组合成的C包括2 3 4 4 6 8 6 9 12共9个数。题解:二分好题,最重要... 继续阅读 »
ACM

Atcoder - Widespread(二分答案)

Atcoder - Widespread(二分答案)
题意:你遇到了N个怪兽,你可以选择其中一头怪兽进行攻击,它将会受到a点伤害值,其他怪兽获得b点伤害值(b<a)。当一个怪兽的hp为0时他将会消失,求攻击的最少次数。题解:选择最大的进行攻击肯定不是最优,这题可以用二分答案来解。假设当前攻击次数为mid,那么每头怪兽收到的攻击就是mid*b,剩下要是还有值则选用a的伤害值来攻击,看最后是否能够把每头怪兽消灭掉,如果能消灭那么就将右区间减少,否则... 继续阅读 »
ACM

POJ - 3621 Sightseeing Cows (最优比率生成环)

POJ - 3621 Sightseeing Cows (最优比率生成环)
给出一个有L个点P条边的**有向图(有向图记得了,判成无向图一直跑不出数据气死)**,每个点上的点权为F,每条边上的边权为T。请计算存在一个回路使得∑Fi/∑Ti最大。同样进行二分建图,跑spfa判断是否存在环,由于是正环,所以取反就相当于判负环了。只不过这题目数据有点水啊(不如说题目描述不够准确),网上很多人从1开始跑环的,但是也有人说是从哪个点都可以,仔细看了一下题目是从起始地点开始,也终于起... 继续阅读 »
ACM

POJ - 2728 Desert King (最优比率生成树)

POJ - 2728 Desert King (最优比率生成树)
题目大意是给你n个点的完全图,对于每两个点之间的边有两个权值,cost和len,求一个生成树,使得∑cost/∑len最小。每条边cost的计算是这条边两端点的权值之差的绝对值。len的计算是两个点之间的距离。01分数规划传送门:http://woodcoding.com/?id=172我们可以先根据给出的数据求出每条边的cost和len,然后把每条边的权值设为cost-x*len跑生成树求和,最... 继续阅读 »
ACM

POJ 2976 - Dropping tests(基础01分数规划)

POJ 2976 - Dropping tests(基础01分数规划)
题目的意思是你现在有n场测试,每场测试的成绩总共有b个题目,你对了a个题目,然后你可以选择放弃k个测试,选择剩下的所有测试来作为你的总分数,总分数定义为∑ai/∑bi。请计算你能获得的最大分数。明显的01分数规划模板题,我们令∑ai/∑bi>=x,所以有∑ai-x*∑bi>=0;对每场测试进行计算然后排序选择除掉k个之后剩下的和然后不断判断就好了。01分数规划不会?不如看看之前文章的分... 继续阅读 »
ACM

01分数规划

01分数规划
个人对01分数规划的理解是:01分数规划是利用二分的思想,不断地对答案进行二分验证,使得答案趋近于正确值,最后在精度允许的情况下得到最终的正确答案。先来举个例子,假设有一堆物品,价值为分别为v_i(v_i\geq0)vi(vi≥0),代价分别为w_i(w_i\geq0)wi(wi≥0)。每种物品只有选和不选,请选出一些物品,使他们的收益和最大(为了体现出01规划中01的思想,我们规定这里的w>... 继续阅读 »
ACM

CodeForces - 626C - Block Towers(二分)

CodeForces - 626C - Block Towers(二分)
题意:给出n、m,请计算一个只有n个2的倍数和m个3的倍数构成并且没有重复的序列中最小的max(n*2, m*3)。为了接下来学习01规划找到的这个题。这个题有两种解法,一种是贪心,一种是二分。我们先来看看贪心解法:一、贪心:首先,我们考虑到2的倍数和3的倍数是有他们的最小公倍数6的倍数的重复的。所以我们只需要先假定n就是n*2,m就是m*3,这时候可能有6的重复,所以我们从6开始不断增长6的倍数... 继续阅读 »
ACM

POJ 2785 - 4 Values whose Sum is 0

POJ 2785 - 4 Values whose Sum is 0
题目意思是每行给你四个数,然后再每列选一个数,四列任取一组之和等于0,求有多少组这种组合?一开始想复杂了,以为是动态规划,后来比完才知道是二分,暴力也可以做(不知道为什么暴力时间还短一些)。暴力的话就是先a、b组合排序,然后c、d组合排序。从ab的开头开始找,从cd的末尾开始找,这样时间会快点。二分的话就是,排列的的时候将cd组合为-(c+d),然后排序之后二分查找和ab相同的即可。代码:Stat... 继续阅读 »
ACM

CodeForces 778A - String Game(二分)

CodeForces 778A - String Game(二分)
题目意思是给你一个字符串,然后接下来是一个字串,然后再给你一个原字符串每个字符位置打乱的序列,按照这个序列开始删除字符,直到删除到再删除会导致字串不存在为止,问你最多删除多少次。竟然是二分!!!虽然开始看到给出的字符串很长,想想也不可能是常规的解法,但是二分实在没想到啊,二分的题做的太少了。二分,把序列二分一下查找字串是否存在,嗯,就是这么个意思。代码:StatusAcceptedTime62ms... 继续阅读 »