二分法 - Page 5

「BZOJ2732」[HNOI2012] 射箭
Description沫沫最近在玩一个二维的射箭游戏，如下图1所示，这个游戏中的x轴在地面，第一象限中有一些竖直线段作为靶子，任意两个靶子都没有公共部分，也不会接触坐标轴。沫沫控制一个位于(0,0)的弓箭手，可以朝0至90?中的任意角度（不包括0度和90度），以任意大小的力量射出带有穿透能力的光之箭。由于游戏中没有空气阻力，并且光之箭没有箭身，箭的轨迹会是一条标准的抛物线，被轨迹穿过的所有靶子都认为被沫沫射中了，包括那些...
52014年12月4日6,496二分法,半平面交

WC2010重建计划
DescriptionInput第一行包含一个正整数N，表示X国的城市个数.第二行包含两个正整数L和U，表示政策要求的第一期重建方案中修建道路数的上下限接下来的N-1行描述重建小组的原有方案，每行三个正整数Ai,Bi,Vi分别表示道路(Ai,Bi),其价值为Vi其中城市由1..N进行标号Output输出最大平均估值，保留三位小数SampleInput423121132143SampleOutput2.500HINT20%的数据,N<=500030%的数据,N<=100000,原有方案恰...
22014年12月3日7,558二分法,点分治,单调队列
「CF492D」Vanya and Computer Game
VanyaandhisfriendVovaplayacomputergamewheretheyneedtodestroynmonsterstopassalevel.Vanya'scharacterperformsattackwithfrequencyxhitspersecondandVova'scharacterperformsattackwithfrequencyyhitspersecond.Eachcharacterspendsfixedtimetoraiseaweaponandthenhehits(thetimetoraisetheweaponis1 / xsecondsforthefirstcharacterand1 / ysecondsforthesecondone).Thei-thmonsterdiesafterhereceivesaihits.Vanya...
02014年12月2日3,333二分法
「BZOJ1567」[JSOI2008] Blue Mary的战役地图
DescriptionBlueMary最近迷上了玩Starcraft(星际争霸)的RPG游戏。她正在设法寻找更多的战役地图以进一步提高自己的水平。由于BlueMary的技术已经达到了一定的高度,因此，对于用同一种打法能够通过的战役地图，她只需要玩一张，她就能了解这一类战役的打法，然后她就没有兴趣再玩儿这一类地图了。而网上流传的地图有很多都是属于同一种打法，因此BlueMary需要你写一个程序，来帮助她判断哪些地图是属于同一类的。具体来说...
12014年11月13日4,346二分法,哈希表
NOIP2011聪明的质检员
题目描述Description小T是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有n个矿石，从1到n逐一编号，每个矿石都有自己的重量wi以及价值vi。检验矿产的流程是：见图若这批矿产的检验结果与所给标准值S相差太多，就需要再去检验另一批矿产。小T不想费时间去检验另一批矿产，所以他想通过调整参数W的值，让检验结果尽可能的靠近标准值S，即使得S-Y的绝对值最小。请你帮忙求出这个最小值。输入描述InputDescripti...
02014年11月6日6,635二分法
「NOIP模拟赛」数字对
「题目描述」小H是个善于思考的学生，现在她又在思考一个有关序列的问题。她的面前浮现出一个长度为n的序列{ai}，她想找出一段区间[L,R](1<=L<=R<=n)。这个特殊区间满足，存在一个k(L<=k<=R)，并且对于任意的i(L<=i<=R)，ai都能被ak整除。这样的一个特殊区间[L,R]价值为R-L。小H想知道序列中所有特殊区间的最大价值是多少，而有多少个这样的区间呢？这些区间又分别是哪些呢？你能帮助她吧。「输...
02014年11月4日4,287ST表,二分法
「NOIP模拟赛」密码
「问题描述」哪里有压迫，哪里就有反抗。moreD的宠物在法庭的帮助下终于反抗了。作为一只聪明的宠物，他打算把魔法使moreD的魔法书盗去，夺取moreD的魔法能力。但moreD怎么会让自己的魔法书轻易地被盗取？moreD在魔法书上设置了一个密码锁，密码锁上有一个问题。施以斯卧铺魔法吧，你有M次机会，如此将得完美密码。然后是一串小写字母串。moreD的宠物斯卧铺魔法就是施法时的字符串其中相邻两位交换。而moreD对于完美密码的...
22014年11月2日5,360贪心,线段树,二分法
「想法题系列」逗比三角形
「题目描述」小J是一名OI退役滚粗文化课选手，他十分喜欢做题，尤其是裸题。他现在有一个二维盒子和一些二维三角形，这个盒子拥有无限的高度和L的宽度。而且他的三角形也都是一些锐角三角形或者是直角三角形。现在小J想把这些三角形放入盒子里，由于小J从txt大神犇那里学会了魔♂法，所以小J的三角形既可以无视盒子边界又可以重叠放置，但是必须有一条边紧贴盒子底面所在的直线。现在小J想要最大化在盒子中的被三角形覆盖的...
02014年10月29日3,973二分法,几何
「NOIP模拟赛」狐狸的谜语
题目描述话说某一个月黑风高的晚上,一只褐色的狐狸快速地跳过了一只懒狗,并留下一个字符串“032089”和一个数字5。这其中一定隐含了某些秘密!酷爱思考的你马上发现，这个字符串可以写成：“03+2+0*89”，结果为5。这是一个非常有趣的问题!现在给出一个长度为N的数字字符串和一个数字T，要求插入最少的加号或者乘号，使得数字字符串的运算结果为T。运算符*号优先级高于+号，运算数可以有任意个前导0。榆入格式输入不超过5组数据,...
02014年10月28日4,677迭代深搜,二分法
「NOIP模拟赛」小奇回地球
原题目名：时间与空间之旅2015.9.13日hzwer重制了题面与数据「题目背景」开学了，小奇在回地球的路上，遇到了一个棘手的问题。「问题描述」简单来说，它要从标号为1的星球到标号为n的星球，某一些星球之间有航线。由于超时空隧道的存在，从一个星球到另一个星球时间可能会倒流，而且，从星球a到b耗费的时间和星球b到a耗费的时间不一定相同。宇宙法规定：“禁止在出发时间前到达目的地。”每艘飞船上都有速度调节装置，...
32014年10月28日5,427spfa,二分法
「BZOJ2709」[Violet 1] 迷宫花园
DescriptionInputOutputSampleInput22.545######S##E######211312#############S###E#####################################################################SampleOutput0.500000.21053HINTSource题解。。。。二分+最短路判定即可不知道为何读入会出现奇怪的问题让我re了一版。。。。一直检查数组。。。[crayon-676854c369add898390205/] ...
02014年10月27日4,047STL,dijkstra,二分法
「vijos1894」セチの祈り
背景琼花飘落彩蝶曼舞又是一年春满腹愁情化作伤春酒梧桐细雨影影绰绰残阳落韶华飞逝梦断都成空描述在Ninian的花园里，有许多琼花，环绕着中间的凉亭。有N片琼花，组成一个环。Ninian想在凉亭中发动[セチの祈り]，需要划分出三个区域的琼花，为了平均，要最大化面积最小的区域的面积。划分区域：即用三刀把这个环分成三段，每段称之为一个区域。格式输入格式第一行一个整数N。接下来N个整数Si，表示第i片琼花的面积。输出格式...
02014年10月26日3,417贪心,二分法