自己思路的问题：每次用一个中转节点多连一条线就是等于跳过了一个节点，想到了偶数就是/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”
比赛结束智商上线系列
昨天的时候看C没整明白然后来看D，没想出来构造方法又回去卡C结果最后都没出呵呵呵，今早起来写了几个样例，组合了下就发现了规律：每次找到left最大的那个人和right最大的那个人，如果不是同一个人就合并中间left和right重合部分，ans加上这一部分（ans+=max(maxleft,maxright)）然后把这俩人重合的部分消去合并成一个新人放回集合里；如果是同一个人那就自己一个人一个圈子就好了。
感性理解的话就是要尽可能的让长的段之间有重复，重复就可以节省椅子，而始终都找最长的left和right就能保证这一要求。
wa点：multiset中如果两个元素它们定义<运算符的那个信息相同他就认为是相同的，而erase的时候会把所有相同的都erase掉，所以为了区别不同的人加上了一个id。。。很神奇吧。。
这场有点惨的过分了，怎么说呢。。。经过了这一段的训练感觉该提高一些了但是却还是这样子。。。继续努力吧
这个题卡了是最最难受的，因为从矩阵的角度考虑不管怎么样都搞不出来一个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://codeforces.com/contest/1038/problem/E
“这题有点难受”系列。之所以能这么O(n)做完全是有且仅有4个点，玄学。
其实也不是很难受，主要是最后一组测试(test 117)让我意识到原来的处理方法对于那种特殊情况都不适用，然后感觉在这时候只能用n²算法才能解决。。。想了很久反正是，最后终于发现当（奇点数==4&&删去最小边会使得4个点不联通）这种情况只有两种，一种是三个点连成环然后剩下一个挂在外面，另一种是1到2和3到4有1条边，而2到3有两条，所以只要把这两种情况特殊判断一下就还是O(n)的算法了。。
正经地说：把1234看成4个点，n个block相当于边，题目意思就是找出一条最长的路使得每条路都只能走一次，无向图只能走一次，很显然的欧拉路径的操作。但是要分很多情况讨论。
首先分连通分量有几个的时候，当有2，3，4个的时候就是找到这几个连通分量中的最大值，因为这时候每个联通分量都一定是有欧拉路径的，3的时候可能比较难证明，但是可以通过4个点组成的图奇点只有024三种可能推出来。
然后当只有一个连通分量也就是四个点都联通的时候，讨论奇点数量，前面已经说过奇点数量只可能是024，当是02的时候直接全选因为一定有欧拉路径，当是4的时候再分类讨论：找权值最小的那条边，看他是不是去掉后会使得多出来一个连通分量，说是多出来一个联通分量其实只有可能是多出来一个孤立的点，因为其他情况都与（4个点都是奇点）这个条件相矛盾，所以删除这条边如果能使得原图不连通那么一定是分成了一个3个点一个1个点，这里面又有两种具体的情况，也就是之前说的，一种只有一个桥另一种有两个桥，如果不是这两种情况那么直接取全部的边然后删除掉最小权值边，如果是这两种情况则单独特判即可。。需要注意的是这两种情况需要循环一遍所有的边来确定最大值，因为删除的可能是其他的边也可能是桥。
https://hihocoder.com/problemset/problem/1457
要求求出来n个串中所有子串的十进制和。
考虑单个串的情况：顺着sam的边走的话，一个点的所有字串等于它所有的父节点的字串+c，c为从父节点转移来的路径字符，由十进制的性质可以知道当前节点（设为st）的和为则求出sam状态转移图的拓扑序然后刷sum即可；
多个串的情况：考虑把多个串合并为1个串，每两个串之间以‘9’+1填充（也就是: )，然后建立sam。此时要求出sam每个状态中有多少个不含：字符的子串，这里用到了一个性质就是，这个值恰好就是从初始状态S到状态st的所有”不经过冒号转移的边”的路径数目，而有向无环图上的路径数目也是一个经典的拓扑排序问题！
由此只需求拓扑序的过程中把有效子串个数求出来就行了。
wa点的话，注意第一次调用sam前要用init函数初始化。另外，拓扑排序无需纠结数据结构条件是指向父节点还是从父节点指向子节点。
继续阅读“[SAM][多串][不同子串十进制求和][拓扑排序] hihocoder #1457 : 后缀自动机四·重复旋律7”
http://newoj.acmclub.cn/problems/2057
看的时候没有什么思路，想过dp但是感觉数据量不可行，看了题解才意识到离散化即可O(n^2)，暴力刷表推出来每个点的最优值即可。
此外，还学习到了v[i][j]=v[i][j-1]+v[i-1][j]-v[i-1][j-1]+mp[make_pair(x[i],y[j])];这种处理方法，如果没有想到-v[i-1][j-1]的话，就不会想到推出来vij也就没有后面的操作了。此外，在二维平面上这种只有两个轴向转移的思想也是很重要。确定了dp的一个转移的方向。最后，确定答案的一步也很有趣，由于离散化导致的不能确定m天的位置，所以只能再遍历所有的点然后取小于等于m天的那些点向m天转移的最大值。
wa点的话离散化忘记去重。。。。很尴尬的操作
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://newoj.acmclub.cn/problems/2053
只要能想到用最小费用最大流去做，建图还是相对好想的：左边n个点表示n根蜡烛，右边n*m个点（或者m个点但是每个点有n条边连汇点，二者是等价的），然后源点连左边n个点之间cost为0容量为1，表示每个蜡烛最多被用一次，然后从左边到右边i到ai所有的n个分点连容量为1 cost为2*k-1的边，最后右边每个点跟汇点连容量为1 cost为0的边，最后跑最小费用最大流即可。
平方费用处理的话也不难毕竟看过lrj书上的处理平方费用的方法。。。这种平方费用的话可以拆点也可以拆边，但是思路都是新弄出来的边cost都是当流量从i到i+1的时候的增量，也就是i^2-(i-1)^2，因为这个差值是随着i增大而增大的，所以最大流增加的时候一定是从小到大选择这些边的，而这些边的cost从小到大依次选择就可以累加出来x^2，也就是与原来的要求等效了。
继续阅读“[最小费用流][平方费用][拆点/边建图] 2018camp Birthday”
http://codeforces.com/contest/1042/problem/D
嗯，大概是发现了自己以前一直没有正确理解mergesort。。。。
vp时候发现一开始这个题目过的人竟然比C多然后就提前去看了，但是竟然并没想出来正解emmmmmm，想过分治但是不知道怎么在线性合并左右段，看了前排dalao代码恍然大悟，其实就是逆序数的推广，这里把前缀和当成要处理的对象即可，如果是逆序数的话就是输出来一个数字右边有多少个比他大的，这里的话是sum[i]的右边有多少个比sum[i]+t小的，而t是常数所以其实几乎和逆序数一样。。如果仔细考虑逆序数的分治算法的话，会发现他能保证合并的时候线性是因为每次左右两边都是排好序的，这样的话就可以线性合并，而为什么排序这个操作不会影响到结果呢？因为在合并的时候左右两边各自的结果已经被计算过了，需要计算的仅仅是跨越中点的那些lr对！而这些计算和左右两边各自的顺序没有关系，只要保证左边的在左边右边的在右边就行了：因为我们是计算合法的数量，只要存在就+1，跟他什么时候存在早存在晚存在没关系。 继续阅读“[分治][mergesort][经典算法推广][实现] Codeforces Round #510 div2 D Petya and Array”
