二分法 - Page 3

【bzoj2770】YY的Treap
Description志向远大的YY小朋友在学完快速排序之后决定学习平衡树，左思右想再加上SY的教唆，YY决定学习Treap。友爱教教父SY如砍瓜切菜般教会了YY小朋友Treap（一种平衡树，通过对每个节点随机分配一个priority，同时保证这棵平衡树关于priority是一个小根堆以保证效率）。这时候不怎么友爱的510跑了出来，他问了YY小朋友一个极不和谐的问题：怎么求Treap中两个点之间的路径长度。YY秒了之后决定把这个问题交给你...
02015年4月16日1,836STL,二分法,线段树

【cf526X】ZeptoLab Code Rush 2015
懒得开多篇了，深夜口胡TAT现在是凌晨4点。。。A：KingofThieves枚举起始点模拟[crayon-59e5cdfd22f97226398609/]B：OmNomandDarkPark算出最大值，从最高层开始贪心，能加尽量加[crayon-59e5cdfd22fa0900267687/]C：OmNomandCandies设hb/wb为小于ha/wa即a的单位质量价值高分类讨论若wb很大，则可以枚举b取了多少个否则a取的数量一定与c/wa相差不超过wb分类暴力TAT[crayon-59e5cdfd22fa5707858974/]D： OmNom...
32015年4月5日1,450模拟,贪心,二分法,哈希表,调和级数
【bzoj2095】[Poi2010]Bridges
DescriptionYYD为了减肥，他来到了瘦海，这是一个巨大的海，海中有n个小岛，小岛之间有m座桥连接，两个小岛之间不会有两座桥，并且从一个小岛可以到另外任意一个小岛。现在YYD想骑单车从小岛1出发，骑过每一座桥，到达每一个小岛，然后回到小岛1。霸中同学为了让YYD减肥成功，召唤了大风，由于是海上，风变得十分大，经过每一座桥都有不可避免的风阻碍YYD，YYD十分ddt，于是用泡芙贿赂了你，希望你能帮他找出一条承...
02015年4月4日2,018二分法,最大流,欧拉图
【bzoj2083】[Poi2010]Intelligence test
Description霸中智力测试机构的一项工作就是按照一定的规则删除一个序列的数字，得到一个确定的数列。Lyx很渴望成为霸中智力测试机构的主管，但是他在这个工作上做的并不好，俗话说熟能生巧，他打算做很多练习，所以他希望你写一个程序来快速判断他的答案是否正确。Input第一行为一个整数m（1<=m<=1000000）第二行包括m个用空格分开的整数ai（1<=ai<=1000000），组成了最初的序列，第三行为一个整数n（1<=n<=...
02015年4月3日1,153二分法
【bzoj2084】[Poi2010]Antisymmetry
Description对于一个01字符串，如果将这个字符串0和1取反后，再将整个串反过来和原串一样，就称作“反对称”字符串。比如00001111和010101就是反对称的，1001就不是。现在给出一个长度为N的01字符串，求它有多少个子串是反对称的。Input第一行一个正整数N(N<=500,000)。第二行一个长度为N的01字符串。Output一个正整数，表示反对称子串的个数。SampleInput811001011SampleOutput7hint7个反对称子串分别是：01(出现两...
22015年4月2日1,310二分法,哈希表
【codechef】March Challenge 2015
只做了前6题弃疗了感觉codechef写题解也没啥人看……【codechefCNOTE】ChefandNotebooks纯模拟[crayon-59e5cdfd3eef1195497940/]【codechefSIGNWAVE】SignWave听说此题打表可以找规律。。引用zld神犇的话吧。。。就是若干个余弦函数的零点均不同。。然后sin函数的分布就十分奇怪了。。比如s=3的时候就是312131213，忽略两端的情况。。就变成非常规则的1213121然后我们再考虑余弦函数当c=2的时候分布就是011101110...
02015年3月17日1,283模拟,二分法,并查集,离线处理
【fjwc2015】世界树
【题目描述】奥丁杀死的巨人伊米尔后，从伊米尔的尸体上生长出来一株巨大的梣树，它是整个宇宙的核心，被称为世界之树，这个巨木的枝干构成了整个世界，它被神秘的奥术力量所守护。奥丁发现，世界树的每个节点至多有两棵子树，其蕴含的奥术力量是子树奥术力量的最大值+1，如果一个节点没有子树，其奥术力量为1，这些节点被称为“源”。世界树在悠长的岁月里形成了奇妙的魔法平衡，具体来说，它的左子树与右子树的奥术力量的差的绝对...
02015年2月4日1,756二分法,高精度,矩阵乘法
离大海最远点在哪里？
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日2,091STL,链表,二分法,半平面交
【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日2,851kruskal,二分法
【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日2,642二分法,树状数组
【bzoj2527】[Poi2011]Meteors
DescriptionByteotianInterstellarUnion(BIU)hasrecentlydiscoveredanewplanetinanearbygalaxy.Theplanetisunsuitableforcolonisationduetostrangemeteorshowers,whichontheotherhandmakeitanexceptionallyinterestingobjectofstudy.ThememberstatesofBIUhavealreadyplacedspacestationsclosetotheplanet'sorbit.Thestations'goalistotakesamplesoftherocksflyingby.TheBIUCommissionhaspartitionedtheorbitinto...
42015年1月7日3,055二分法,树状数组
【bzoj2756】[SCOI2012]奇怪的游戏
DescriptionBlinker最近喜欢上一个奇怪的游戏。这个游戏在一个N*M的棋盘上玩，每个格子有一个数。每次Blinker会选择两个相邻的格子，并使这两个数都加上1。现在Blinker想知道最少多少次能使棋盘上的数都变成同一个数，如果永远不能变成同一个数则输出-1。Input输入的第一行是一个整数T，表示输入数据有T轮游戏组成。每轮游戏的第一行有两个整数N和M，分别代表棋盘的行数和列数。接下来有N行，每行M个数。Output 对于...
62015年1月3日3,902最大流,二分法
【bzoj1082】[SCOI2005]栅栏
Description农夫约翰打算建立一个栅栏将他的牧场给围起来，因此他需要一些特定规格的木材。于是农夫约翰到木材店购买木材。可是木材店老板说他这里只剩下少部分大规格的木板了。不过约翰可以购买这些木板，然后切割成他所需要的规格。而且约翰有一把神奇的锯子，用它来锯木板，不会产生任何损失，也就是说长度为10的木板可以切成长度为8和2的两个木板。你的任务：给你约翰所需要的木板的规格，还有木材店老板能够给出的木材的规格...
02014年12月24日2,700深度搜索,二分法