http://codeforces.com/contest/1064/problem/D
这个题最操蛋的是我把复杂度弄错了导致没有敢写暴力。。不过官方并没有出题解所以我也不知道我的做法是否可行，只能说通过了目前的所有数据。
做的思路就是求出来原点到每个点所用的最小的left和最小的right，求的方法就是暴力bfs，但是这里有个问题是有可能会有一个点可以通过多条路径到达，那么该如何确定最小值？如果直接裸搜不打标记会使得无限循环，如果打标记则会使得多种可能没有考虑，我这里用了一个玄学剪枝就是当当前点的下一个点的数据有被更新的时候才加到queue里，否则就不加，可以保证去掉了很多无用的扩展也可以保证搜索可以结束。另外一个优化是加了点是否已经在queue内的判断，可以避免多余的入队操作（这个貌似也可以用在一般的dij里啊）
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”
思路简单，就是求出来结果的所有质因数的指数+1乘起来就行了。
首先由于题目的要求这里读入的ai只有两种情况，要么ai=p*q是两个不相等素数的乘积，要么ai=p^k，其中k取2，3，4。显然后一种情况很容易处理，但是第一种就有些难受了，直接的想法是用一些优秀的O(N^(1/4))的非完美大整数分解算法（这个看tutorial的评论区神仙各有千秋）。但是由于第一类的数只能分解成两个质因数，而且我们最后要的是质因数的指数而不需要关心质因数本身是多少，所以就有了更好的策略：如果一个数字的质因数在其他数字中出现过，那么一定可以通过gcd求出来，这时候等于说另一个质因数直接一除也能求出来，等于这个ai就完全解决了，像第二种情况一样加到map里即可；如果说这个数的俩质因数都没有在其他数字中出现过那么我们肯定不能求出来这俩数字是多少了，但是我们可以知道出现了俩独特的质因数，他出现且仅出现在所有aj==ai里，那么我们可以把ai直接存进map里，存起来他对应的加了多少次，另外要单独开一个set记录下来哪些ai是这样的ai，最后计算的时候如果是这样的ai的话就乘以(1+map值)的平方就可以了。
所以说一定要分析所给数据的性质，他的约束是解题的难点但同时也可能是解题的突破口。
写的时候还有一点弄错了就是把哥德巴赫猜想和这个搞混了。。那个是+这个是*，而且哥德巴赫猜想在1e18的范围内一定是有一个小的和一个大的，这个小的不超过1e5好像，所以那个是只需要枚举小的然后判断大的是否为质数即可。
其实也不是正常意义上的meet in the middle了，只是这个处理的思想有点像。（似乎每次做交互题都会卡？
自己做的时候是理解错题目意思了，以为图上只要联通的点都能返回YES，但是其实是按照他的限制下走的时候能走到才能返回YES。这样的话需要考虑的问题就比较好处理了。。。。一开始理解的那种的话根本没法在4*n次询问的限制下做出来。
因为右下半矩阵的路线只能通过询问（1，1）到该点的可行性来获得，左上半矩阵的路线只能通过询问（n,n）到该点的可行性获得，要想获得完整的可行路线只能在交界重合的地方处理，也就是反对角线上的方块。为了使得两个方向的推法能够走到同样的对角线点上，可以采取极端策略，左边的就尽量往下走，右边的尽量往左走，这样两种操作到最后的结果都是相同的，会走到对角线上的极端点（最左下的可行点），这时候就保证了两条路能够接上。 继续阅读“[思维][meet in the middle] codeforces 1023 E”
http://codeforces.com/contest/1013/problem/D
题意：每次可以从矩形的3个角产生第4个角，问至少需要添加多少个方块可以使得让整张图都充满方块。
自己想的是奇怪的思路，因为发现一个联通的块可以扩展到这个块的maxx，maxy，但是之后就不知道怎么做了。看了题解才恍然大悟，原来是把坐标转化成二分图的左右节点，然后考虑连通分量的个数就可以了。证明的时候，首先注意到一点就是二分图中两个点之间的路径个数一定是奇数，对于同一个连通分量中的左右两个点x，y，他们之间的距离如果是1的话那说明二者之间一定有了一条路径了，也就是这个点已经有一个方块了，如果不是1那么至少是3，每次取距离y最近的3个点，按照题目中给的性质，就可以生成一条新的边，也就是从倒数第四个直接联到y，这样的话，每次边的数量都会-2，到最后一定能减少到1，回到之前的情况。所以在同一个连通分量里的左右所有的点一定能连到一起，也就是说所有的方块一定能被涂上。这时候等于说连通分量和能全部染色等价了，我们就只需要计算出来最少需要多少条边使整个图成为连通图就行了。。其实也就是 连通分量数-1
wa点的话因为把n+m写成了2*n错了还以为横纵坐标是一样大的。。。愚蠢的错误emmmm
自己思路的问题：每次用一个中转节点多连一条线就是等于跳过了一个节点，想到了偶数就是/2，奇数是+1/2，但是没有想到怎么去统计实现。
这个问题最后的答案可以表示为（S+O)/2，其中S是所有点对之间的路径长度之和，O是路径长度为奇数的路径的数量。然后就是如何计算这两个数字的问题。
我以前的理解是求S得用两遍dfs的treeDP，然而这次学到了新操作就是可以分别考察每一条边他被多少对点之间的路径包含了，只需要求出有根树每个点对应的子树中的节点个数即可，S+=(n-subts[x])*subs[x]。
求O的方法就更妙了，画出来一颗有根树就可以发现，两个节点之间的距离奇偶性可以用他们到根节点的奇偶性来表示！（因为树形结构本身对于根节点来说有某种意义上的差分性质emmm），假如两个点到root的路径长度（也就是depth）奇偶性相同，那么他们之间的路径就是偶数的否则是奇的。所以只需要求出来所有的奇数层的节点个数乘以所有的偶数层的节点个数就可以得到O了。
继续阅读“[比赛][TreeDP][树的性质][换轴][统计技巧] codeforces 1060E Sergey and Subway”
这场有点惨的过分了，怎么说呢。。。经过了这一段的训练感觉该提高一些了但是却还是这样子。。。继续努力吧
这个题卡了是最最难受的，因为从矩阵的角度考虑不管怎么样都搞不出来一个O(n3)的算法，无论如何都不可能，然 而 ，然 而！这题目根本就不用考虑矩阵。。。因为每一行每一列都是成比例的啊。。。光给个矩阵怎么可能n²算出来答案？很明显是跟题目数据自身的性质有关系的，然后自己就傻脸看了俩小时不知道怎么操作，呵呵，出发点就不对怎么可能算出来。。。
因为每一行都是成比例的，比例是bi，所以要求一个最大的不超过x的子矩阵，只需要枚举上下边然后给预处理出来的sb数组乘个上下边之差就可以了，小于x的操作可以用sb[x/(pa[j]-pa[i-1])]来操作。。。。。。所有的处理都极其暴力，但是因为所有的处理都是在a或者b的一维序列上进行的，所以暴力也是n²，如果脑子里只有那个矩阵的话怎么都不可能n²，因为他是个二维的。。
写错的地方的话是x可能会比pb[m]大，这时候只需要取到这个最大值就可以了。
继续阅读“[比赛][CF][预处理][问题本身的性质] codeforces 1060C Maximum Subrectangle”
http://newoj.acmclub.cn/problems/2054
题目给了一个方块板子，每次要么给同一列所有数字加上同一个数，要么给同一行加上全一个数，然后现在给出经过若干次这种操作之后的一个局面但是把其中一个点换成了-1，要求出来这个点的值应该是多少。
一开始没什么思路，后来写了写表达式似乎发现了可以直接解出来。设ri是第i行加的总数字，ci是第i列加的总数字，row是现在的-1所在的一行的和，col是-1所在的一列的和，若-1坐标为x，y，则可以设要求的数字为t=rx+cy，这时候可以列出来两个方程：
① row+col+2t+21==nt+Σri+Σci
② n*(Σri+Σci)==t+1+Σboard[i][j]
其中第一个方程是要求的那一点的行和列的和的两种表达式，第二个方程式整个board上的所有的点的和的两种表达形式。如果把(Σri+Σci)看作一个整体消掉，可以直接求出来t的表达式t=(n*(row+col)+2*n-Σboard[i][j]-1)/(n-1)^2
http://codeforces.com/contest/1041/problem/E
比赛完5min想到了ac做法emmmm
并没有看懂官方题解，NO的判别其实很简单，只要有b不是n的情况就NO，因为不管怎么分都一定会有一个n。YES的情况怎么构造？我自己的做法是把n作为根节点，把条件排序后从小到大考虑：如果一个点出现了一次，那么就连一条从根节点到这个点的边，并且把这个点标记为用过的；如果出现了多次，那么就到前面找没有标记过的点找一个最小的插到当前点和他的父节点之间，并且把找到的点也标记为用过的。
所以为什么是正确的？首先按照a排序后可以发现如果一个数字重复出现了那么一定是从第ai个往前重复，如1 3 3 4，这个重复的3一定是从第3个往前延申，按照我的构造方法，如果不是这样那就不可能满足要求，因为3和5之间的路上的节点一定是全是小于3的数字，而且以3为根的子树我这里直接让他为空。这样的话总可以在前面找到足够数量的数字来插入到3的这一条链上（忽然感觉说不清楚了但是这么构造一定是对的emmmmm
wa的话感觉可能是当时很饿然后树上的插入操作和标记都写错n次，神奇的是每次都能通过前30个test然后被3x刷掉。。
题目：http://codeforces.com/problemset/problem/1030/F
这个题最主要的是自己没有想出来怎么求出那个“不动的点”，因为其实整体的cost用k去表示出来是很困难的，求出来也无法发现其极值点。但是如果考虑差分就会比较好做，很容易发现当当前设的k点变成k+1时，cost变化了(S(l,k)-S(k+1,r))*(p[k+1]-p[k])，其中S(l,r)=Σw[i](l<=i<=r)。这样的话很明显当且仅当S(l,k)≤S(k+1,r)S(l,k)≤S(k+1,r)时k+1比k更优。所以我们只要找到最小的k使得S(l,k)>=S(l,r)/2就行了！
然后是对于一个[l,r]对求出k之后，如何快速的求出其cost。
对于i∈(l,k)i∈(l,k) 代价是∑(pk−pi−(k−i))∗wi（l<=i<=k)
对于i∈(k,r)i∈(k,r) 代价是∑(pi−pl−(i−k))∗wi（k<=i<=r)
把pi-i看成一个整体，记为ai，就可以得到cost=∑(ak−ai)∗wi(l<=i<=k)+∑(ai−al)∗wi(k<=i<=r)
展开整理就可以得到cost=ak*(S(l,k)-S(k,r))-(Σwi*ai(l<=i<=k)-Σwi*ai(k<=i<=r))。这样的话用一个BIT快速求S(l,r)，另一个BIT快速求Σwi*ai就可以了。
wa点的话，发现了一个以前没有注意到的bug，那就是我每次判断都是if(x>mod)x%=mod;但是忽然意识到在有减法的运算中，还有一种下越界的可能性，所以应该是if(x>mod||x<-mod)x%=mod; 继续阅读“[BIT][思维][反证][差分求极值] codeforces1030F Putting Boxes Together”
