写这个题为了提醒自己先想简单的做法再想复杂的，不要一上来就跑偏到复杂操作上去。。。
题目要求给出n*m的乘法表中第K大的元素，n和m都是5e5数量级. 暴力显然不行，所以得找个快速的方法分辨出第k大，然后我由于这几天一直在搞数论，脑子抽了从质因数分解的角度考虑结果弄得巨复杂。。。最后看官方题解就一句话二分查找，醍醐灌顶。。。
由于生成表格的方法是i*j所以check只要把所有的x/i加和与k比较大小就是了。
继续阅读“[CF][二分查找][×] codeforces 448D Multiplication Table”
昨晚肝这一场是真的赔了，傻不拉几的C低级失误wa了一发，出完发现大家都会F然后跑去看了20min没头绪，折回去搞这个D，到最后也没过。。。感觉复杂度没错却一直tle，一直弄到两点受不了了睡觉去了，今早上课困得一批。
下午睡醒之后一直tle on test 27，给跪了好吧，疯狂卡常数真的有意思？最后把multiset改成priority_queue过了，真的服了，到目前为止52组数据吧，最狠的一组达到了2979ms，差21ms超时呵呵呵呵呵呵。。。
继续阅读“[CF][二分check][贪心][×] codeforces 1132D Stressful Training”
http://codeforces.com/contest/1062/problem/E
这题两个难点，第一个是如何快速找到一堆不一定在一起的节点的公共LCA，第二个是如何确定这一堆节点中需要剔除哪一个。
可以先想一下，设原集合的lca为p1，可以取得最优答案的点为x，其他点为vi，那么x一定不在lca(所有的vi)这个点的子树上。这时候，任意一个vi和x的lca都是p1。这时假如维护一个S[l,r]表示[l,r]的公共LCA，根据上面说的性质，这个S序列一定存在一个断点，从这个点开始所有的S==p1,这样的话就可以利用二分查找找到这个断点，可以确定这个断点一定是候选答案之一。另外一个在二分的过程中其实是所有的lca都是基于最左边那个点积累过来的，所以除了分界点之外另外一个可能影响到答案的就是最左边这个点。到这里就算是找到了唯二可能影响答案的点，只需要对他们分别验证就可以了。从dalao的代码里学到了lca也可以作为线段树维护的变量。。。 继续阅读“[线段树+][LCA][dfs序][二分查找][×] codeforces 1062E”
没做出来看题解的时候就在想出题人是怎么搞出来的。。。这个做法emm
最大值最小化肯定要想二分，但是二分后这题目怎么check是个技术活。我最悲催的是理解错了题目意思，以为这些珠子（不管是什么吧我感觉是珠子）可以互换位置。实际上是不可以换的emm所以说看题还是要好好搞明白。
然后说说这个check，这个一开始有点迷，因为它本身是dp那一章的题，但是二分的check一般都是判断一个可行性，那加了这个二分出来的答案的约束怎么判断可行性？首先可以确定一般dp不会说去dp那种“区间上的最大值”之类的东西，他要做一定是一个量化的东西去求最优解。这里的话可以想象一下，如果用了比m更少的段就可以满足要求那么就可以继续进行下去？这样的话必须保证段数和最紧的上限是一个正比的关系！但是算一算可以发现并没有这种正比关系，一般这时候就放弃用二分的方法了，但是这个题最精彩的地方就在于他的奇偶性，由于题目本身一直在要求“半段”，所以可以利用奇偶性来保证正比单调，具体可以看这位dalao的博客
http://codeforces.com/contest/1064/problem/E
又是喜闻乐见的交互+二分，这个已经在cf的讨论区被吐槽两次了，每次出交互题都是二分。。。我一开始没有搞懂题意，以为是你随便给他出点它会自动调整让点可以分为两片区域，后来才意识到他是给定了点的颜色分布，就是第几个点你只要问就是安排好的，也就是说这个需要你掌握问的点的坐标。。。
但是在不知道下一个点是什么的时候如何发问呢，首先想简化的过程，如果问的点全在一条线上会发生什么：假设左边为白点右边为黑，那么那个分界线一定是先往一个方向走了几步，然后又得回头往另一个方向走，如此反复。那么如何保证每次“回头”都可以有足够的余地让继续走下去而不与之前定好的界限相交？想到了一个叫二分的东西。。在倍增法的实现里其实就可以发现，他每次都会减半所以每次都不会覆盖到原来的部分。
但是这个题目直接二分又是有问题的，因为最多可以有30个点，而[log2(1e9)]==29，也就是说有一种情况可能最后会有俩点重合，为了避免这种情况可以先ask一个(0,0)，并且以此确定左半边的颜色，而不是像一开始说的一样自己定左右颜色。这样的话就剩下了29个点需要处理了，1e9的范围可以保证无论如何二分都可以达到没有任何两个点重合的结果。这样的话只需要在分界处的两个点之间画一条斜线就可以了。
因为这个29的坑wa了n发。。。
继续阅读“[二分][精度][思维] codeforces1064E Dwarves, Hats and Extrasensory Abilities”
