写这个题为了提醒自己先想简单的做法再想复杂的，不要一上来就跑偏到复杂操作上去。。。
题目要求给出n*m的乘法表中第K大的元素，n和m都是5e5数量级. 暴力显然不行，所以得找个快速的方法分辨出第k大，然后我由于这几天一直在搞数论，脑子抽了从质因数分解的角度考虑结果弄得巨复杂。。。最后看官方题解就一句话二分查找，醍醐灌顶。。。
由于生成表格的方法是i*j所以check只要把所有的x/i加和与k比较大小就是了。
继续阅读“[CF][二分查找][×] codeforces 448D Multiplication Table”
去年校赛的时候感觉此题难的一批，，，昨天做polya练习题的时候做到了poj 2888去翻了下matrix67大神的十个利用矩阵乘法解决的经典题目中的第9题才恍然大悟。。。Oooooor2 做完这俩题再来看XDOJ的这个题已经是自然而然就可以搞出结果的了。
这个题的思想就是：把每一列3*1的小方格当成一个“珠子”，把他可能的8种情况当成“颜色”，然后这些颜色同时也代表状态，类似于poj2888的颜色相邻限制，这里的状态之间“能不能相邻”其实就是在状压dp里“能不能转移”的限制，不同状态之间的转移图如下（来自matrix67的那篇文章
主要是利用了斐波那契数列对mod1e9+9时二次剩余的性质。说起来这个性质也是很奇葩，只见过两次应用这个题目的情况，一个是这个题一个是/cf.
二次剩余的定义是 当存在某个x使得x^2 \equiv d(mod p)成立时，称“d是模p的二次剩余”，当对任意不成立时，称“ d是模 p的二次非剩余”
而对于斐波那契数列有更具体的性质：
继续阅读“[数论][二次剩余应用][组合数][等比数列] ZOJ 3774 Power of Fibonacci”
紫书DP课后题最后一题了，也算是把这一部分做完了吧。
这个题，在uva上的数据太水了，导致很多网上的题解代码是错误的。在gym10128H这里会wa。这些题解大多是用一个简单的贪心策略处理分段，然后用区间dp处理分出来的段落。但是实际上分段也需要用一个dp，比如数据 1 2 4 3 1 2，用简单的贪心分段就会把4 3分到前面那一段，这样的出来结果是5（当把1 2 放进4 3里的时候4和3都要打开），但是如果把4 3分到后面的1 2里答案是4，是更优的解。
先讲简单的部分：分好段之后的区间dp。这个就是普通的区间dp $$dp(l,r)=min(dp(l,i)+dp(i+1,r)+cost(l,i,i+1,r)),i\in[l,r)$$其中 \[dp(l,r)\]表示
[l,r]之间的套娃组装成1个所需要的最小花费, 继续阅读“[区间DP][双DP][×] UVA 1579&Gym 10128H Matryoshka”
昨晚肝这一场是真的赔了，傻不拉几的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的博客
利用并查集处理合并，并保存每个块对应的覆盖范围(在y轴上的)上下界；利用线段树（更新区间的范围从并查集维护的信息中得到）维护每个x.5的点对应的州数和城市数。区间修改单点查询，只要确定好x.5这些点在线段树中的对应的下标就可以了，我这里是x.5在线段树中下标为(x+1)。由于我写的是1-n的线段树写完了才发现题目说的0-n-1，只能把读进来的东西都++。具体的操作：对于road，先找两个点是否在一个块里，如果是了那就不用任何操作（画图可以看出来如果这俩是一个块里的那么他们覆盖范围之间一定已经有线了），否则先把这两个的分别的块对应的区域在线段树中减去他的影响，再将两个块合并之后，再在线段树中加上这一新块的影响。先减后加，这样就可以避免繁杂的分类讨论了。。。
第一版正经的线段树ac之后想了想感觉在这个情境下只需要保证叶子节点的信息有效就行了，推了一下感觉可以去掉maintain的操作。。。试了下果然可以，而且快了很多，在vjudge上已经是用线段树的跑的最快的了（前几名都是用的BIT emmm
wa的点：本来一气呵成写完很舒服但是没想到出了很多bug，因为一些愚蠢的bug调试了很久。。。。数据结构这块还是太弱了。
继续阅读“[线段树+][并查集][区间信息维护] UVALive 4730 Kingdom”
https://cn.vjudge.net/problem/UVA-10271
确实是经典。。。这种一开始没有什么头绪的dp，可以自己写出来几组样例，从中发掘最优解的性质，从而找到入手点。经过这样的一个xjb试探之后发现了：最优解的每组筷子中的短的那两根必定是在有序序列中相邻的。这样的话就可以确定一个转移的方法了，类似于背包里对于每个物品选还是不选，在这里对于每根筷子确定选还是不选，如果选，根据上面的性质他必须和之前的那根筷子组成一副。由此可以确定一个最基本的转移方程形式dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(len[i]-len[i-1])^2)，dp[i][j]表示对于前i个筷子分给j个人的最优解。这里还有一个问题是必须要给每个人再分一根最长的筷子，其实可以发现这个条件更好处理，只要满足i>=3*j就可以了：因为这个最长的筷子其实只要比另外俩长就可以，所以在最优解中的这根筷子有些人之间甚至可以换着用，顺序也无所谓，满足这个条件一定能分配好的。
对于这个状态转移方程，可以确定一个边界条件是dp[i][0]=0（从转移方程的第二部分可以得出来）
这个题自己当时主要还是思维限制，只想着怎么能有类似于dfs序线段树那种操作，或者是就某个点对他的子树做一个什么类似于线段树的打标记处理。。但是感觉太复杂了，没搞出来，而且也没有把可以离线这个点利用起来，还是too young
正解是在dfs过程中维护一个线段树，这棵树的下标是代表了当前dfs到的深度（而非节点），看到这儿就感觉是个很妙的操作，这样的话只需要每次进入到一个节点的时候把对应的属于该节点的所有的操作（这个需要离线处理，把对应的操作存用个vector存起来就可以了）都处理一遍，也就是把对应的所有的区间上的数值加上，dfs离开的时候把对应的区间上的数值减去，回滚一下，就可以保证在dfs过程中就把所有的操作处理完了。
