二分法 - Page 4

「fjWC2015」世界树
「题目描述」奥丁杀死的巨人伊米尔后，从伊米尔的尸体上生长出来一株巨大的梣树，它是整个宇宙的核心，被称为世界之树，这个巨木的枝干构成了整个世界，它被神秘的奥术力量所守护。奥丁发现，世界树的每个节点至多有两棵子树，其蕴含的奥术力量是子树奥术力量的最大值+1，如果一个节点没有子树，其奥术力量为1，这些节点被称为“源”。世界树在悠长的岁月里形成了奇妙的魔法平衡，具体来说，它的左子树与右子树的奥术力量的差的绝对...
02015年2月4日4,935二分法,高精度,矩阵乘法

离大海最远点在哪里？
http://218.5.5.242:9014/problem.asp?id=1678题目描述遥远的海上有一座岛屿，这个岛屿的轮廓是一个凸多边形，把边视为岛屿的海岸线。当地的居民想要在岛屿上找一地点使其到大海的距离最远，这地点应在哪里？岛上居民们习惯地把岛上某个点到岛屿的各条海岸线（即各边）距离中最小者看成该点到大海的距离。如下图所示，点O到大海的距离为min{j,k,l,m,n}=j,其中j,k,l,m,n分别为O到AB，BC，CD，DE，EA的距离。现在，给您N...
02015年2月3日7,457STL,链表,二分法,半平面交
「BZOJ2654」tree
Description　　给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。题目保证有解。Input　　第一行V,E,need分别表示点数，边数和需要的白色边数。接下来E行每行s,t,c,col表示这边的端点(点从0开始标号)，边权，颜色(0白色1黑色)。Output　　一行表示所求生成树的边权和。SampleInput22101110120SampleOutput2HINT数据规模和约定0:V<=101,2,3:V<=150,..,19:V<...
42015年1月16日8,192kruskal,二分法
「BZOJ2738」矩阵乘法
Description　　给你一个N*N的矩阵，不用算矩阵乘法，但是每次询问一个子矩形的第K小数。Input　　第一行两个数N,Q，表示矩阵大小和询问组数；接下来N行N列一共N*N个数，表示这个矩阵；再接下来Q行每行5个数描述一个询问：x1,y1,x2,y2,k表示找到以(x1,y1)为左上角、以(x2,y2)为右下角的子矩形中的第K小数。Output　　对于每组询问输出第K小的数。SampleInput2221341212111223SampleOutput13HINT　　矩阵中数...
02015年1月7日7,459二分法,树状数组
「BZOJ2527」[POI2011] Meteors
DescriptionByteotianInterstellarUnion(BIU)hasrecentlydiscoveredanewplanetinanearbygalaxy.Theplanetisunsuitableforcolonisationduetostrangemeteorshowers,whichontheotherhandmakeitanexceptionallyinterestingobjectofstudy.ThememberstatesofBIUhavealreadyplacedspacestationsclosetotheplanet'sorbit.Thestations'goalistotakesamplesoftherocksflyingby.TheBIUCommissionhaspartitionedtheorbitinto...
42015年1月7日8,421二分法,树状数组
「BZOJ2756」[SCOI2012] 奇怪的游戏
DescriptionBlinker最近喜欢上一个奇怪的游戏。这个游戏在一个N*M的棋盘上玩，每个格子有一个数。每次Blinker会选择两个相邻的格子，并使这两个数都加上1。现在Blinker想知道最少多少次能使棋盘上的数都变成同一个数，如果永远不能变成同一个数则输出-1。Input输入的第一行是一个整数T，表示输入数据有T轮游戏组成。每轮游戏的第一行有两个整数N和M，分别代表棋盘的行数和列数。接下来有N行，每行M个数。Output 对于...
62015年1月3日9,704二分法,最大流
「BZOJ1082」[SCOI2005] 栅栏
Description农夫约翰打算建立一个栅栏将他的牧场给围起来，因此他需要一些特定规格的木材。于是农夫约翰到木材店购买木材。可是木材店老板说他这里只剩下少部分大规格的木板了。不过约翰可以购买这些木板，然后切割成他所需要的规格。而且约翰有一把神奇的锯子，用它来锯木板，不会产生任何损失，也就是说长度为10的木板可以切成长度为8和2的两个木板。你的任务：给你约翰所需要的木板的规格，还有木材店老板能够给出的木材的规格...
02014年12月24日6,401深度搜索,二分法
「BZOJ1486」[HNOI2009] 最小圈
题解分数规划，二分答案用dfs版的spfa判负环[crayon-6920d83b5086a372967682/]
02014年12月23日6,635spfa,二分法
「BZOJ2282」[SDOI2011] 消防
Description某个国家有n个城市，这n个城市中任意两个都连通且有唯一一条路径，每条连通两个城市的道路的长度为zi(zi<=1000)。这个国家的人对火焰有超越宇宙的热情，所以这个国家最兴旺的行业是消防业。由于政府对国民的热情忍无可忍（大量的消防经费开销）可是却又无可奈何（总统竞选的国民支持率），所以只能想尽方法提高消防能力。现在这个国家的经费足以在一条边长度和不超过s的路径（两端都是城市）上建立消防枢纽，为了尽...
62014年12月22日7,111二分法,广度搜索
「CF497B」Tennis Game
PetyaandGenaloveplayingtabletennis.Asinglematchisplayedaccordingtothefollowingrules:amatchconsistsofmultiplesets,eachsetconsistsofmultipleserves.Eachserveiswonbyoneoftheplayers,thisplayerscoresonepoint.Assoonasoneoftheplayersscorestpoints,hewinstheset;thenthenextsetstartsandscoresofbothplayersarebeingsetto0.Assoonasoneoftheplayerswinsthetotalofssets,hewinsthematchandthematchisover.Heresandt...
02014年12月18日4,006二分法
「BZOJ1822」[JSOI2010] Frozen Nova 冷冻波
DescriptionWJJ喜欢“魔兽争霸”这个游戏。在游戏中，巫妖是一种强大的英雄，它的技能FrozenNova每次可以杀死一个小精灵。我们认为，巫妖和小精灵都可以看成是平面上的点。当巫妖和小精灵之间的直线距离不超过R，且巫妖看到小精灵的视线没有被树木阻挡（也就是说，巫妖和小精灵的连线与任何树木都没有公共点）的话，巫妖就可以瞬间杀灭一个小精灵。在森林里有N个巫妖，每个巫妖释放FrozenNova之后，都需要等待一段时间，...
62014年12月15日5,219最大流,二分法,几何
「BZOJ2348」[Baltic 2011] Plagiarism
Description世界编程大赛的选手们提交N份程序文件f1,…,fN给评测系统。在将评测结果正式公布之前，评委会想要排除一切可能的剽窃现象。他们已有一个对比程序，用来比较两份程序文件，并判断它们是否太过相似了。然而程序文件的数目相当大，把每两份（一对，pair）文件都进行比较的话将花太多的时间。另一方面，许多对(pair)可以直接被排除，如果文件的大小相差太大的话。更准确地说，评委会决定，如果每两份文件（一对，pair）中...
02014年12月15日3,351二分法