POJ2455Secret Milking Machine[最大流 无向图 二分答案]
SecretMilkingMachineTimeLimit:1000MS MemoryLimit:65536KTotalSubmissions:11865 Accepted:3445DescriptionFarmerJohnisconstructinganewmilkingmachineandwis...
C. Anton and Fairy Tale----思维+二分答案
C.AntonandFairyTaletimelimitpertest1secondmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputAntonlikestolistentofairytales,especiall...
POJ 1743 Musical Theme（后缀数组+二分答案）
【题目链接】 http://poj.org/problem?id=1743【题目大意】给出一首曲子的曲谱，上面的音符用不大于88的数字表示，现在请你确定它主旋律的长度，主旋律指的是出现超过一次，并且长度不小于5的最长的曲段，主旋律出现的时候并不是完全一样的，可能经过了升调或者降调，也就是说，是原来主...
Rabbit的机器人-二分答案
Rabbit的机器人思路：可以推知挡板的位置与最后一步的方向有关。如果是R根据题目要求那么最终结果一定是在>0的位置，因为按照题意要求的最终不能回到重复走过的位置。所以如果有解的话挡板只能放在<0的位置，分析一下就是放在>0的位置有两种情况1.在最终结果前面，这显然不可以会直接导致...
bzoj4985 评分 (二分答案+dp)
首先二分一个答案x，然后我们把>=x的数看成1,<x的数看成0，那如果最后剩下1，这个答案就是合法的。那我们就来算让某一位得1至少需要填几个1（设这个值是f[i]）i=1..n时，显然，如果i已经固定，f[i]=0或inf（取决于原来是1还是0）；如果i还没有固定，那f[i]=1然后每次...
POJ 3261 Milk Patterns（后缀数组+二分答案+离散化）
题意：给定一个字符串，求至少出现k次的最长重复子串，这k个子串可以重叠。分析：经典的后缀数组求解题：先二分答案，然后将后缀分成若干组。这里要判断的是有没有一个组的符合要求的后缀个数（height[i]>=mid）不小于k。如果有，那么存在k个相同的子串满足条件，否则不存在。#include&l...
数字对——RMQ+二分答案
题目描述 小H是个善于思考的学生，现在她又在思考一个有关序列的问题。她的面前浮现出一个长度为n的序列{ai}，她想找出一段区间[L,R](1<=L<=R<=n)。这个特殊区间满足，存在一个k(L<=k<=R)，并且对于任意的i(L<=i<=R)，ai都能被a...
[NOIP2011] 聪明的质检员（二分答案）
题目描述小T是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有n个矿石，从1到n逐一编号，每个矿石都有自己的重量wi以及价值vi。检验矿产的流程是：1、给定m个区间[Li,Ri]；2、选出一个参数W；3、对于一个区间[Li,Ri]，计算矿石在这个区间上的检验值Yi：这批矿产的检验结果Y为各个...
【BZOJ2440】完全平方数（二分答案，莫比乌斯反演）
【BZOJ2440】完全平方数（二分答案，莫比乌斯反演）题面BZOJ题解很显然，二分一个答案考虑如何求小于等于这个数的非完全平方数倍数的个数这个明显可以直接，莫比乌斯反演一下然后这题就很简单了#include<iostream>#include<cstdio>#include...
[CodePlus 2017 11月赛&洛谷P4058]木材 题解（二分答案）
[CodePlus201711月赛&洛谷P4058]木材Description有n棵树，初始时每棵树的高度为Hi，第i棵树每月都会长高Ai。现在有个木料长度总量为S的订单，客户要求每块木料的长度不能小于L，而且木料必须是整棵树（即不能为树的一部分）。现在问你最少需要等多少个月才能满足订单。输...
BZOJ4317Atm的树&BZOJ2051A Problem For Fun&BZOJ2117[2010国家集训队]Crash的旅游计划——二分答案+动态点分治(点分树套线段树/点分树+vector)
题目描述Atm有一段时间在虐qtree的题目，于是，他满脑子都是tree，tree，tree……于是，一天晚上他梦到自己被关在了一个有根树中，每条路径都有边权，一个神秘的声音告诉他，每个点到其他的点有一个距离（什么是距离不用说吧），他需要对于每个点回答：从这个点出发的第k小距离是多少；如果atm不能...
NOIP2010关押罪犯[并查集｜二分答案＋二分图染色 | 种类并查集]
题目描述S城现有两座*，一共关押着N名罪犯，编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为c的罪犯被关押在同一*...
POJ 3579 Median（二分答案+Two pointers）
【题目链接】 http://poj.org/problem?id=3579【题目大意】给出一个数列，求两两差值绝对值的中位数。【题解】因为如果直接计算中位数的话，数量过于庞大，难以有效计算，所以考虑二分答案，对于假定的数据，判断是否能成为中位数此外还要使得答案尽可能小，因为最小的满足是中位数的答案，...
Codeforces Round #276 (Div. 1) E. Sign on Fence （二分答案 主席树 区间合并）
链接：http://codeforces.com/contest/484/problem/E题意：给你n个数的，每个数代表高度；再给出m个询问，每次询问[l,r]区间内连续w个数的最大的最小值；思路：因为查询的到的值一定是输入的其中一个，那么我们可以二分答案，判断二分得到的答案是否符合，那么在这里我...