emmm第一感觉好像后缀数组之类的结构，但是这个每个元素是个整数，而字符串处理中每个元素都是一个长度为1的字符，，，所以很难把他等同于字符串来处理。但是直接理解的话，要求的话一定是找到一个排列，然后考虑他的每个子段，然后再在其他所有的排列中去找有没有这个子段，直接裸暴力的话n^3*10，肯定不行，但是想一下如果仅仅是考虑所有的子段就一定是不小于n^2的了，所以起码要在这里进行优化。然后由字符串的性质就可以知道一个长度为i的串如果满足要求的话，那么他的所有子串也都是满足要求的这些子串可以不用再计算了，发现了这个之后怎么去实施这个想法？考虑以每个下标i为开始的最长子串，这里如果用暴力的方法每次从i开始递增， 然后在与其他串判断，则当然仍然是n^3的，但是可以发现与其他串判断这个过程其实有很多重复的判断，假如已经知道了i到i+k个存在的话，判断第i+k+1个时候只需要把这一个数字去和其他的串中对应的数字比较是否全部相等就可以了，这样的话把复杂度降到了n^2*10，但是仍然不够，再考虑之前说的，枚举字段中的重复假设已经知道以i开始的到i+k个数字满足要求，那么在算以i+1开始的子段的时候，可以直接从第i+1+k+1个数字开始，也就是说中间的那些都不用再考虑了，因为这些信息已经在算第i个的时候计算过了。所需要保存的只有每个序列中数字i出现的位置而已。
[暴力][BFS][最短路][复杂度分析] codeforces 1064D Labyrinth
http://codeforces.com/contest/1064/problem/D
这个题最操蛋的是我把复杂度弄错了导致没有敢写暴力。。不过官方并没有出题解所以我也不知道我的做法是否可行，只能说通过了目前的所有数据。
做的思路就是求出来原点到每个点所用的最小的left和最小的right，求的方法就是暴力bfs，但是这里有个问题是有可能会有一个点可以通过多条路径到达，那么该如何确定最小值？如果直接裸搜不打标记会使得无限循环，如果打标记则会使得多种可能没有考虑，我这里用了一个玄学剪枝就是当当前点的下一个点的数据有被更新的时候才加到queue里，否则就不加，可以保证去掉了很多无用的扩展也可以保证搜索可以结束。另外一个优化是加了点是否已经在queue内的判断，可以避免多余的入队操作（这个貌似也可以用在一般的dij里啊）
[拓扑序][博弈][重点错误] codeforces 1033C Permutation Game
这个题wa到最后才意识到是dfs刷表的思想本身是错误的，必须按照拓扑序来处理，这两个是不等价的。不等价的原因是dfs可能会多次刷到同一节点而且这个节点的父节点还没有完全确定下来。比如当某个节点只有一个父节点的时候，本来dfs给了他1，也就是必胜态，但是如果某一次之后的刷新把父节点变成了1，那么由于该节点只有一个父节点所以他只能变成0。而原来写的dfs不能解决的就是这样一个问题：对于一个节点来说，是不是所有的父节点都是1或者至少有一个0，因为单纯的dfs可能会求很多遍这个点（如果不这样又没办法更新），如果用拓扑序的话就可以保证在搜到一个点的时候这个点的父节点已经全部搞定了，这也跟拓扑序处理的时候每次只走“一步”有关系。这样的话就可以保证不会有多余的1没有变成0了。
[换轴][并查集][异或性质][连通分量] codeforces 1040E Network Safety
http://codeforces.com/contest/1040/problem/E
这个做法最重要的是原本的每一条边两端点一定不相等，所以两个点如果同时被异或结果一定仍然不相等。 然后就是考虑一个点被异或另一个点没有被异或的情况，一开始觉得会很复杂？但是实际上不是这样的，远没有想象中的复杂： 当x确定的时候，只有a⊕b==x的那些边会受到影响，这些边必须同时被选中，而剩下的，无所谓。。所以就把这些边连起来的点缩点之后就成了2^q的选择方式了。。
实现细节：①会卡并查集退化，所以必须写按秩合并 ②每次只要记录下被改动的点，然后下一次把这些点并查集复原即可，否则由于并查集的初始化时间复杂度会退化。
[比赛][TreeDP][树的性质][换轴][统计技巧] codeforces 1060E Sergey and Subway
自己思路的问题：每次用一个中转节点多连一条线就是等于跳过了一个节点，想到了偶数就是/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”
[比赛][贪心][STL] codeforces1060D Social Circles
比赛结束智商上线系列
昨天的时候看C没整明白然后来看D，没想出来构造方法又回去卡C结果最后都没出呵呵呵，今早起来写了几个样例，组合了下就发现了规律：每次找到left最大的那个人和right最大的那个人，如果不是同一个人就合并中间left和right重合部分，ans加上这一部分（ans+=max(maxleft,maxright)）然后把这俩人重合的部分消去合并成一个新人放回集合里；如果是同一个人那就自己一个人一个圈子就好了。
感性理解的话就是要尽可能的让长的段之间有重复，重复就可以节省椅子，而始终都找最长的left和right就能保证这一要求。
wa点：multiset中如果两个元素它们定义<运算符的那个信息相同他就认为是相同的，而erase的时候会把所有相同的都erase掉，所以为了区别不同的人加上了一个id。。。很神奇吧。。
[比赛][CF][预处理][问题本身的性质] codeforces 1060C Maximum Subrectangle
这场有点惨的过分了，怎么说呢。。。经过了这一段的训练感觉该提高一些了但是却还是这样子。。。继续努力吧
这个题卡了是最最难受的，因为从矩阵的角度考虑不管怎么样都搞不出来一个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”
[构造][树][贪心] codeforces 1041E Tree Reconstruction
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刷掉。。
[分治][mergesort][经典算法推广][实现] Codeforces Round #510 div2 D Petya and Array
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”
[数学][质因数分解][预处理优化] codeforces 1034A Enlarge GCD
http://codeforces.com/problemset/problem/1034/A
题意问给定n个数，从中最少去掉多少个数之后可以使得剩下的数字的gcd严格大于原序列的gcd。
思路：先求出来原序列的gcd，无解的情况很容易判断，当序列中最大的数字就是gcd的时候无解。对于有解的情况，把每个数字除以这个gcd，剩下的一个序列就是gcd为1的序列，然后只要求出来去掉多少个数字之后可以使得序列gcd不为1就行了。这时候考虑去掉k个数字之后剩下的数字gcd为几，不妨设为w，很容易知道如果能求出来对于每个质数有多少个数字有这个质因子，那么取“在序列中出现最多次数的那个质数”的出现次数就是最大的剩下的序列中的元素个数，这里的出现次数是说如果ai%w==0则cnt++的意思。那么能求出来剩下的元素最多有多少个，也就能求出来去除的元素最少有多少个了。
比赛时候这个题是把我T爆了，主要是很难确定对于每个数暴力质因数分解好还是线性筛预处理出来1.5e7之内的素数比较好，一开始一直用的暴力质因数分解但是test23一直t，最后6min换了预处理素数ac了，其实手推渐进复杂度感觉二者差不多。。。。玄学卡常，而且最后过了也是800ms飘过。。。