二分法 - Page 3

TLX Practice Contest
被练习赛虐QAQA快速冪脑补一下[crayon-5c9146e8b6253164792070/]B把两种行分开分别dp求前i行有j行两人都错然后枚举两种行分别两人都错了i，j用排列组合算一下贡献即可[crayon-5c9146e8b625b187071598/]C二分+树形dp[crayon-5c9146e8b6265169674881/]...
62015年5月8日2,042递推与动规,二分法,树形动规,快速幂,排列组合

「BZOJ2811」[Apio2012] Guard
DescriptionInputOutputSampleInput534121341440451SampleOutput35HINT在这个样例中，有两种可能的安排方式：1，3，5 或者 2，3，5。即 3 和 5后面必然躲着一个忍者。考虑第一个灌木丛，存在一种安排方案使得它的后面躲着忍者，但也存在一种安排方案使得它后面没有躲忍者，因此不应该输出 1。同理，不应该输出 2。题解首先先将0的区间去除，可以用线段树TT如果去除0剩下的坐标编号等于忍者数，则所有剩下的坐标...
122015年4月24日4,744贪心,二分法,线段树
UOJ Round #3
http://vfleaking.blog.uoj.ac/blog/43「UR#3」核聚变反应强度[crayon-5c9146e8b763b905753582/]「UR#3」铀仓库[crayon-5c9146e8b7646251942407/]「UR#3」链式反应题目都不敢看。。。
02015年4月19日1,791二分法,最大公约数与最小公倍数
「BZOJ2770」YY的Treap
Description志向远大的YY小朋友在学完快速排序之后决定学习平衡树，左思右想再加上SY的教唆，YY决定学习Treap。友爱教教父SY如砍瓜切菜般教会了YY小朋友Treap（一种平衡树，通过对每个节点随机分配一个priority，同时保证这棵平衡树关于priority是一个小根堆以保证效率）。这时候不怎么友爱的510跑了出来，他问了YY小朋友一个极不和谐的问题：怎么求Treap中两个点之间的路径长度。YY秒了之后决定把这个问题交给你...
02015年4月16日2,795STL,线段树,二分法
「CF526X」ZeptoLab Code Rush 2015
懒得开多篇了，深夜口胡TAT现在是凌晨4点。。。A：KingofThieves枚举起始点模拟[crayon-5c9146e8b7e49503962424/]B：OmNomandDarkPark算出最大值，从最高层开始贪心，能加尽量加[crayon-5c9146e8b7e52321168565/]C：OmNomandCandies设hb/wb为小于ha/wa即a的单位质量价值高分类讨论若wb很大，则可以枚举b取了多少个否则a取的数量一定与c/wa相差不超过wb分类暴力TAT[crayon-5c9146e8b7e56055826931/]D： OmNom...
32015年4月5日2,182模拟,贪心,二分法,哈希表,调和级数
「BZOJ2095」[POI2010] Bridges
DescriptionYYD为了减肥，他来到了瘦海，这是一个巨大的海，海中有n个小岛，小岛之间有m座桥连接，两个小岛之间不会有两座桥，并且从一个小岛可以到另外任意一个小岛。现在YYD想骑单车从小岛1出发，骑过每一座桥，到达每一个小岛，然后回到小岛1。霸中同学为了让YYD减肥成功，召唤了大风，由于是海上，风变得十分大，经过每一座桥都有不可避免的风阻碍YYD，YYD十分ddt，于是用泡芙贿赂了你，希望你能帮他找出一条承...
02015年4月4日3,528最大流,二分法,欧拉图
「BZOJ2083」[POI2010] Intelligence test
Description霸中智力测试机构的一项工作就是按照一定的规则删除一个序列的数字，得到一个确定的数列。Lyx很渴望成为霸中智力测试机构的主管，但是他在这个工作上做的并不好，俗话说熟能生巧，他打算做很多练习，所以他希望你写一个程序来快速判断他的答案是否正确。Input第一行为一个整数m（1<=m<=1000000）第二行包括m个用空格分开的整数ai（1<=ai<=1000000），组成了最初的序列，第三行为一个整数n（1<=n<=...
02015年4月3日1,940二分法
「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日2,378二分法,哈希表
「codechef」March Challenge 2015
只做了前6题弃疗了感觉codechef写题解也没啥人看……「codechefCNOTE」ChefandNotebooks纯模拟[crayon-5c9146e8cfa8b272202230/]「codechefSIGNWAVE」SignWave听说此题打表可以找规律。。引用zld神犇的话吧。。。就是若干个余弦函数的零点均不同。。然后sin函数的分布就十分奇怪了。。比如s=3的时候就是312131213，忽略两端的情况。。就变成非常规则的1213121然后我们再考虑余弦函数当c=2的时候分布就是011101110...
02015年3月17日2,002模拟,二分法,并查集,离线处理
「fjWC2015」世界树
「题目描述」奥丁杀死的巨人伊米尔后，从伊米尔的尸体上生长出来一株巨大的梣树，它是整个宇宙的核心，被称为世界之树，这个巨木的枝干构成了整个世界，它被神秘的奥术力量所守护。奥丁发现，世界树的每个节点至多有两棵子树，其蕴含的奥术力量是子树奥术力量的最大值+1，如果一个节点没有子树，其奥术力量为1，这些节点被称为“源”。世界树在悠长的岁月里形成了奇妙的魔法平衡，具体来说，它的左子树与右子树的奥术力量的差的绝对...
02015年2月4日2,621二分法,高精度,矩阵乘法
离大海最远点在哪里？
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日3,603STL,链表,二分法,半平面交
「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<...
52015年1月16日5,731kruskal,二分法